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.
All code is now hosted in a github repo codecamp-2007-puzzle. I will post the other solutions as permission is granted.
