Inside F#

Brian's thoughts on F# and .NET

Archive for August, 2010

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()
 

Posted in Uncategorized | Leave a Comment »

Yet another release of F# (August 2010 CTP)

Posted by Brian on August 18, 2010

In case you missed it, today we announced a new release of F#.  If you have VS2010 already, then you probably don’t need this release; this release pretty much just puts the same bits in new CTP packaging.  Briefly:

  • The previous CTP only had the .NET 2.0 versions of the compiler and msbuild tools
  • The previous CTP only installed into the free VS2008 Integrated Shell

Whereas:

  • The new CTP also has the .NET 4.0 versions of the compiler and msbuild tools
  • The new CTP can also install into the free VS2010 Integrated Shell

The MSI tries to be smart – if you have .NET 2.0, it installs those tools; if you have .NET 4.0, it installs those tools; if you have any VS2008, it installs the VS2008 support; if you have the VS2010 Shell, it installs that support.  As always, if you have a prior F# CTP install, uninstall it first, before installing the new CTP.

So basically the new release is of interest to you mostly if you fall into one of these buckets:

  • You have been using the ‘free’ F#-in-VS2008-Shell, and you want to upgrade to ‘free’ 2010 tools so you can take advantage of the pretty new WPF environment and zoomable editor and multi-monitor support and use .NET 4.0 and other “2010-specific stuff”.  The CTP is (and always has been) the moral equivalent of “Visual F# Express”.
  • You have been looking for a .NET 4.0 version of the F# compiler and tools to install on your build server/continuous-integration server, and you didn’t want to install all of Visual Studio on that machine just to get the F# compiler.
  • You’re using F# on Mono/Linux/Mac (grab the ZIP rather than the MSI). (You can already use F# with success on other platforms; I imagine the story here will continue to improve markedly in the coming months, as stuff like this starts to bear fruit.)

So that’s it.  Again, if you have VS2010 Pro or above, you already have all the bits you need on your dev box.  This release just makes those bits more freely available and more conveniently packaged for those without a full VS2010 install.

(There’s a white lie in the previous sentence; there is one new thing in the new CTP, which is an FSharp.Core.dll for Windows Phone 7, but I hope to discuss that in more depth in a future blog post.  I haven’t done _any_ phone programming myself yet, though I am keen to do it, when I find some free time.  If you just can’t wait, then perhaps see Don’s blog for some starter links here.)

Posted in Uncategorized | Leave a Comment »