Telephone Lookup
July 23, 2013
In the early days of Unix, Mike Lesk wrote a directory-assistance program that allowed users to input a name using the numeric keypad on a telephone and get a telephone number in return. The program worked by “signing” each name with its telephonic equivalent, then storing the signatures in a database. This scheme makes collisions possible, but in practice collisions are rare, and when they do happen the user is prompted for additional information.
Your task is to write a program that takes a name and returns a telephone number; a database is provided on the next page. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Here is my python solution, I didn’t try running it but I believe it is mostly correct:
def store_name(entry, database): signature = 0 surname = entry[0] int phone_num = 2 #Loop over all the characters to create the signature for i in range(0, len(surname)): place = 10 ^ ((len(surname) - 1) - i) #Figure out the correct digit (I should have used an array here like it suggested in the authors solution) if surname[i] == 'a' || surname[i] == 'b' || surname[i] == 'c': digit = 2 else if surname[i] == 'd' || surname[i] == 'e' || surname[i] == 'f': digit = 3 else if surname[i] == 'g' || surname[i] == 'h' || surname[i] == 'i': digit = 4 else if surname[i] == 'k' || surname[i] == 'l' || surname[i] == 'm': digit = 5 else if surname[i] == 'o' || surname[i] == 'p' || surname[i] == 'q': digit = 6 else if surname[i] == 'r' || surname[i] == 's' || surname[i] == 't': digit = 7 else if surname[i] == 'u' || surname[i] == 'v' || surname[i] == 'w': digit = 8 else if surname[i] == 'y' || surname[i] == 'x' || surname[i] == 'z': digit = 9 signature = signature + (digit * place) if database.haskey(signature): database[signature].append(entry) else: database[signature] = [entry] def create_signature_database(contacts_list, database): for entry in contacts_list: store_name(entry, database) def phone_lookup(number): database database = {} contacts_list = [('surname1', '613612333000')] create_signature_database(contacts_list, database) input_number = get_input_from_user() if database.haskey(input_number): if len(database[input_number]) > 1: print "Potential matches to your query " + str(database[input_number]) else: print "Match found! " + str(database[input_number][0]) else: print "No matches found"The problem says “Your task is to write a program that takes a name and returns a telephone number”. However, it seemed more fitting to write a program that takes a signature and returns a telephone number, as opposed to just taking a name. If the program took the name as input, then there would seemingly be no need for the name’s signature.
Here’s a Common Lisp program that takes a name signature and returns associated names and phone numbers. The database only contains a few names, including an example collision.
(defun code (char) "Returns the telephone digit for characters a-zA-Z" (let ((map #(2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 9 9 9 9))) (aref map (- (char-code (char-upcase char)) 65)))) (defun signature (name) "Returns the signature of a name as an integer" (parse-integer (map 'string #'(lambda (char) (char (write-to-string (code char)) 0)) name))) (defun make-database () "Create a hash table that maps signatures to name/numbers" (let ((table (make-hash-table))) (dolist (name-number '(("SMITH" 555-0001) ("DAVIS" 555-0002) ("ANDERSON" 555-0003) ("SAM" 555-0004) ("PAM" 555-0005))) (push name-number (gethash (signature (first name-number)) table))) table)) (defparameter *database* (make-database)) (defun lookup (signature) "Given a signature, return a list of possible name/numbers" (dolist (pair (gethash signature *database*)) (format t "~a: ~a~%" (first pair) (second pair)))) (defun example () (lookup 32847))I have a feeling a lot could be simplified, but it’s quite late already.
This code runs on chicken scheme, where srfi-1 needs to be included explicitly, and srfi-26 (cut, cute) isprovided by default.
;; (run-tests) runs included test suite ;; (main) prompts for numeric input, returns matched name(s) or "Not found" message (load "telephone-db.scm") ; a list of uppercase strings, i.e. '("SMITH" "HILL" "GRANT") (use srfi-1) (define (int->telephone c) (cond ((and (>= c 65) (<= c 67)) 2) ((<= c 70) 3) ((<= c 73) 4) ((<= c 76) 5) ((<= c 79) 6) ((<= c 83) 7) ((<= c 86) 8) ((<= c 90) 9) (else (error "unsupported character")))) (define normalize (compose int->telephone char->integer char-upcase)) (define hash-name (compose (cut map normalize <>) string->list)) (define hash-db (map (lambda(n)(cons (hash-name n) n)) raw-telephone-db)) (define (find-phones p) (filter (lambda(el) (list= eq? (car el) p)) hash-db)) (define (find-phone n) (find-phones (map (cute - <> 48) (map char->integer (string->list n))))) (define (print-result res) (cond ((= 1 (length res)) (display "Found: ") (display (cdar res))) ((= 0 (length res)) (display "Not found")) (else (display "Ambiguous reference: ") (display (map cdr res)))) (newline)) (define (main) (print-result (find-phone (read-line)))(exit)) (define (run-tests) (let ((cases (list (equal? (cdar (find-phone "76484")) "SMITH") (= (length (find-phone "4455")) 2) (= (length (find-phone "888888888")) 0)))) (if (not (every (cute eq? #t <>) cases)) (begin (display cases) (newline)) (display "OK\n"))))Here’s a ruby version …
names = %w[ SMITH ROSE POPE ROSA SOSA ] def name_to_number(name) mapping = { "A" => "2", "B" => "2", "C" => "2", "D" => "3", "E" => "2", "F" => "2", "G" => "4", "H" => "4", "I" => "4", "J" => "5", "K" => "5", "L" => "5", "M" => "6", "N" => "6", "O" => "6", "P" => "7", "Q" => "7", "R" => "7", "S" => "7", "T" => "8", "U" => "8", "V" => "8", "W" => "9", "X" => "9", "Y" => "9", "Z" => "9" } number = "" name.each_char { |c| number << mapping[c] } number end lookup_names = names.inject({}) { |lookup_names, name| (lookup_names[name_to_number(name)] ||= []) << name; lookup_names } puts "76484 = #{lookup_names['76484']}" puts "7672 = #{lookup_names['7672']}"I just used a few of the name to show the technique. The only slightly tricky part is the inject. We need to initialize it to an empty hash and then when we add the name to the hash if there’s nothing currently there, we initialize with an empty array ( the ||= [] piece).
I’ve missed doing these … I’m hoping to get back into them a bit.
A Python solution:
import string db = {} numpad = {'a':'2', 'b':'2', 'c':'2', 'd':'3', 'e':'3', 'f':'3', 'g':'4', 'h':'4', 'i':'4', 'j':'5', 'k':'5', 'l':'5', 'm':'6', 'n':'6', 'o':'6', 'p':'7', 'q':'7', 'r':'7', 's':'7', 't':'8', 'u':'8', 'v':'8', 'w':'9', 'x':'9', 'y':'9', 'z':'9' } def db_add(name, tel): sig = sign_name(name) if sig in db: db[sig].append((name, tel)) else: db[sig] = [(name, tel)] def sign_name(name): sig = '' for l in string.lower(name): sig += numpad[l] return int(sig) def db_get(sig): results = db.get(sig) if not results: print "No results found" elif len(results) > 1: print "Multiple records match signature %d:" % sig for r, i in enumerate(results): print "%d. %s" % (i+1, r[0]) print "Enter number of desired choice:" while True: s = raw_input("--> ") try: record = results[int(s)-1] print "Name: %s\nNumber: %d\n\n" % (record[0], record[1]) break except: print "Please enter a number:" else: record = results[0] print "Name: %s\nNumber: %d\n\n" % (record[0], record[1]) names=[ 'SMITH','JOHNSON','WILLIAMS','JONES','BROWN', 'DAVIS','MILLER','WILSON','MOORE','TAYLOR', 'ANDERSON','THOMAS','JACKSON','WHITE','HARRIS', 'MARTIN','THOMPSON','GARCIA','MARTINEZ','ROBINSON', 'CLARK','RODRIGUEZ','LEWIS','LEE','WALKER', 'HALL','ALLEN','YOUNG','HERNANDEZ','KING', 'WRIGHT','LOPEZ','HILL','SCOTT','GREEN', 'ADAMS','BAKER','GONZALEZ','NELSON','CARTER' ] def test(): from random import randint for name in names: db_add(name, randint(1000000, 9999999)) db_get(46692539) db_get(427747) db_get(111)