With the advent of predictive text, it's surprising how few keypresses are needed to produce a short text message. In this kata we code a simple implementation of predictive text and use it to encode and decode text messages. For simplicity in this kata:
- All messages to be encoded contain only lower-case alphabetic characters and spaces (no digits, punctuation, line-feeds, etc.).
- Words are separated by single spaces.
Our predictive text algorithm uses a preloaded list, dictionary, of approximately 1200 frequently used English words, all in lower case, no hyphens or apostrophes. It starts like this:
dictionary = ["the","a","is","of","and","to","in","you","that","it","he","for","was","on", ...]
The algorithm is described below by imagining how a user would press the phone keypad to enter their message:
- The user enters their message one word at a time.
- Words which are not in the dictionary must be keyed in full (including a final space character unless the end of the message has been reached).
- After each keypress, the algorithm offers the user a selection of up to three dictionary words, any of which may be selected by user keying
1, 2, or 3.
- At the start of the message, or after a word has been completed, the selection of words is the first three words from the dictionary:
"the" "a" "is".
- At any other point during the encode/decode process, the selection of words is the first three words from the dictionary which match with the characters already entered in the current word.
- Whenever the user can see that the complete current word is displayed in the selection of words, the user selects the word by entering
1, 2 or 3. Otherwise the user continues entering the current word until it appears in the selection or until the word is completed by the user entering a space character.
Encode Example:
Encode the message "that was incredibly simple"
original message | word selection | encoded message
-----------------------------|---------------------------------------|-------------------------
"" | "the" "a" "is" | ""
"t" | "the" "to" "that" | "t"
SELECT THIRD WORD ---------------------------------^^^^
"that " | "the" "a" "is" | "t3"
"that w" | "was" "with" "what" | "t3w"
SELECT FIRST WORD -------^^^
"that was " | "the" "a" "is" | "t3w1"
"that was i" | "is" "in" "it" | "t3w1i"
"that was in" | "in" "into" "inside" | "t3w1in"
"that was inc" | "include" "inch" "increase" | "t3w1inc"
"that was incr" | "increase" "incredible" "" | "t3w1incr"
"that was incre" | "incredible" "" "" | "t3w1incre"
"that was incred" | "incredible" "" "" | "t3w1incred"
"that was incredi" | "incredible" "" "" | "t3w1incredi"
"that was incredib" | "incredible" "" "" | "t3w1incredib"
"that was incredibl" | "incredible" "" "" | "t3w1incredibl"
"that was incredibly" | "" "" "" | "t3w1incredibly"
"that was incredibly " | "the" "a" "is" | "t3w1incredibly "
"that was incredibly s" | "said" "she" "some" | "t3w1incredibly s"
"that was incredibly si" | "side" "since" "six" | "t3w1incredibly si"
"that was incredibly sim" | "simple" "similar" "" | "t3w1incredibly sim"
SELECT FIRST WORD -------^^^
"that was incredibly simple" | "the" "a" "is" | "t3w1incredibly sim1"
Encoded message: "t3w1incredibly sim1"
Decoding
The process for decoding a valid encoded message is almost the same as the encode process. Simply imagine the user entering the encoded message on their phone:
- As the user enters the characters of the encoded message, the characters are copied to the ddecoded message and the word selection is presented.
- Whenever the user enters
1, 2 or 3 the current word of the decoded message is replaced by the selected word.
Decode Example:
Encode the message "t3w1simply incr2"
encoded message | word selection | decoded message
-------------------------|-------------------------------------|--------------------------------
"" | "the" "a" "is" | ""
"t" | "the" "to" "that" | "t"
"t3" | "the" "a" "is" | "that "
"t3w" | "was" "with" "what" | "that w"
"t3w1" | "the" "a" "is" | "that was "
"t3w1s" | "said" "she" "some" | "that was s"
"t3w1si" | "side" "since" "six" | "that was si"
"t3w1sim" | "simple" "similar" "" | "that was sim"
"t3w1simp" | "simple" "" "" | "that was simp"
"t3w1simpl" | "simple" "" "" | "that was simpl"
"t3w1simply" | "" "" "" | "that was simply"
"t3w1simply " | "the" "a" "is" | "that was simply "
"t3w1simply i" | "is" "in" "it" | "that was simply i"
"t3w1simply in" | "in" "into" "inside" | "that was simply in"
"t3w1simply inc" | "include" "inch" "increase" | "that was simply inc"
"t3w1simply incr" | "increase" "incredible" "" | "that was simply incr"
"t3w1simply incr2" | "the" "a" "is" | "that was simply incredible"
Decoded message: "that was simply incredible"
The task:
Write the functions encode and decode as follows:
encode takes a lower-case string (of alphabetic words separated by spaces) and returns a lower-case string (including spaces and digits) encoded as described above.
decode takes a lower-case string (of alphabetic characters, digits and spaces) and returns a lower-case string of lower-case alphabetic words, separated by spaces, decoded as described above.
All inputs will be valid.
Message size: between 2 and 50 words
Word size: between 1 and 20 characters
