Call Routing problem

This project is inspired by a real-world problem at a telephony API company – let's call it Teleo.

The primary task is to implement an international call routing system that finds the least cost route through multiple carriers. One of the goals of this project is to demonstrate the wide variety of solutions and compare the trade-offs with each.

Background

Phone Numbers

Phone numbers are structured hierarchically and reveal the geography of call routing networks. International phone numbers begin with a + followed by the country code, area code, local code, and further groups that represent successively smaller locales. For example, U.S. phone numbers use the format +1-222-333-4444, while U.K. numbers look like +44-222-3333-4444, and Japanese numbers are written as +81-22-333-4444. Fortunately, phone numbers can be normalized into a standard format beginning with a '+' followed by only digits (no hyphens, dots, or spaces). Normalized U.S. numbers look like this: +12223334444. For this project, you will only need to use normalized numbers.

Routes

A route is a path through a carrier's phone network. Longer routes connect specific geographic regions while shorter routes reach larger regions. Hierarchical phone numbers allow routes to be easily represented with just a short phone number prefix. For example, +1415234 identifies a neighborhood in San Francisco, +1415 represents greater San Francisco, +1 covers the entire US, and +4420 covers most of London.

Carriers

Teleo has contracts with multiple telephone carriers which each specialize in different geographic regions, but they often overlap. Thus, their competitive advantage is that they can choose which carrier to route outgoing phone calls through to minimize costs. When finding a route to use in a single carrier's route list, the longest matching prefix must be used, as it's the most specific route. Some phone numbers may match prefixes in multiple carrier route lists, and in this case you may choose the least expensive one. In the rare case of identically priced routes, either is acceptable.

Input Data

Input data comes in several plain text files. Some represent carrier route lists while others contain phone numbers of which you need to find the least cost route.

Carrier Routes

Each carrier's routes and their associated costs are given in a single file. Each line is a single route formatted as a comma-separated pair: a route's normalized prefix (starting with a +), then its cost in USD (a floating-point number). For example:

+1512,0.04
+1415,0.02
+1415234,0.03
+1415246,0.01

These files are named "carrier-routes-N.txt" where N is an integer. (Carrier 1, 2, 3, ...)

Using the carrier route list above, the cost of calling +14152345678 would be $0.03, as it matches with the prefixes +1415 and +1415234 (longest match), but not with +1415246.

Phone Numbers

The phone numbers you need to look up the route costs for are each normalized and given on separate lines of a file. For example:

+15124156620
+14152345678
+19876543210

These files are named "phone-numbers-N.txt" where N is an integer.

Output Data

After finding the least cost route for each phone number, write the number and its cost on a comma-separated line of a new text file. If there is no route for a number, write 0. For example, using the carrier route list and phone numbers given above, the output is:

+15124156620,0.04
+14152345678,0.03
+19876543210,0

Name these files "route-costs-N.txt" where N is the scenario number (see below).

Scenario: List of route costs to check

You have a carrier route list with 100,000 (100K) entries (in arbitrary order) and a list of 1000 phone numbers. How can you operationalize the route cost lookup problem?


I have a carrier route list that contains the prefix of a route and the tariff that applies to it, looking somewhat like this:

+86153,0.84
+449275049,0.49
+8130,0.68
+4928843955,0.40
+449187847,0.48
+8197753,0.75
+449916707,0.58
+64655676,0.40
+34924199,0.39
+1941613,0.05

I name these input text files "route-costs-N.txt" where N is the scenario number of phone call routes.

The output files are generated as following:

After finding the least cost route for each phone number, write the number and its cost on a comma-separated line of a new text file. If there is no route for a number, write 0.

Code snippet of my code can be found here.

Testing files for valid phone numbers are found here.

import sys
from datetime import datetime

_end = '_end_'


def phone_route_cost_check(filename, number):
    open_file = open(filename, 'r')
    data = open_file.readlines()

    number_cost = []
    for line in data:
        print(line)
        for i in range(0, len(line)):
            if line[i] == ',':
                print(i)
                number = line[0:i]
                price = line[i+1:-1]
                number_cost.append((number, price))

    print( number_cost)
    trie = make_dictionary_trie(number_cost)

    open_file.close()


def make_dictionary_trie(all_tups):
    trie_root = dict()

    for tup in all_tups:
        current_node = trie_root
        number = tup[0]
        price = tup[1]

        for letter in number:
            current_node = current_node.setdefault(letter, {})
        current_node[_end] = price
    # print trie_root
    return trie_root


def search_trie_for(trie, prefix):
    current_node = trie
    for letter in prefix:
        if letter in current_node:
            current_node = current_node[letter]
        else:
            return False
    else:
        if _end in current_node:
            return current_node[_end]
        else:
            return False


def autocomplete_for(trie, prefix):
    current_node = trie
    for letter in prefix:
        if letter in current_node:
            current_node = current_node[letter]
        else:
            return False


def print_trie(trie, prefix):
    current_node = trie
    word = prefix
    for key in current_node:
        if key == _end:
            print (str(word))
        else:
            word = prefix + key
phone_route_cost_check('route-costs-10.txt', '+14152345678')

My output shows a list of phone numbers and cost:

+86153,0.84

6
+449275049,0.49

10
+8130,0.68

5
+4928843955,0.40

11
+449187847,0.48

10
+8197753,0.75

8
+449916707,0.58

10
+64655676,0.40

9
+34924199,0.39

9
+1941613,0.05

8
[('+86153', '0.84'), ('+449275049', '0.49'), ('+8130', '0.68'), ('+4928843955', '0.40'), ('+449187847', '0.48'), ('+8197753', '0.75'), ('+449916707', '0.58'), ('+64655676', '0.40'), ('+34924199', '0.39'), ('+1941613', '0.05')]
  • Your description confuses me. I don't understand where the 0.09$ comes from and where the prefix +1415 is defined. Can you clarify that, please? – Roland Illig Nov 4 '17 at 7:44
  • I provide the cost for the routes for each line next to the phone pre-fix. I calculate the cost by simply looking the cost files for each routes. For example, using the carrier route list and phone numbers given at DropBox: dropbox.com/sh/tj6ppp6uwf12cce/AADje96PJhfsIXJEtP1OjwjFa – NinjaG Nov 6 '17 at 23:00
  • 3
    Re "+1 covers the entire US": actually, +1 covers most of North America, including Canada and many Carribean countries. Though that's not relevant to the code. – Toby Speight Jul 10 at 14:17
  • Hi NinjaG, are you sure you want to accept my answer? Make sure to accept the one that helped you the most, which is not necessarily the one with the most votes! – janos Jul 17 at 5:30
up vote 6 down vote accepted
+50

Working with files

Always use a context manager with when working with files. Instead of this:

open_file = open(filename, 'r')

# ...

open_file.close()

Write like this:

with open(filename, 'r') as open_file:
    # ...

This way you don't need to call open_file.close().

Use Python classes to implement Abstract Data Types

A group of functions take a trie as parameter to perform various operations on it. This is one way to implement an Abstract Data Type. Python offers a better way, using classes. That will provide better encapsulation enforced by the grammar, and a much simpler usage.

Program organization

I don't understand how to use this program.

  • The phone_route_cost_check function reads the input file, builds a list of (number, price) tuples, prints it, builds a trie without doing anything with it.

  • The functions search_trie_for, autocomplete_for and print_trie are not used at all.

  • sys and datetime are imported but not used.

  • The phone_route_cost_check prints stuff that doesn't look useful for anything.

I suggest to rethink how this program should be used. A good start might be to enumerate intended use cases, and expected outputs.

Broken print_trie

The name of this function seems to imply it's intended to print a trie, but it's broken.

Broken autocomplete_for

This function will return either False, or None. I don't think you intended it like that.

Parsing comma separated values

This is a very poor way to split line on a ,:

for i in range(0, len(line)):
    if line[i] == ',':
        number = line[0:i]
        price = line[i+1:-1]

A more natural way would be to use split:

number, price = line.strip().split(',')

Iterating over list of pairs

Instead of this:

for tup in all_tups:
    number = tup[0]
    price = tup[1]
    # ...

A simpler and more natural way to iterate over pairs would be:

for number, price in all_tups:
    # ...

You have identified a reasonable datastructure to use for this problem. And your code is decently formatted and separated out into functions. However, your solution conflates behavior of this datastructure with the concerns of the project. I'd recommend separating those so that you can test each in isolation.

Example:

  1. Given a trie that works properly, can code that uses it correctly identify the cheapest route?
  2. And then given a series of inserts followed by a query does your trie return the correct result?

With this separation, the trie doesn't have to be concerned with any of the specifics of phone numbers (including their representation, how they're parsed, where they're loaded from). And the business logic doesn't have to care about how the trie works.

So first, let's look at specific small things that you can improve in your code, then we'll take a stab at apply them along with this overarching idea of separating concerns.

  • Unused imports
  • Try to follow PEP8; it's a good style guide to follow and will put you in a position to write good, Pythonic code (use flake8 to see what needs fixing)
  • When dealing with files, sockets, etc. always use with to ensure that they are always cleaned up (ex. with open(filename) as f: print(f.read()))
  • range(0, n) can just be range(n)
  • Don't mix print()s into library code. Try to extract all IO so that code is reusable in other contexts. Ideally only main() should be doing IO.
  • Use a main() function invoked via if __name__ == '__main__': main()
  • In your main function use something like argparse to parse for arguments that you now have hardcoded
  • _end = '_end_' as a sentinel is not very pythonic. We'd probably use None in this case. But as you'll see below I don't actually think you need the sentinel.
  • If f is a file, then you can just do for line in f instead of using readlines(). The former streams the data, which will be much more efficient for large files.
  • Use tuple unpacking where appropriate (ex. for number, price in all_tups:)
  • Instead of your look to separate on the ',' use builtins! Specifically, number, price = line.split(',', 1). Note that the 1 is important here because it ensure that this can't raise a ValueError if there is more than 1 comma.
  • In search_trie_for you seem to be returning a price or False. Usually we would use None instead of False here. Or, if it was an error to lookup something that didn't exist, we would raise IndexError.
  • You should document your functions with """Docstrings.""" as the API they expose isn't entirely clear from their names.

With that in mind, let's design an optimal (and ideally, Pythonic) API for your business logic. We'll see how Python allows us to easily wrap this in a convenient CLI interface. Then we'll use the business logic to inform an appropriate API for our trie. Instead of using a bunch of disparate functions, let's package this behavior up into a class:

class PhoneRouteTable:
    @classmethod
    def create(cls):
        return cls(Trie())

    def __init__(self, costs):
        self._costs = costs

    def insert_route(self, route, cost):
        """
        Insert a carrier's phone route with the given cost.

        route - should be a normalize phone prefix (ex. +12345)
        cost - should be a Decimal
        """
        try:
            self._costs[route] = min(self._costs[route], cost)
        except IndexError:
            self._costs[route] = cost

    def compute_cost(self, phone_number):
        """Returns the Decimal cost of routing phone_number."""
        try:
            raise self._costs.last_value_along(phone_number)
        except IndexError:
            raise UnrouteablePhoneNumberError(phone_number)

That should be it. Re-reading the project specs indicates that we only need to be able to support adding routes and querying for route costs. This class handles both. A few things to note:

  • The use of the create classmethod instead of just creating the Trie inside the constructor allows us to unit test. In this way, we can pass in a mocked trie to test the business logic against
  • The trie raises standard python exceptions when it encounters errors. Where appropriate, we convert it to our own domain specific exceptions
  • Doc comments!
  • This code contains no trie logic, nor logic about parsing the data. It should be very straightforward to test

Now let's see how fantastic argparse is by wrapping this business logic in a CLI app and learning a bit about efficient data processing in Python:

from argparse import ArgumentParser, FileType
import csv
from decimal import Decimal
# from x import PhoneRouteTable, UnrouteablePhoneNumberError
import sys

def main():
    args = get_args()
    routes = PhoneRouteTable.create()

    # Import carrier route costs
    for carrier in args.carriers:
        for prefix, cost in csv.reader(carrier):
            try:
                routes.insert_route(prefix, Decimal(cost))
            except ValueError:
                print(f'Bad cost: {cost}', file=sys.stderr)
                sys.exit(1)

    # Answer queries for routing costs
    for phone_number in args.phone_numbers:
        try:
            cost = routes.compute_cost(phone_number)
        except UnrouteablePhoneNumberError:
            cost = 0

        print(f'{phone_number},{cost}')

def get_args():
    parser = ArgumentParser(description='compute costs to route phone calls')

    parser.add_argument('carriers', type=FileType('r'), nargs='+',
                        help='carrier csv files with prefix,cost rows')
    parser.add_argument('--phone-numbers', type=FileType('r'), default=sys.stdin,
                        help='file containing a list of phone numbers for which to compute costs')

    return parser.parse_args()

argparse is really swell! Notice how it succinctly allows us to define a CLI API that accepts multiple route files and one phone numbers file (defaulting to stdin). It automatically opens the files for us. Then, we are careful to process them as a stream instead of reading entire files in (which can be slow, especially for large input files). We also use csv.reader to parse the route files instead of doing the separating ourselves. Also notice our appropriate use of for to iterate over lines in files (or lines in csv). We take care to properly handle exceptions either gracefully or by printing an error to stderr and exiting with an appropriate error code. We also use Decimal instead of floats, because you should never use floats for money.

This allows for invocations like this:

$ ./compute_phone_cost.py routes/*.txt --phone-numbers phone_numbers.txt

Now that we have working business logic (which we should test), let's look into the trie. We've already codified an API for our trie when writing the business logic. Let's see what it looks like alone.

trie['a'] = 5
trie['abc'] = 7
trie['abcd'] = 10
trie['abcd'] = min(trie['abcd'], 9)
trie['bcd'] = 18

print(costs.last_value_along('abcd')) # 9
print(costs.last_value_along('abc'))  # 7
costs.last_value_along('b')           # ValueError

Now let's see how we can implement a class with this API. We'll take advantage of some __dunderscore__ methods and builtin python behavior:

class TrieNode:
    def __init__(self):
        self.value = None
        self.subtrie = Trie()


class Trie:
    def __init__(self):
        self._nodes = {}

    def __getitem__(self, prefix):
        key, remaining_prefix = self._split_prefix(prefix)

        node = self._nodes[key]
        if remaining_prefix:
            return node.subtrie[remaining_prefix]
        else:
            if node.value is None:
                raise KeyError('key not in trie')

            return node.value

    def __setitem__(self, prefix, value):
        key, remaining_prefix = self._split_prefix(prefix)

        node = self._nodes.setdefault(key, TrieNode())
        if remaining_prefix:
            node.subtrie[remaining_prefix] = value
        else:
            node.value = value

    def last_value_along(self, prefix):
        """
        Returns value of the deepest node (with a value) on a walk of prefix
        through the trie.
        """
        key, remaining_prefix = self._split_prefix(prefix)

        try:
            subtrie = self._nodes[key].subtrie
            return subtrie.last_value_along(remaining_prefix)
        except KeyError:
            return self[key]

    def _split_prefix(self, prefix):
        try:
            return prefix[0], prefix[1:]
        except IndexError:
            raise KeyError('empty key')

Note how we use the TrieNode to avoid your sentinel. This also has the nice side effect of giving us an empty dict upon creation so we don't have to special case setting keys that are brand new (none of their prefixes exist in the tree). We rely heavily on the correct and pythonic default behavior of dicts and raise errors where appropriate.

Hopefully that gives you some ideas about how to apply the major principles of separation of concerns and single responsibility along with some of the small tips and tricks I gave related specifically to your code.

When thinking about optimizations, we can now concern ourselves with just the datastructure. If we test the business logic with a mocked trie, we know that as long as our optimizations pass our trie unit tests (and our unit tests are thorough), then we still have a correct project. Without delving into code too much, one problem with tries is that you can get lots of unique suffixes that end up looking like long linked lists if you were to graph the trie. This is inefficient for space (each node along these paths must have a value and a dict associated with it). You could look into doing some kind of key compression where inserting 'abc' literally inserts self._nodes['abc']. However, this does require some more bookkeeping to properly handle more inserts (what if you insert 'a' afterwards, you need to fragment the exists 'abc' into 'a' and 'bc' so you can insert the new 'a' value?) and complicates lookup logic. For more information, see the Wikipedia article: Trie § Compressing tries.

  • Didn't have the time to go through your entire answer (or the question, for that matter), so correct me if I got this wrong, but if this is the canonical 'I need a sentinel as a flag' case, the most common solution is simply to instantiate object and use the is operator, rather than using str or None. – Daniel Jul 15 at 18:25
  • Yes that’s true. I made the point that None was appropriate in this case because the sentinel wasn’t necessary given a more sane structuring of the DS. But you’re right that’s better general advice. – Bailey Parker Jul 15 at 19:38

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.