## 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.

Pages: 1 2 3

### 5 Responses to “Telephone Lookup”

1. mike said

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

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)

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 len(database[input_number]) > 1:
print "Potential matches to your query " + str(database[input_number])
else:
print "Match found! " + str(database[input_number])
else:
print "No matches found"
```
2. Daniel said

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))```
3. simon said

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)))
(else (display "Ambiguous reference: ") (display (map cdr res))))
(newline))

(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"))))
```
4. slabounty said

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.

5. Josh said

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'
}

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):
return int(sig)

def db_get(sig):
results = db.get(sig)
if not results:
elif len(results) > 1:
print "Multiple records match signature %d:" % sig
for r, i in enumerate(results):
print "%d. %s" % (i+1, r)
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, record)
break
except:
else:
record = results
print "Name: %s\nNumber: %d\n\n" % (record, record)

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',