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.

About these ads

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[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"
    
  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)))
            ((= 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"))))
    
  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'
    		  }
    
    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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 598 other followers

%d bloggers like this: