Inside F#

Brian's thoughts on F# and .NET

F# for puzzles (Morse code decoder)

Posted by Brian on August 26, 2010

At Microsoft (and around the Seattle area) there is a tradition of puzzle events: PuzzleHunt, Puzzle Safari, PuzzleDay, and so forth.  I always find these events really enjoyable.  There are a wide variety of creative puzzle types that require ingenuity to solve.  Automated tools, such as anagram solvers (where e.g. you type in a jumble of letters, and a list of all reasonable anagrams is output), are occasionally useful, but usually the puzzles are constructed so that humans need to do the majority of the solving and tools are of limited utility.
A hybrid tool, however, that lets humans apply smarts while letting the machine do the grunt-work, can be very useful.  For example, suppose I need to decode a Morse code string like
let toDecode = "......-...-..---.-----.-..-..-.."
In real life, there would be spacing to delimit letters and words, but in a puzzle event, you’re often on your own.  The nature of Morse Code means there’s about a million bazillion possible ways to decode that string into letters, so it’s non-trivial to just brute force a solution.  But if you insert a human into the loop, you can quickly discard the blind alleys and home in on the right answer.
I wrote a tool for decoding such Morse code strings that is driven by a human, but where the computer does the tedious grunt-work.  The idea is simple; the computer works out all the possibilities for the next 3 letters, and then the human selects which prefixes “look promising” to investigate further.  If it turns into a blind alley, we can backtrack and try again.  Some screenshots along with some prose will explain.
When you start things off, you see all the possibilities for the first letters:
Morse1
Hm, perhaps I think “SEE” looks like the most likely start.  I can type ‘see’ and now the tool shows
Morse2
where the blue highlight shows the currently “committed” prefix in both the Morse code and the decodings I’m working with.  Ok, I glance down the list and this looks like a blind alley.  So I press backspace three times and look at the original list from the first screenshot again.  There are a few reasonable looking prefixes starting with “HE”, so I type ‘he’ and see
Morse3
and it looks like the first word might be ‘HERE’ or ‘HELLO’.  Some further exploring and I’ll quickly find
Morse4
and I’ll bet that “HELLOWORLD” is the intended decoding.  Shazam!  Doing this all by hand would have taken a lot longer.
Some of you might be thinking that the entire process could be entirely automated—that is, by using English dictionaries, analyses of letter frequencies, etc., the computer could try the most likely paths and not have to brute force it.  You might be right, but the puzzle creators are often very clever to foil such things.  For example, the text might be “THEYEARMMXWAS…” where encoding 2010 as a Roman numeral is likely to foul up an auto-solver.  Or perhaps this might be part of some puzzle entitled “X marks the spot” where the puzzle involved crossing out excess ‘X’s and then “XHELLOXWORLDX” might be the answer, or whatnot.  In general, puzzle creators are good at ensuring that humans will have success where machines alone would fail.
This is an F# blog, so of course I need to show you the F# code for the tool.  It’s a mere 75 lines, with more than a third of those lines devoted to the Morse code table itself.  Which is to say, the code is short and easy—you can hack this up in just a few minutes (I know, because I hacked it up in just a few minutes last night).  So I present the code without further explanation—enjoy!
let morseTable = [
 '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', "--.."
 ]
 
let toMorse s = 
    let d = dict morseTable
    System.String.Join("", [|for c in s do yield d.[c]|])
 
let rec possiblyNextLetters n (morse:string) =
    match n, morse with
    | 0,_ -> [[' ']]
    | _,"" -> [[' ']]
    | _ -> 
        [for c,m in morseTable do
            if morse.StartsWith(m) then
                let r = possiblyNextLetters (n-1) (morse.Substring(m.Length)) 
                let r2 = [for x in r -> c::x]
                yield! r2]
 
open System
let mutable committed = ""
let toDecode = "......-...-..---.-----.-..-..-.."
while true do
    let committedMorse = toMorse committed
    let restMorse = toDecode.Substring(committedMorse.Length)
    assert(toDecode.StartsWith(committedMorse))
    Console.BackgroundColor <- ConsoleColor.Blue 
    Console.Write(" {0}", committedMorse)
    Console.BackgroundColor <- ConsoleColor.Black 
    Console.WriteLine(restMorse)
    let nexts = possiblyNextLetters 3 restMorse |> List.map (fun cs -> System.String(Seq.toArray cs))    
    for n in nexts do
        Console.BackgroundColor <- ConsoleColor.Blue 
        Console.Write(" {0}", committed)
        Console.BackgroundColor <- ConsoleColor.Black 
        Console.WriteLine(n)
    let k = Console.ReadKey()
    Console.WriteLine()
    if k.Key = ConsoleKey.Backspace && committed.Length > 0 then
        committed <- committed.Substring(0, committed.Length - 1)
    else
        let k = k.KeyChar
        let k = System.Char.ToUpper(k)
        if k >= 'A' && k <= 'Z' then
            if nexts |> Seq.exists (fun s -> s.StartsWith(string k)) then
                committed <- committed + string k
            else
                Console.WriteLine(" Not a legal next char!")
        else
            Console.WriteLine(" Press a letter to commit that letter, or backspace to uncommit one")
    Console.WriteLine()
 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: