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

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 627 other followers

%d bloggers like this: