Code Camp Puzzle Reviewed

So the puzzle for the code camp was to decode the Morse Code message:

Message Received – Decode Required

The following transmission was received from General Gates:

.-.-...-..-.-.------.--.....-...--.---.-.------...--------.-..---.--...-.---.-..--.-.-.....-.---.-..-----.-.--.-....-..-.........

You must decode this to find the hidden message. Unfortunately, the message was damaged in transmission and all the spaces between the words were lost. However, we do know that only the following letters are in the message:

A .-  B -... C -.-.  D -..  E .  F ..-.  G --.  H ....  
I ..  J .---  K -.-  L .-..  M --N -.  O ---  P .--.  
Q --.-  R .-.  S ... T -  U ..-  V ...-  W .--  X -..-  
Y -.--  Z --..

We are also certain that the message only contains words in the standard military dictionary, located here. The are only 10 words in the message, five letter T’s and four letter E’s.

We received six solutions, one was from a non-attendee, and another was “lost” in the Ether, while the DNUG mailing list server was inactive over the weekend. So we had four solutions on the day of the draw.

The most abstract solution was a genetic algorithm submitted by Tim Schurr. It built 100 partial text’s, then for 100 iterations it does light mutation and replaces each solution when the new evaluates better. Then each 100th iteration the solutions are ranked and the top 50% are heavily mutated, over top of the bottom. around 100,000 generations were required to solve the puzzle. It was the only solution to use a GUI over the console, with progress bar and every thing. If the solution was not found, then the best 30 solutions were shown. Giving an output like this:

ALL TROOPS LAY -.-.----- BOOT CAMP FOR A TECHNOLOGY REFRESH
ALL TROOPS REPORT MOST TOOL OWE IT .---.-..- TECHNOLOGY REFRESH
ALL TROOPS REPORT TONE ATOM KIT MADE -.---.-..- TECHNOLOGY REFRESH
ALL TROOPS REPORT TONE ATOM CAT KNEE -.---.-..- TECHNOLOGY REFRESH

Very cool.

The next solution of note worthiness was Simon Green’s. Simon built a console application, but he pimped it out with multi-coloured fonts *Bling*. Simon’s solution built a tree of all the words that could be formed at each step along the Morse code. It then built a tree of possible solutions, which are then iterated over with via a massive LINQ expression using a set of Cursor like objects. He explained it to me many times, and I’m still not sure I’m doing it justice. As part of the same solution he had a classic backtracking search that could be interrupted and you then could manually select through the options at each word, this mode could then resume searching. All and all a very complete solution. Simon went on to win the Zune via the magic of a name draw.

Liam Clarke-Hutchinson’s solution was done in F#, which I’ve not used, but reading the code it seems to do stuff. I can follow code, but getting a bigger picture is beyond me right now, but anyhow, it solves the problem. And I will have to learn how it does it, latter.

Andrew Sewell’s solution was a C# 2.0 solution. Andrew builds a dictionary of all input words, and stores the matching Morse code result for the word. He then does back tracking via recursive object creations to iterate across each word in the dictionary cloning the current object for each match. He handles the multiple solutions by collecting solutions in a container.

Andrew McMillan’s solution also builds a dictionary of text/encoded objects with the ‘T’ and ‘E’ constraints marked in each object. It then backtracks via recursion matching each word in the dictionary. Unfortunately, his email was delayed in the Ether, so was not in the draw. I’m feeling pretty stink about this as we had such a low submission count that he stood a chance of winning.

My solution, builds a Radix Tree (a n-tree (and in this case a binary-tree)) of the Morse code for each word in the input dictionary. Each text word was added to the tree where it was “formed” in Morse code. I then used IEnumerable<>’s to to step down the tree following the code at the current location returning all words attached to each node traversed in the tree. I then had a higher level IEnumerable<> that did the recursion applying the letter and word count constraints. This meant that I could loop across the solutions as they were found.

My code is here, Tim’s code is here, Liam’s code is here, Andrew Sewell’s code is here, and I will post the other solutions as permission is granted.

5 thoughts on “Code Camp Puzzle Reviewed”

  1. Hey Simeon, Good solution and fast too. Was a good weekend, and thanks for the lift to the airport! Cheers, Al

  2. Cheer Alistair, I had a great time over the weekend also. NP on the lift, it’s not like I had to pay a fare to get here ;-)

    Any questions on the code just ask.

  3. I found 5 legitimate messages that met all the criteria. Note that “good English” was not a criterion. ;-)

    ALL TROOPS REPORT TO BOOT CAMP FOR A TECHNOLOGY REFRESH
    ALL TROOPS REPORT TONE ATOM CAMP FOR A TECHNOLOGY REFRESH
    ALL TROOPS REPORT MOST TOO LOAN FOR A TECHNOLOGY REFRESH
    ALL TROOPS REPORT TO BOOM LOAN FOR A TECHNOLOGY REFRESH
    ALL TROOPS REPORT MOST TOOL OWE FOR A TECHNOLOGY REFRESH

    The main thing I learnt from doing this was to read all the instructions before beginning! (I was busy, and not going to Code Camp, so I didn’t start until after it was over. And I didn’t want to read how anyone else had solved it. So I avoided rereading the spec — missing the letter and word limitations. And even the dictionary of allowed words. So my original solution even called the MS Word spellchecker to test for valid words. Plus some other optimisations to skip obviously wrong words.

    All in all, I really enjoyed the challenge.

  4. I’m very glad you enjoyed the puzzle.

    I’m not sure that there are five solutions that match the criteria, because your last solution “ALL TROOPS REPORT MOST TOOL OWE FOR A TECHNOLOGY REFRESH” has five E’s yet, the criteria said only four.

    Using Word, sounds like a clever solution albeit slow.

Comments are closed.