Telephone Lookup

July 23, 2013

Here are the one thousand most common surnames in the United States, from http://names.mongabay.com/most_common_surnames.htm:

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
MITCHELL       PEREZ          ROBERTS        TURNER         PHILLIPS
CAMPBELL       PARKER         EVANS          EDWARDS        COLLINS
STEWART        SANCHEZ        MORRIS         ROGERS         REED
COOK           MORGAN         BELL           MURPHY         BAILEY
RIVERA         COOPER         RICHARDSON     COX            HOWARD
WARD           TORRES         PETERSON       GRAY           RAMIREZ
JAMES          WATSON         BROOKS         KELLY          SANDERS
PRICE          BENNETT        WOOD           BARNES         ROSS
HENDERSON      COLEMAN        JENKINS        PERRY          POWELL
LONG           PATTERSON      HUGHES         FLORES         WASHINGTON
BUTLER         SIMMONS        FOSTER         GONZALES       BRYANT
ALEXANDER      RUSSELL        GRIFFIN        DIAZ           HAYES
MYERS          FORD           HAMILTON       GRAHAM         SULLIVAN
WALLACE        WOODS          COLE           WEST           JORDAN
OWENS          REYNOLDS       FISHER         ELLIS          HARRISON
GIBSON         MCDONALD       CRUZ           MARSHALL       ORTIZ
GOMEZ          MURRAY         FREEMAN        WELLS          WEBB
SIMPSON        STEVENS        TUCKER         PORTER         HUNTER
HICKS          CRAWFORD       HENRY          BOYD           MASON
MORALES        KENNEDY        WARREN         DIXON          RAMOS
REYES          BURNS          GORDON         SHAW           HOLMES
RICE           ROBERTSON      HUNT           BLACK          DANIELS
PALMER         MILLS          NICHOLS        GRANT          KNIGHT
FERGUSON       ROSE           STONE          HAWKINS        DUNN
PERKINS        HUDSON         SPENCER        GARDNER        STEPHENS
PAYNE          PIERCE         BERRY          MATTHEWS       ARNOLD
WAGNER         WILLIS         RAY            WATKINS        OLSON
CARROLL        DUNCAN         SNYDER         HART           CUNNINGHAM
BRADLEY        LANE           ANDREWS        RUIZ           HARPER
FOX            RILEY          ARMSTRONG      CARPENTER      WEAVER
GREENE         LAWRENCE       ELLIOTT        CHAVEZ         SIMS
AUSTIN         PETERS         KELLEY         FRANKLIN       LAWSON
FIELDS         GUTIERREZ      RYAN           SCHMIDT        CARR
VASQUEZ        CASTILLO       WHEELER        CHAPMAN        OLIVER
MONTGOMERY     RICHARDS       WILLIAMSON     JOHNSTON       BANKS
MEYER          BISHOP         MCCOY          HOWELL         ALVAREZ
MORRISON       HANSEN         FERNANDEZ      GARZA          HARVEY
LITTLE         BURTON         STANLEY        NGUYEN         GEORGE
JACOBS         REID           KIM            FULLER         LYNCH
DEAN           GILBERT        GARRETT        ROMERO         WELCH
LARSON         FRAZIER        BURKE          HANSON         DAY
MENDOZA        MORENO         BOWMAN         MEDINA         FOWLER
BREWER         HOFFMAN        CARLSON        SILVA          PEARSON
HOLLAND        DOUGLAS        FLEMING        JENSEN         VARGAS
BYRD           DAVIDSON       HOPKINS        MAY            TERRY
HERRERA        WADE           SOTO           WALTERS        CURTIS
NEAL           CALDWELL       LOWE           JENNINGS       BARNETT
GRAVES         JIMENEZ        HORTON         SHELTON        BARRETT
OBRIEN         CASTRO         SUTTON         GREGORY        MCKINNEY
LUCAS          MILES          CRAIG          RODRIQUEZ      CHAMBERS
HOLT           LAMBERT        FLETCHER       WATTS          BATES
HALE           RHODES         PENA           BECK           NEWMAN
HAYNES         MCDANIEL       MENDEZ         BUSH           VAUGHN
PARKS          DAWSON         SANTIAGO       NORRIS         HARDY
LOVE           STEELE         CURRY          POWERS         SCHULTZ
BARKER         GUZMAN         PAGE           MUNOZ          BALL
KELLER         CHANDLER       WEBER          LEONARD        WALSH
LYONS          RAMSEY         WOLFE          SCHNEIDER      MULLINS
BENSON         SHARP          BOWEN          DANIEL         BARBER
CUMMINGS       HINES          BALDWIN        GRIFFITH       VALDEZ
HUBBARD        SALAZAR        REEVES         WARNER         STEVENSON
BURGESS        SANTOS         TATE           CROSS          GARNER
MANN           MACK           MOSS           THORNTON       DENNIS
MCGEE          FARMER         DELGADO        AGUILAR        VEGA
GLOVER         MANNING        COHEN          HARMON         RODGERS
ROBBINS        NEWTON         TODD           BLAIR          HIGGINS
INGRAM         REESE          CANNON         STRICKLAND     TOWNSEND
POTTER         GOODWIN        WALTON         ROWE           HAMPTON
ORTEGA         PATTON         SWANSON        JOSEPH         FRANCIS
GOODMAN        MALDONADO      YATES          BECKER         ERICKSON
HODGES         RIOS           CONNER         ADKINS         WEBSTER
NORMAN         MALONE         HAMMOND        FLOWERS        COBB
MOODY          QUINN          BLAKE          MAXWELL        POPE
FLOYD          OSBORNE        PAUL           MCCARTHY       GUERRERO
LINDSEY        ESTRADA        SANDOVAL       GIBBS          TYLER
GROSS          FITZGERALD     STOKES         DOYLE          SHERMAN
SAUNDERS       WISE           COLON          GILL           ALVARADO
GREER          PADILLA        SIMON          WATERS         NUNEZ
BALLARD        SCHWARTZ       MCBRIDE        HOUSTON        CHRISTENSEN
KLEIN          PRATT          BRIGGS         PARSONS        MCLAUGHLIN
ZIMMERMAN      FRENCH         BUCHANAN       MORAN          COPELAND
ROY            PITTMAN        BRADY          MCCORMICK      HOLLOWAY
BROCK          POOLE          FRANK          LOGAN          OWEN
BASS           MARSH          DRAKE          WONG           JEFFERSON
PARK           MORTON         ABBOTT         SPARKS         PATRICK
NORTON         HUFF           CLAYTON        MASSEY         LLOYD
FIGUEROA       CARSON         BOWERS         ROBERSON       BARTON
TRAN           LAMB           HARRINGTON     CASEY          BOONE
CORTEZ         CLARKE         MATHIS         SINGLETON      WILKINS
CAIN           BRYAN          UNDERWOOD      HOGAN          MCKENZIE
COLLIER        LUNA           PHELPS         MCGUIRE        ALLISON
BRIDGES        WILKERSON      NASH           SUMMERS        ATKINS
WILCOX         PITTS          CONLEY         MARQUEZ        BURNETT
RICHARD        COCHRAN        CHASE          DAVENPORT      HOOD
GATES          CLAY           AYALA          SAWYER         ROMAN
VAZQUEZ        DICKERSON      HODGE          ACOSTA         FLYNN
ESPINOZA       NICHOLSON      MONROE         WOLF           MORROW
KIRK           RANDALL        ANTHONY        WHITAKER       OCONNOR
SKINNER        WARE           MOLINA         KIRBY          HUFFMAN
BRADFORD       CHARLES        GILMORE        DOMINGUEZ      ONEAL
BRUCE          LANG           COMBS          KRAMER         HEATH
HANCOCK        GALLAGHER      GAINES         SHAFFER        SHORT
WIGGINS        MATHEWS        MCCLAIN        FISCHER        WALL
SMALL          MELTON         HENSLEY        BOND           DYER
CAMERON        GRIMES         CONTRERAS      CHRISTIAN      WYATT
BAXTER         SNOW           MOSLEY         SHEPHERD       LARSEN
HOOVER         BEASLEY        GLENN          PETERSEN       WHITEHEAD
MEYERS         KEITH          GARRISON       VINCENT        SHIELDS
HORN           SAVAGE         OLSEN          SCHROEDER      HARTMAN
WOODARD        MUELLER        KEMP           DELEON         BOOTH
PATEL          CALHOUN        WILEY          EATON          CLINE
NAVARRO        HARRELL        LESTER         HUMPHREY       PARRISH
DURAN          HUTCHINSON     HESS           DORSEY         BULLOCK
ROBLES         BEARD          DALTON         AVILA          VANCE
RICH           BLACKWELL      YORK           JOHNS          BLANKENSHIP
TREVINO        SALINAS        CAMPOS         PRUITT         MOSES
CALLAHAN       GOLDEN         MONTOYA        HARDIN         GUERRA
MCDOWELL       CAREY          STAFFORD       GALLEGOS       HENSON
WILKINSON      BOOKER         MERRITT        MIRANDA        ATKINSON
ORR            DECKER         HOBBS          PRESTON        TANNER
KNOX           PACHECO        STEPHENSON     GLASS          ROJAS
SERRANO        MARKS          HICKMAN        ENGLISH        SWEENEY
STRONG         PRINCE         MCCLURE        CONWAY         WALTER
ROTH           MAYNARD        FARRELL        LOWERY         HURST
NIXON          WEISS          TRUJILLO       ELLISON        SLOAN
JUAREZ         WINTERS        MCLEAN         RANDOLPH       LEON
BOYER          VILLARREAL     MCCALL         GENTRY         CARRILLO
KENT           AYERS          LARA           SHANNON        SEXTON
PACE           HULL           LEBLANC        BROWNING       VELASQUEZ
LEACH          CHANG          HOUSE          SELLERS        HERRING
NOBLE          FOLEY          BARTLETT       MERCADO        LANDRY
DURHAM         WALLS          BARR           MCKEE          BAUER
RIVERS         EVERETT        BRADSHAW       PUGH           VELEZ
RUSH           ESTES          DODSON         MORSE          SHEPPARD
WEEKS          CAMACHO        BEAN           BARRON         LIVINGSTON
MIDDLETON      SPEARS         BRANCH         BLEVINS        CHEN
KERR           MCCONNELL      HATFIELD       HARDING        ASHLEY
SOLIS          HERMAN         FROST          GILES          BLACKBURN
WILLIAM        PENNINGTON     WOODWARD       FINLEY         MCINTOSH
KOCH           BEST           SOLOMON        MCCULLOUGH     DUDLEY
NOLAN          BLANCHARD      RIVAS          BRENNAN        MEJIA
KANE           BENTON         JOYCE          BUCKLEY        HALEY
VALENTINE      MADDOX         RUSSO          MCKNIGHT       BUCK
MOON           MCMILLAN       CROSBY         BERG           DOTSON
MAYS           ROACH          CHURCH         CHAN           RICHMOND
MEADOWS        FAULKNER       ONEILL         KNAPP          KLINE
BARRY          OCHOA          JACOBSON       GAY            AVERY
HENDRICKS      HORNE          SHEPARD        HEBERT         CHERRY
CARDENAS       MCINTYRE       WHITNEY        WALLER         HOLMAN
DONALDSON      CANTU          TERRELL        MORIN          GILLESPIE
FUENTES        TILLMAN        SANFORD        BENTLEY        PECK
KEY            SALAS          ROLLINS        GAMBLE         DICKSON
BATTLE         SANTANA        CABRERA        CERVANTES      HOWE
HINTON         HURLEY         SPENCE         ZAMORA         YANG
MCNEIL         SUAREZ         CASE           PETTY          GOULD
MCFARLAND      SAMPSON        CARVER         BRAY           ROSARIO
MACDONALD      STOUT          HESTER         MELENDEZ       DILLON
FARLEY         HOPPER         GALLOWAY       POTTS          BERNARD
JOYNER         STEIN          AGUIRRE        OSBORN         MERCER
BENDER         FRANCO         ROWLAND        SYKES          BENJAMIN
TRAVIS         PICKETT        CRANE          SEARS          MAYO
DUNLAP         HAYDEN         WILDER         MCKAY          COFFEY
MCCARTY        EWING          COOLEY         VAUGHAN        BONNER
COTTON         HOLDER         STARK          FERRELL        CANTRELL
FULTON         LYNN           LOTT           CALDERON       ROSA
POLLARD        HOOPER         BURCH          MULLEN         FRY
RIDDLE         LEVY           DAVID          DUKE           ODONNELL
GUY            MICHAEL        BRITT          FREDERICK      DAUGHERTY
BERGER         DILLARD        ALSTON         JARVIS         FRYE
RIGGS          CHANEY         ODOM           DUFFY          FITZPATRICK
VALENZUELA     MERRILL        MAYER          ALFORD         MCPHERSON
ACEVEDO        DONOVAN        BARRERA        ALBERT         COTE
REILLY         COMPTON        RAYMOND        MOONEY         MCGOWAN
CRAFT          CLEVELAND      CLEMONS        WYNN           NIELSEN
BAIRD          STANTON        SNIDER         ROSALES        BRIGHT
WITT           STUART         HAYS           HOLDEN         RUTLEDGE
KINNEY         CLEMENTS       CASTANEDA      SLATER         HAHN
EMERSON        CONRAD         BURKS          DELANEY        PATE
LANCASTER      SWEET          JUSTICE        TYSON          SHARPE
WHITFIELD      TALLEY         MACIAS         IRWIN          BURRIS
RATLIFF        MCCRAY         MADDEN         KAUFMAN        BEACH
GOFF           CASH           BOLTON         MCFADDEN       LEVINE
GOOD           BYERS          KIRKLAND       KIDD           WORKMAN
CARNEY         DALE           MCLEOD         HOLCOMB        ENGLAND
FINCH          HEAD           BURT           HENDRIX        SOSA
HANEY          FRANKS         SARGENT        NIEVES         DOWNS
RASMUSSEN      BIRD           HEWITT         LINDSAY        LE
FOREMAN        VALENCIA       ONEIL          DELACRUZ       VINSON
DEJESUS        HYDE           FORBES         GILLIAM        GUTHRIE
WOOTEN         HUBER          BARLOW         BOYLE          MCMAHON
BUCKNER        ROCHA          PUCKETT        LANGLEY        KNOWLES
COOKE          VELAZQUEZ      WHITLEY        NOEL           VANG

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

%d bloggers like this: