SRM 468, D1, 250-Pointer (T9)

James S. Plank

Fri Sep 2 01:04:04 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: April, 2010
Competitors who opened the problem: 705
Competitors who submitted a solution: 630
Number of correct solutions: 495
Accuracy (percentage correct vs those who opened): 70.21%
Average Correct Time: 43 minutes, 15 seconds.

This is a long problem writeup, but there are no tricks in it. I'm guessing that in 2010, the problem was more intuitive than it is in more modern times.

Back before Smart Phones took over the universe, cell phones had a gray and black screen, and 12 buttons laid out like their predecessor, non-cell phones. The 12 buttons were 0 through 9, plus '#' and '*'. Here's an example:

Sending text messages on these phones was a pain, but the cell phone manufacturers developed something called "T9" to make it easier - see https://en.wikipedia.org/wiki/T9_(predictive_text).

With T9, you would simply type the numeric keys that spell the word you want. Given the phone above, you could type "the" with "843" and "bad" with 223. After you typed your word, the T9 system would display the word that matched the keystrokes, and that their system thought was the most likely word for you to type. If there were multiple words that had the same keystrokes, you would press '#' to cycle through all of the words with the same keystrokes.

This topcoder problem has you implement the T9 functionality, but there are a few wrinkles:

The mapping of characters to digits is specified by the arguments to the problem.
When there are multiple words that map to the same sequence of characters, you cycle through them with the '#' characters alphabetically, rather than in some predictive order.
When you type '*', it is equal to typing 5 '#' characters.

In the topcoder problem, they give you a vector of strings that you concatenate together to create a string of keystrokes. You job is to use T9 to turn those keystrokes into words.

Your goal is to create a map, whose keys are the keystrokes you need for a word, and whose vals are vectors of the words that correspond to the keystrokes. Eventually, you will want the vectors to be sorted.

Let's use example two to illustrate. You are going to want a map with two keys: "223" and "843". Here are the keys and vals:

Key "223". Val: { "aad", "aae", "aaf", "acd", "ace", "acf", "bad" }.
Key "843". Val: { "the", "tie" }.

Once you have this map, you'll run through the keystroke string, and extract keystrokes that correspond to words. From those, you'll figure out what words to put in your final string.

We're going to build up a solution. You should do every step here, and then test to make sure you've gotten it done correctly.

Part 1: Mapping letters to numbers

First, you need to map each letter from 'a' to 'z' to its number on the keypad. You can do this with a map, or you can do it with an array of 'z'+1 elements, where you just use elements 'a' to 'z'. Print out the mapping. Here is my printout for each example.

Examples 0 through 4:

a maps to 2
b maps to 2
c maps to 2
d maps to 3
e maps to 3
f maps to 3
g maps to 4
h maps to 4
i maps to 4
j maps to 5
k maps to 5
l maps to 5
m maps to 6
n maps to 6
o maps to 6
p maps to 7
q maps to 7
r maps to 7
s maps to 7
t maps to 8
u maps to 8
v maps to 8
w maps to 9
x maps to 9
y maps to 9
z maps to 9

Example 5:

a maps to 4
b maps to 5
c maps to 5
d maps to 3
e maps to 3
f maps to 5
g maps to 5
h maps to 8
i maps to 8
j maps to 6
k maps to 6
l maps to 3
m maps to 9
n maps to 5
o maps to 4
p maps to 6
q maps to 2
r maps to 2
s maps to 7
t maps to 6
u maps to 4
v maps to 7
w maps to 7
x maps to 6
y maps to 4
z maps to 4

Part 2: Creating the keystroke strings that correspond to each word

Next, you need to create the keystroke strings for each word. You'll be using your mapping from the last part to do that. Print them out and double-check that they are correct:

Example 0:

Word bad = 223

Example 1:

Word the = 843
Word tie = 843

Example 2:

Word bad = 223
Word ace = 223
Word aad = 223
Word aae = 223
Word aaf = 223
Word acf = 223
Word acd = 223
Word the = 843
Word tie = 843

Example 3:

Word the = 843
Word tie = 843
Word bad = 223
Word ace = 223
Word aad = 223
Word aae = 223
Word aaf = 223
Word acf = 223
Word acd = 223

Example 4:

Word bad = 223
Word ace = 223
Word aad = 223
Word aae = 223
Word tie = 843
Word aaf = 223
Word acf = 223
Word acd = 223
Word the = 843

Example 5:

Word xktgmfmoqlmivm = 66659594239879
Word hmthr = 89682
Word tpjgmnmaremiwm = 66659594239879
Word tpjcmnmyrlmhvm = 66659594239879
Word xkpnmgmzqdmhsm = 66659594239879
Word wqopvvmiig = 7246779885
Word melbcbqeeg = 9335552335
Word jkxnmbmardmhwm = 66659594239879
Word kpxnmcmyqlmism = 66659594239879
Word wrztvsmhhf = 7246779885
Word srztssmiic = 7246779885
Word pxtgmfmyrdmhwm = 66659594239879
Word vqoxswmiin = 7246779885
Word wryksvmihb = 7246779885
Word ptjfmbmoremhvm = 66659594239879

Part 3: Creating the map with unsorted vectors

Now, you create the map that I describe above, with keystroke strings as keys, and vectors of dictionary words as vals. Don't bother sorting the vector yet. Print out the map, and double-check your answer:

Example 0:

Key 223: bad

Example 1:

Key 843: the tie

Example 2:

Key 223: bad ace aad aae aaf acf acd
Key 843: the tie

Example 3:

Key 223: bad ace aad aae aaf acf acd
Key 843: the tie

Example 4:

Key 223: bad ace aad aae aaf acf acd
Key 843: tie the

Example 5:

Key 66659594239879: xktgmfmoqlmivm tpjgmnmaremiwm tpjcmnmyrlmhvm xkpnmgmzqdmhsm jkxnmbmardmhwm kpxnmcmyqlmism pxtgmfmyrdmhwm ptjfmbmoremhvm
Key 7246779885: wqopvvmiig wrztvsmhhf srztssmiic vqoxswmiin wryksvmihb
Key 89682: hmthr
Key 9335552335: melbcbqeeg

Part 4: Sort the vectors

Use the sort() method from the algorithms library:

Example 0:

Key 223: bad

Example 1:

Key 843: the tie

Example 2:

Key 223: aad aae aaf acd ace acf bad
Key 843: the tie

Example 3:

Key 223: aad aae aaf acd ace acf bad
Key 843: the tie

Example 4:

Key 223: aad aae aaf acd ace acf bad
Key 843: the tie

Example 5:

Key 66659594239879: jkxnmbmardmhwm kpxnmcmyqlmism ptjfmbmoremhvm pxtgmfmyrdmhwm tpjcmnmyrlmhvm tpjgmnmaremiwm xkpnmgmzqdmhsm xktgmfmoqlmivm
Key 7246779885: srztssmiic vqoxswmiin wqopvvmiig wryksvmihb wrztvsmhhf
Key 89682: hmthr
Key 9335552335: melbcbqeeg

Part 5: Extract the keystrokes

Now, it's time to interpret the keystroke string. What I did was identify the strings and how many '#' signs there are (adding 5 for a '*'). And I identified the spaces. See if you can get your output to match mine here:

Example 0:

String = 223.  Number of '#': 0
Space
String = 223.  Number of '#': 0

Example 1:

Space
String = 843.  Number of '#': 1
Space
Space
Space
String = 843.  Number of '#': 1
Space
Space
Space

Example 2:

String = 223.  Number of '#': 1
Space
String = 223.  Number of '#': 6
Space
Space
String = 843.  Number of '#': 1
Space

Example 3:

String = 843.  Number of '#': 0
Space
Space
String = 223.  Number of '#': 1
Space
String = 223.  Number of '#': 6

Example 4:

String = 223.  Number of '#': 1
Space
String = 223.  Number of '#': 6

Example 5:

Space
Space
String = 7246779885.  Number of '#': 2
Space
Space
Space
Space
Space
Space
String = 89682.  Number of '#': 0
Space
Space
Space
Space
Space
String = 7246779885.  Number of '#': 2
Space
Space
Space
Space
String = 7246779885.  Number of '#': 1
Space
Space
Space
Space
String = 89682.  Number of '#': 0
Space
Space
Space
Space
String = 9335552335.  Number of '#': 0
Space
Space
String = 66659594239879.  Number of '#': 3
Space
Space
Space

Part 6: Create your return value

Now, use the key strings and '#' numbers to look up each of the proper strings in the map, and create the return string.

I am not posting a solution, because I often give this one in lab.