Telephone Lookup

July 23, 2013

We begin by pairing the names with their rank, which we will use in place of the telephone number:

(define surnames (map list (map string-upcase (map symbol->string '( SMITH JOHNSON ... VANG))) (range 1 1001)))

The code that signs a name just looks up each character and returns a list:

(define (sign name) ; telephone keyboard A B C D E F G H I J K L M N O P Q R S T U V W X Y Z (define keys (vector 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)) (define (lookup c) (vector-ref keys (- (char->integer c) 65))) (map lookup (string->list name)))

To create the database, we initialize a hash table and add each name/rank pair to it:

(define t (make-hash)) (do ((ss surnames (cdr ss))) ((null? ss)) (set! t (t 'update (sign (caar ss)) (lambda (k v) (cons (car ss) v)) (list (car ss)))))

Then looking up a name by its telephone-keypad signature is simple:

(define (lookup name) (cdr (t 'lookup (sign name))))

We used range and string-upcase from the Standard Prelude and our new hash tables from a recent exercise. You can run the program at http://programmingpraxis.codepad.org/ocKGx9nn.

Collisions aren’t a problem, as we suggested earlier. Out of a thousand surnames, there are only 19 pairs that have the same signature, and one triple: BARR, BASS, CARR. Lesk would have had even fewer collisions, because he added a first initial that we don’t have here; he reported only about 0.2% collisions. (I’m quoting from Column 2, Exercise 6 of Jon Bentley’s book Programming Pearls.)

Posted by programmingpraxis

Filed in Exercises

5 Comments »

5 Responses to “Telephone Lookup”

mike said

August 2, 2013 at 6:02 PM

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"

Daniel said

August 3, 2013 at 4:42 PM

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))

simon said

August 8, 2013 at 10:13 PM

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"))))

slabounty said

August 11, 2013 at 11:16 PM

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.

Josh said

September 20, 2013 at 2:08 PM

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)

Programming Praxis