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

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)

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

Cancel

Connecting to %s

Programming Praxis