### James S. Plank

Fri Sep 2 01:04:04 EDT 2016
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.