My Diversions

Well at least my picture is:

Perhaps the Sudbury, Ontario municipal sculptor will use that photo as a reference when they erect a statue honoring Tom Davies…

I’ve recently found myself not blogging because I didn’t wish to inflict the posts on Planet Atlassian. So now anything non-technical which I don’t think is of interest to subscribers to this blog (Hi to both of you!) appears here.

Along with some colleagues I entered the ICFP programming contest this year.

You can read some more about our experience at Matt’s blog.

I thought the problem — guiding a Mars rover to a goal amongst obstacles — was very well chosen. It was possible to navigate the example maps with very simple software, so everyone could get the satisfaction of seeing their rover succeed. If you had the time and skills, there were a vast number of directions to go in to improve your rover’s performance. This compares favourably with last year’s problem. That problem was very clever, and I had a lot of fun playing with it, but I never got close to having a worthwhile submission because the threshold for even partial success was quite high. So kudos to the ICFP2008 team for creating a problem which has a low barrier to entry while still having the ‘dynamic range’ needed to challenge the top teams.

I’ll definitely participate next year. Among the lessons we learnt:

• Have all the team on the same premises, especially for the first few hours. When you are writing software this quickly you need to all be on the same page all the time.
• For developing geometry based heuristics visualisation is very important. You need to be able to see what your code is trying to do — where it is trying to go, what it thinks is blocking it, when it starts to turn and so on.

We wrote our entry in Java, but over the next few weeks I plan to produce something just as sophisticated in CAL. It is a functional programming contest after all

I’m much happier with the second version:

out3 a =
    let
        renderGroup g =
            let 
                char = head g;
                count = length g;
                renderChars :: Int -> String;
                renderChars n =
                    (fromChar char) ++
                    (if n >1 then  " " ++ (renderChars $ n-1) else "");
            in
                if count > 2 then
                    (renderChars 2) ++ 
                    " <span>" ++ (renderChars (count - 2)) ++ "</span>"
                else
                    renderChars count;
        concatWithSep list = (head list) ++ concatMap (\s -> " " ++ s) (tail list);
    in
        concatWithSep $ map renderGroup (group a);

This only uses one ‘exotic’ list function, group:

group :: Eq a => [a] -> [[a]]
    Splits the specified list into a list of lists of equal, adjacent elements.

My program is longer than Matt’s — roughly twice as long — but I think this version is easier to understand.

Matt’s Javascript for loop has some complicated state, contained in some loop variables which are modified in the body of the loop as well as in the for statement itself. I think that’s a recipe for confusion.

My colleague Matt Ryall wrote about this simple algorithm for marking up a series of letters — which is complex enough to be interesting.

I wrote a version in CAL:

arr = ['a', 'b', 'c', 'c', 'd', 'e', 'e', 'e', 'e', 'e',
          'f', 'e', 'f', 'e', 'f', 'a', 'a', 'a', 'f', 'f', 'f'];

data State = State string :: String current :: (Maybe Char) count :: Int;

out =
    let
        initial = State “” Nothing 0;
        f :: State -> Char -> State;
        f state char =
            let
                State s current count = state;
                charStr = fromChar char;
                appendSameChar = 
                    if count == 2 then
                        s ++ ” <span>” ++ charStr
                    else
                        s ++ ” ” ++ charStr;
                appendDiffChar =
                    if count > 2 then
                        s ++ “</span> ” ++ charStr
                    else
                        s ++ ” ” ++ charStr;
            in
                case current of
                    Nothing -> State (fromChar char) (Just char) (1 :: Int);
                    Just c ->
                        if c == char then
                            State appendSameChar (Just char) (count+1)
                        else
                            State appendDiffChar (Just char) 1;
            ;
        finalState = foldLeftStrict f initial arr;
    in
        finalState.State.string ++(if finalState.State.count > 2 then
            “</span>”
        else
            “”);

Positive proof that you can write verbose, confusing code in any language — but at least this code had no bugs — once it compiled it worked correctly first time.

As a follow up to this I will try to do better!