#StackBounty: #python Phone call routing cost checker

Bounty: 50

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 tradeoffs 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')]


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.