Freigeben über

Solving the Morris Puzzle with F#

  • Artikel

It’s been 11 years since I attended a class which presented both the functional and logic programming paradigms in a single semester, materializing in a Prolog and a Caml Light projects. That class shook the grounds on top of which I had been building my plain old common imperative programming skills and so it made me think outside the box. One can say it changed my life, as I spent 2 and a half years LISPing around lists, lambdas and an incredible number of parentheses. I’m still not sure if that change was for better or for worse, but that is a question beyond the scope of this blog.

One thing is sure, though: I learned there are different paradigms and instances of those paradigms (programming languages) which are better suited for different problems and scenarios. This brings me to the puzzle I’m bringing to this post. My wife showed me the sequence that follows:

  • 1
  • 11
  • 21
  • 1211
  • 111221

She then asked me to continue the sequence and I confess it took me quite a while to figure out the pattern. If you’re in trouble, just search the web for the Morris Puzzle or keep up reading and reverse-engineer the code below. The point is this problem is what the functional programming paradigm was created for and I’d like to share my F# solution with you.

#light
open System

// obtains a digit list from a string supposedly containing an integer
let rec IntListFromString (s : string) =
match s.Length with
| 0 -> []
| _ ->
let char = s.Substring (0, 1) in
let parsed = 0 in
System.Int32.Parse(char) :: IntListFromString (s.Substring 1)

// prints a list by printing each of its elements consecutively
let PrintList l =
List.iter print_any l;
System.Console.WriteLine()

// this recursive function implements the core Morris puzzle algorithm
let rec MorrisHelper x l =
match l with

// an empty list will result in an empty list
| [] -> []

// a list with a single element will typically result in a list
// with 2 elements
| [y] ->

// account for sequences of 10 or more elements
if x >= 10 then
let left = x/10 in
let right = x%10 in
[left;right;y]
else
[x;y]

// if the head of the list equals the next element, increment the
// count and recursively call the function. Otherwise, prefix the
// resulting list with a count and the counted element and call
// the helper function again in a recursively manner
| y::z ->
if y = List.hd z then
MorrisHelper (x+1) z
else
if x >= 10 then
let left = x/10 in
let right = x%10 in
[left;right;y] @ (MorrisHelper 1 z)
else
[x;y] @ (MorrisHelper 1 z)

// this recursive function allows the execution of several
// iterations of the Morris Puzzle for a starting list
let rec MorrisPuzzle l iterations =
match iterations with

// if the number of iterations is zero, then the output
// is the list itself (recursion base)
| 0 -> l

// otherwise, call the helper function and print the results,
// decrementing the iteration count and recursively calling this
// function
| _ -> let res = MorrisHelper 1 l in
PrintList res;
MorrisPuzzle res (iterations-1)

/// The main entry point for the application.
[<STAThread>]
[<EntryPoint>]
let main(args) =
let startingList = IntListFromString args.[0]
PrintList startingList
let listaRes = MorrisPuzzle startingList (System.Int32.Parse args.[1])
0

As the code is thoroughly decorated with comments, please allow me not to dive any deeper into it, what do you say?

Let me just provide some pointers if you’re into trying out F# yourself:

This is just great, don't you think? The question now is: for when a CLR-based logic programming language? I've seen a very clever move around a P# language which compiles to C#, it can't be that difficult bringing that to MSIL directly, right? Microsoft Research, what says you? J

Till next time,

Manuel Oliveira

Comments

  • Anonymous
    March 27, 2010
    Ping back from CommonInterview, great solution thanks, especially cool that it is in functional language...