A few months ago we launched International calling with JMP.  One of the big tasks leading up to this launch was computing the rate card: that is, how much calls to different destinations would cost per minute.  While there are many countries in the world, there are even more calling destinations.  Our main carrier partner for this feature lists no fewer than 59881 unique phone number prefixes in the rates they charge us.  This list is, quite frankly, incomprehensible.  One can use it to compute the cost of a call to a particular number, but it gives no confidence about the cost of calls in general.  Many items on this list are similar, and so I set out to create a better list.

My first attempt was a simple one-pass algorithm.  This would record each prefix with its price and then if a longer prefix with a different price were discovered it would add that as well.  This removes the most obvious effectively-duplicate data, but still left a very large list.  I added our markup and various rounding rules (since increments of whole cents are easier to understand in most cases anyway, for example) which did cut down a bit further, but it became clear that the one-pass was not going to be sufficient.  Consider:

1. +00 at $0.01
2. +0010 at $0.02
3. +0011 at $0.02
4. +0012 at $0.02
5. +0013 at $0.02
6. +0014 at $0.02
7. +0015 at $0.02
8. +0016 at $0.02
9. +0017 at $0.02
10. +0018 at $0.02
11. +0019 at $0.02

There are many sets of prefixes that look like this in the data.  Of course the right answer here is that +001 is $0.02, which is much easier to understand than this list, but the algorithm cannot know that until it has seen all 10 overlapping prefixes.  Even worse:

1. +00 at $0.01
2. +0010 at $0.02
3. +0011 at $0.02
4. +0012 at $0.02
5. +0013 at $0.02
6. +0014 at $0.02
7. +0015 at $0.03
8. +0016 at $0.02
9. +0017 at $0.02
10. +0018 at $0.02
11. +0019 at $0.02

From this input we would like:

1. +00 at $0.01
2. +001 at $0.02
3. +0015 at $0.03

So just checking if the prefixes we have so far are a fully-overlapped set is not enough.  Well, no problem, it’s not that much data, perhaps I can implement a brute-force approach and be done with it.

Brute force is very slow.  On this data it completed, but as I found I kept wanting to tweak rounding rules and other parts of the overlap detection the speed became really problematic.  So I was searching for a non-bruteforce way that would be optimal across all prefixes and fast enough to re-run often in order to play with the effects of rounding rules.

Trie

As I was discussing the problem with a co-worker, trying to speed up lookups we were thinking about trees.  Maybe a tree where traversal to the next level was determined by the next digit in the prefix?  As we explored what this would look like, it became obvious that we were inventing a Trie.  So I grabbed a gem and started monkeypatching things.

Most Trie implementations are about answering yes/no questions and don’t store anything but the prefix in the tree.  I wanted to be able to “look down” from any node in the tree to see if the data was overlapping, and so storing rates right in the nodes seemed useful:

def add_with(chars, rate)
    if chars.empty? # leaf node for this prefix
        @rate = rate
        terminal!
    else
        add_to_children_tree_with(chars, rate)
    end
end

But sometimes we have a level that doesn’t have a rate, so we need to compute its rate from the majority-same rate of its children:

def rate
    # This level has a known rate already
    return @rate if @rate

    groups =
        children_tree.each_value.to_a         # Immediate children
        .select { |x| x.rate }                # That have a rate
        .combination(2)                       # Pairwise combinations
        .select { |(x, y)| x.rate == y.rate } # That are the same
        .group_by { |x| x.first.rate }        # Group by rate
    unless groups.empty?
        # Whichever rate has the most entries in the children is our rate
        @rate = groups.max_by { |(_, v)| v.length }.first
        return @rate
    end

    # No rate here or below
    nil
end

This algorithm is naturally recursive on the tree, so even if the immediate children don’t have a rate they will compute from their children, etc.  And finally a traversal to turn this all back into the flat list we want to store:

def each
    if rate
        # Find the rate of our parent in the tree,
        # possibly computed in part by asking us
        up = parent
        while up
            break if up.rate
            up = up.parent
        end

        # Add our prefix and rate to the list unless parent has it covered
        yield [to_s, rate] unless up&.rate == rate
    end

    # Add rates from children also
    children_tree.each_value do |child|
        child.each { |x| yield x }
    end
end

This (with rounding rules, etc) cut the list from our original of 59881 down to 4818.  You can browse the result.  It’s not as short as I was hoping for, but many destinations are manageable now, and thanks to a little bit of Computer Science we can tweak it in the future and just rerun this quick script.

Hi everyone!

Welcome to the latest edition of your pseudo-monthly JMP update!

In case it’s been a while since you checked out JMP, here’s a refresher: JMP lets you send and receive text and picture messages (and calls) through a real phone number right from your computer, tablet, phone, or anything else that has a Jabber client.  Among other things, JMP has these features: Your phone number on every device; Multiple phone numbers, one app; Free as in Freedom; Share one number with multiple people.

Today JMP turns 5 years old!  We launched on this day in 2017 with a fairly basic set of features: bidirectional Canada/USA SMS and MMS, with incoming calls directed to a pre-existing phone number.  Since then we’ve kept pushing further and further toward feature-parity with the most popular mobile phone number providers, adding outgoing calls, international texting, and group texting.

We have been actively testing the final piece of this work, international calling, and are pleased to announce today that we made it!  With the addition of international calling, which is available to all JMP users as of right now, we are now phone-feature-complete.

What does this mean?  In short, we now support all the features that other providers of mobile phone numbers support: bidirectional MMS (including group texting), domestic and international SMS, and domestic and international calling.  So if you or your friends have been waiting to try JMP until we finished all these features, now is the time to get the word out and try it!

On top of international calling, we now support using as many minutes per month as you like (with 120 Northern America minutes worth of credit included by default) - see our new comprehensive pricing page for details.

You may be wondering: Where do we go from here?  Well, we still have much work to do, and many more newsletters like this one coming up to let you know about it!  There are two main areas of work left:

First, we want to keep our finger on the pulse of telephony, specifically making sure that we add any features that mobile carriers are adding to their phone numbers, like RCS.  If we find such a feature supported on at least Android and iOS, we’ll get it into JMP as soon as possible (for RCS, the rollout is limited, and only on Android so far - if you know of other phone number features we’re missing, reply to let us know!).  Also, we have not forgotten about the many kind requests we’ve received for JMP numbers outside of the USA and Canada.  Those are on our list!

Second, we want to make JMP as easy to use as possible.  There is still much work to do here, particularly on simplifying signups, adding and managing contacts, and group texting.  We want to make sure that group text threads are easier to follow, which requires a little bit of development work yet.  And we are actively working on improving the Cheogram app that many of you have started using on Android, to include these fixes and an easy way to signup for JMP.  In the not too distant future you’ll be able to install the Cheogram app, pick a JMP number from the app, and start using it right away.

In other news, Dino 0.3 has been released which brings with it voice calling features compatible with those used by Converations, Snikket, Movim and JMP! It’s still early days and so there may be some compatibility issues, but reports say the features are working for people.

Lastly, as part of JMP’s 5 year anniversary, we are unveiling our new logo today too!  You can check it out at the usual places, such as https://jmp.chat/ and elsewhere.  Our old logo (which is still live at its old location for the nostalgic) has served us well for the past half decade, and we appreciate all it’s done for us.  The new logo reflects how increasingly close we’re getting to JMP being easy to use for the average person, and hopefully our approachableness.

As always, we’re very open to feedback and would love to hear from you if you have any comments, questions, or otherwise.  Feel free to reply (if you got this by email), comment, or find us on any of the following:

• The chatroom remains the heart of the community.  You can also join from your web browser.
• The blog, where you may be reading this. Can also be followed in a client like Movim.
• The Lemmy Community
• The Subreddit
• On Twitter

Here’s to many more years of JMP!