T9 Titans

Computer Science Level 5

Old cellphones did not used to have QWERTY keyboards. So, typing text was by pressing numeric keys: 

1
2
3
4
5
6
7
8
9
 
1 anything else
2 abc
3 def
4 ghi
5 jkl
6 mno
7 pqrs
8 tuv
9 wxyz

There was something called a T9 predictor which allowed the user to express a word by pressing corresponding keys just once. For example, if the user typed in 274554268 , the predictor would predict Brilliant .

Indeed, it is possible that there are two words which can be represented using the same sequence of digits. In this case, the user could switch between them at his discretion.

What is the sequence of digits for which there are largest number of clashes, if all the words are from this dictionary ?


The answer is 22737.

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

The best way to solve this problem as far as I know is to use an associative array , or what is called a dictionary in Python.

The toT9 is simple to code up: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
def toT9(s):
    num = ""
    for l in s:
        if l in "abc":
            num += "2"
        elif l in "def":
            num += "3"
        elif l in "ghi":
            num += "4"
        elif l in "jkl":
            num += "5"
        elif l in "mno":
            num += "6"
        elif l in "pqrs":
            num += "7"
        elif l in "tuv":
            num += "8"
        elif l in "wxyz":
            num += "9"
        else:
            num += "0"
    return int(num)

Then, we load the file and sort create the frequency distribution table: 

1
2
3
4
5
6
7
8
9
 
f = open("t9Dictionary")
words = f.read().split('\n')
frequencyTable = {}
for word in words:
    num = toT9(word)
    if num in frequencyTable:
        frequencyTable[num] += 1
    else:
        frequencyTable[num] = 1

To extract the entry with the maximum number of clashes, we do the following: 

1
 
list(sorted(frequencyTable, key=frequencyTable.get, reverse=True))[0]

That gives us 22737 . It has 12 clashes.

In fact, these 12 words are: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
 
acres
bards
barer
bares
barfs
baser
bases
caper
capes
cards
cares
cases

4 Helpful 0 Interesting 0 Brilliant 0 Confused

What are the 12 words, out of curiosity?

Eli Ross Staff - 4 years, 7 months ago

Log in to reply

That is a nice question. I added that as a footnote to the solution.

Agnishom Chattopadhyay - 4 years, 7 months ago

'acres', 'bards', 'barer', 'bares', 'barfs', 'baser', 'bases', 'caper', 'capes', 'cards', 'cares', 'cases'

Nikola Staykov - 1 year, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...