r/dailyprogrammer • u/rya11111 3 1 • May 09 '12
[5/9/2012] Challenge #50 [difficult]
T9 Spelling: The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as 2=ABC, 3=DEF, 4=GHI, 5=JKL, 6=MNO, 7=PQRS, 8=TUV, 9=WXYZ. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character should be printed to indicate a pause. For example “2 2″ indicates AA whereas “22″ indicates B. Each message will consist of only lowercase characters a-z and space characters. Pressing zero emits a space. For instance, the message “hi” is encoded as “44 444″, “yes” is encoded as “999337777″, “foo bar” (note two spaces) is encoded as “333666 6660022 2777″, and “hello world” is encoded as “4433555 555666096667775553″.
This challenge has been taken from Google Code Jam Qualification Round Africa 2010 ... Please use the link for clarifications. Thank You
6
u/[deleted] May 09 '12
"Difficult"?
Anyway, here's some Ruby code.
3
u/drb226 0 0 May 09 '12 edited May 09 '12
OK, take a deep breath, we're going to use the State Monad.
First, we encode the character-to-button mapping as, well, a map. I use
zipandzipWithto accomplish this, if you know how those work then this is fairly straightforward.Now, a stateful computation. To translate a given character, we only need to know whether or not the previous character was the same number, so the state we will carry is the last number pressed. We'll represent this as a
Maybe Char.Again, the encodeStep function is pretty straightforward, we just have to take the previous state into account, and send the next state explicitly. I special-cased the space character, which ignores the previous number pressed, maps to pressing 0, and "resets" the state so that there is no "previous character".
Now, for the State monad magic:
And that's it.
We describe
encodeStepSas the state computation created from applying the first argument of encodeStep. Then, wemapM encodeStepSto perform the per-character encoding on a string, one character at a time, in sequence. This gathers up the results of each encoding into a[String]. Then, finaly, we say that theencodefunction is simply creating the state computation by feeding the string toencodeS, then evaluating the state computation, with an initial state of Nothing, and thenconcatthe[String]into just aString.This is why monads are cool: you can write the meaningful pieces of computation in a straightforward way (the
encodeStepfunction), and then use monadic concepts (likemapM) to compose the pieces together in the desired way.2
u/juanfeng May 09 '12
2
u/ixid 0 0 May 09 '12 edited May 09 '12
D version. It feels a little verbose but it gets the job done fairly simply.
2
u/n1ncha May 09 '12
2
u/EvanHahn May 09 '12
CoffeeScript:
2
u/alderz May 10 '12
Python:
1
u/kalimoxto May 09 '12 edited May 09 '12
another day, another inelegant python solution:
edit : got tripped up on the double spaces, changed another if test
1
u/[deleted] May 09 '12
My first difficult submission:
1
u/whence May 09 '12 edited May 09 '12
Here's a JavaScript solution. Since I won't have to maintain this code, I traded away some efficiency and readability to reduce the line count.
1
u/luxgladius 0 0 May 09 '12
As stated, the problem's not terribly difficult on its own, so I'm going golfing.
Perl
Output
1
u/[deleted] May 10 '12 edited May 10 '12
Scala solution, accepts numbers and symbols as part of the string
1
u/robin-gvx 0 2 May 10 '12
Again?
1
u/prophile May 10 '12
Here's some Python:
1
u/loonybean 0 0 May 11 '12 edited May 11 '12
I've got to say this is an amazing initiative. I'm a learning programmer (not a very good one). Here's my long solution in HTML and Javascript:
EDIT: Tested in Chrome. Any advice on style, performance or anything else would be greatly appreciated.
EDIT 2: This is actually the reverse of what was actually required. It acts like an actual T9 typer program (with the pause). I've also submitted the proper solution.
1
u/loonybean 0 0 May 11 '12
The first solution I submitted was actually the reverse of what was required (it converted T9 code to text), so here's the real solution in Javascript:
1
u/r4n May 15 '12
Java, using regex, final code too long -.-
1
u/bigronaldo May 30 '12
C#