Fabian Linzbergers personal website

Folsomite - Blow Up Your Graphite / Riemann Server With Folsom Metrics

Permalink

Since April I have been hacking Erlang at Campanja, a Stockholm based startup offering a service to optimize search engine marketing. Simply put, Campanja helps people that advertise using google adwords to buy the kind of clicks that provide value to their business and at a price that makes sense for them.

Our system runs entirely distributed on top of Amazons Elastic Cloud, keeping close taps on our many Erlang nodes is essential to understanding what is and has been going on.

We have been using Graphite for quite a while to keep graphs of various metrics. Recently we picked up the excellent Riemann monitoring system. Since we want to instrument a lot of metrics across our system, it is important that doing so is straightforward and mostly automatic.

The Riak project has adopted Folsom for collecting metrics in its 1.2 version. They also contributed code for a new type of histogram sampling (slide_uniform) which keeps a constant number of data points for a given metric and a specific sliding window in time. This means one can for example send timing information for each database write to such a histogram metric, even if they happen at a high rate. Only a representative subset will be stored in a constant amount of memory. Estatsd, which we previously used, has no such sampling. Therefore in a similar situation it consumes increasing amounts of memory. If you send data quickly enough as we did in some tests, until none is left and the virtual machine crashes.

On top of the sampling Folsom provides excellent functions to compute statistical summaries of the collected data.

We decided that we wanted to use all of the above together, so I implemented a new application called Folsomite, which we also released on github. Folsomite periodically aggregates all Folsom metrics present as well as a couple of VM statistics and forwards them to both Graphite and Riemann. If we want instrumentation for a node, all we have to do is to add Folsomite and data for all of the metrics we capture via Folsom will automatically be available for graphing and monitoring.

If you also care about details on what is going on in your Erlang nodes - and really, you should - give it a try yourself!

Klarna Programming Challenge

Permalink

At the beginning of this week the results of the Klarna Programming Contest 2010 were published.

Most important news from my perspective:

Overall best solution:

Second prize: Fabian Linzberger (Apple iPhone)

Yay, I made second place! Yay, I won a smartphone!

Since I was asked about the problems I thought I would write up a bit of my experience.

Problem 1

(picture converted to png for the webbrowser. original PPM here)

A picture in PPM format (http://en.wikipedia.org/wiki/Netpbm_format#PPM_example), was given, that contained a hidden message.

I was totally mislead by the hint “what may seem red and insignificant is not”. I thought it referred to the red text in the picture, when (obviously, in retrospect, haha!) it was in fact referring to the least significant bit of the red part of the pixels in the picture. I spent quite some time filtering the shades of grey around the text before I finally realized I was looking in the wrong place.

Basically some of the first 60 or so pixels would appear white to the eye just like the others around them, but in reality about half of them were just a tiny, tiny bit less red. Decode the white pixels to 0s and the less red pixels to 1s in bits, translate to letters and you had the secret message.

Problem 2

(picture converted to png for the webbrowser. original PPM here)

Another picture, another hidden message. Using the solution program from problem 1 gave a hint: “iccanobiF”.

Clearly “Fibonacci”, just backwards. Now it came in handy that I had actually programmed a decoder for the picture file for problem one. Searching around for suspicious pixel values, quickly revealed around 10 or so which were just a little less red, this time distributed somewhere among the blue of the tulip.

Turns out if you make a list of all blue and slightly less blue pixels in the picture, reverse it and use the Fibonacci sequence as indices you again get a list of bits that decode to letters. Reverse that once again and you had the second keyword. Phew.

Problem 3

A variant of the Game of Life. An encoding of letters to a start configurations of cells on a matrix and the other way round was specified. The solution program had to use this on a keyword, run a certain number of iterations and afterwards decode the resulting configuration of cells to another keyword.

This was a bit of work to implement, but overall I found it a lot easier than the previous two picture puzzles: at least the objective was clear.

Problem 4

A hex encoded and Vigenère encrypted message was given. The task was to decode it. The encryption key could be obtained by running another simulation on the solution program for problem 3. Again a bit of coding, but more straightforward than 1 and 2.

All my coding was done in Haskell. Overall experience was quiet pleasant. Converting bits to text felt like taking a bit too much effort, maybe because I am not used to the libraries. As always: Quickcheck rocks!

Google AI Challenge: Tron

Permalink

I participated in the google ai challenge. In the end I was placed 134 out of 708: My profile url.

Since I am working on a Monte Carlo tree search based Computer Go program, I figured I would try to use that as a basis for my bot.

In general it worked quiet ok. Especially in close range combat it is often able to play quite well:

At longer range and when looking for the longest path in endgame situations lack of depth in the tree search shows and quiet many mistakes are made.

I also experimented with using the distance between the players as a heuristic to bias the tree search into deeper branches, this was only mildly successful however. It seemed to be very hard to strike a balance between the heuristic not making a difference and turning my bot into a chaser.

In the final version my bots strategy is as follows:

Test if there is a path reaching the opponent using the a* pathfinding algorithm.

#         ###############
        ##        ...   #
      ##          .#1   #
    ##      #     .###  #
   #        #     .     #
  #         #     .     #
 #          # ..... #   #
#           # .####     #
# ###       # .         #
#     ####  # .         #
#           # .  #      #
#     #       .  #      #
#     #    ###.  #      #
#     #    ....  #      #
#     #    .#           #
#         ..#  ###      #
#         . #      ###  #
#     ####. #           #
#   #  .... #          # 
#     ..    #         #  
#     .     #        #   
#  ###.     #      ##    
#   2#.          ##      
#   ...        ##        
###############

a* found shortest path between players

In case there is not, enter special endgame mode: the value of nodes in tree search is number of moves divided by flood fill size. I am unhappy with the endgame, this should make less mistakes.

In case opponents can still reach each other, use a biased tree search:

p and P are nodes searched for player 1
e and E are nodes searched for player 2 (enemy)
1 is the principal variation for player 1
1 is the principal variation for player 2

###############
#1PPPPPPP     #
#111PPPPP     #
#1111PPP     e#
#PPP1PP     eE#
#PPPPPPP   eEE#
#PPPPPPPe eEEE#
#PPPPPPEEEeEEE#
#PPP p EEEEEEE#
#PPp   EEEEEEE#
#Pp    EEE2EEE#
#      EEE2222#
#     EEEEEE22#
#    EEEEEEE22#
###############
nodes evaluated for each player in tree search at long range

At long range nodes closing in to the opponent are preferred.

Nodes are evaluated using flood fill if they divide opponents into separate areas.

Otherwise random playouts until either player crashes are used.

###############
##     PPP  e #
#### pPPPPWEEE#
#  #PPPP111222#
#  #PPP11W22E2#
#  #PPP11W2EEE#
#  #####1W2EEE#
#    ##1122EEE#
#    PPPW#EEE #
#     PP ##E  #
#         #   #
#         #####
#          ####
#          ####
###############
nodes evaluated for each player in tree search at closer range

Tree search terminates as soon as 0.9 seconds are spent and return the best move found so far.

After reading a little about strategies other people have used, it may also have been a bad heuristic to just approach the other bot. “Voronoi territory” - the number of points that can be reached by each bot first - may have been a better choice. In general a good heuristic is key for Monte Carlo tree search to be able to deeply explore the tree without missing the wrong branches, so this could have helped a lot.

Further links:

Sudoku

Permalink

Lefants haskell sudoku solver

Sometime in autumn 2009 i created a sudoku solver in haskell as a programming exercise for myself. I am pretty happy with the result, it took no more than an afternoon to implement and has been able to solve everything I tried in a couple of seconds. Now I can happily smile to myself whenever I see someone solving sudokus from the newspaper ;)

Below is a commented and syntax highlighted version of the main module, the complete code in git is also online.

If you are interested in more haskell solutions to the sudoku problem, make sure to check out the Sudoku page on haskellwiki

-- Lefants haskell sudoku solver
-- -----------------------------

{-# OPTIONS -O2 -Wall -Werror -Wwarn #-}

-- This is the main module, containing the actual logic.

module Sudoku (
               solveOne,
              ) where
import Data.List


{-
There are two helpers:

 * sudoku-test runs some (very very basic) tests.
 * sudoku-run is the binary for normal invocation, it will read from
   stdin and output to stdout. use it like this:

$ cat <<EOF | ./sudoku-run
.98......
....7....
....15...
1........
...2....9
...9.6.82
.......3.
5.1......
...4...2.
EOF

798624315
315879246
264315978
129587463
683241759
457936182
942158637
531762894
876493521
-}




{-
The Coord type is a three-dimensional coordinate, the 3rd one is the
box the field is in, like indicated here:

+-----------+
|111|222|333|
|111|222|333|
|111|222|333|
+-----------+
|444|555|666|
|444|555|666|
|444|555|666|
+-----------+
|777|888|999|
|777|888|999|
|777|888|999|
+-----------+
-}

type Coord = (Int, Int, Int)



-- Value holds a solution value or a list of remaining valid
-- candidates for the field.

data Value = Element Int | Options [Int]
           deriving (Show)

-- An actual field consists of a coordinate and a Value (as described
-- above).

type Pair = (Coord, Value)



-- This is the main exported function. It will read in a string of
-- digits or . and feed it to the solve' function which will find a
-- solution using solve and then return a prettified string
-- representation.

solveOne :: String -> String
solveOne ls =
    concatMap pretty $
    sortBy compareC $
    solve' $
    zip triples $
    map readOne ls


-- This will return a list of three-dimensional coordinates as
-- explained with the Coord type above.

triples :: [Coord]
triples = 
    zip3 a b $ map z pairs
    where
      pairs = [(a', b') | b' <- [1..9], a' <- [1..9]]
      (a, b) = unzip pairs

      z :: (Int, Int) -> Int
      z (x, y) =
          x2z + y2z
          where
            x2z = ((x - 1) `div` 3) + 1
            y2z = ((y - 1) `div` 3) * 3


-- Pretty representation of field values

pretty :: (t, Value) -> String
pretty (_, Element e) = show e
pretty (_, Options _) = ""


-- Used for sorting coordinates from left to right and top to bottom.

compareC :: (Ord t2, Ord t3) =>
            ((t2, t3, t4), t) -> ((t2, t3, t5), t1) -> Ordering
compareC (c1, _) (c2, _) =
    compareT c1 c2
    where
      compareT (a1, b1, _) (a2, b2, _)
          | b1 == b2  = compare a1 a2
          | otherwise = compare b1 b2



-- Read in a predefined single value or failing that initialize the
-- list of options.

readOne :: Char -> Value
readOne c =
    case c `elem` (map (head.show) ([1..9] :: [Int])) of
      True -> Element (read [c])
      False -> Options [1..9]



-- solve' and solve contain the actual solving logic. solve' will
-- partition the initial list of fields into ones containing single
-- elements (already defined / solved) and those containing a list of
-- remaining options.

solve' :: [Pair] -> [Pair]
solve' ls =
    solution
    where
      Just solution = solve done todo
      (done, todo) = partition isElement ls
      isElement :: (t, Value) -> Bool
      isElement (_, Element _) = True
      isElement (_, Options _) = False


-- solve takes two lists of coordinate / value pairs as parameters:
-- the first one contains solved single element fields, the second all
-- the lists with remaining options.

solve :: [Pair] -> [Pair] -> Maybe [Pair]
-- if all the fields have one element we are done.
solve es [] = Just es
solve es os =
    case as of
      -- no more Options, no solutions possible
      [] -> Nothing
      -- try first option
      (a : as') ->
          -- recurse using backtracking, if we can solve it
          case solve ((c, Element a) : es) os' of
            -- we are done
            Just es' ->
                Just es'
            -- this branch contains no solutions, retry without it
            Nothing ->
                solve es ((c, Options as') : os')

    where
      -- first prune all Options list at the current level, then order
      -- branches with *few* options first
      ((c, Options as) : os') = sortBy lessOptions $ map revaluate os

      lessOptions (_, Options xs) (_, Options ys) =
          compare (length xs) (length ys)
      lessOptions (_, Element _) _ =
          error "illegal lessOptions call"
      lessOptions (_, Options _) (_, Element _) =
          error "illegal lessOptions call"

      -- filter out other Options from list that are made impossible
      -- by choosing a certain one
      revaluate :: Pair -> Pair
      revaluate (c'@(x, y, z), Options aas) =
          {-# SCC "revaluate" #-}
          (c', Options aas')
          where
            aas' = aas \\ otherValues
            otherValues = map (\(_, Element e) -> e)
                          ((filter (\e -> x == px e) es) ++ 
                           (filter (\e -> y == py e) es) ++
                           (filter (\e -> z == pz e) es))
      revaluate ((_, _, _), Element _) =
          error "illegal revaluate call"


-- helper functions to project a single coordinate from a Pair

px :: Pair -> Int
px ((x, _, _), _) = x
py :: Pair -> Int
py ((_, y, _), _) = y
pz :: Pair -> Int
pz ((_, _, z), _) = z

Introduction to Programming With Laby

Permalink

The other day I was playing a little bit with laby, a small program to help in understanding basic programming concepts for kids, but maybe grown ups too.

It is available in Ubuntu in the laby package from karmic (9.10) on. I can highly recommend it, it is always fun to watch a graphical representation of a programmed creature do its job after the coding. I have created a general solution in ocaml that will successfully solve at least all the levels included in 0.5.0.

(* ocaml wall hugger for laby *)
let ant =
  (* go straight ahead til we hit something *)
  while (Robot.look () = `Void) do
    Robot.forward ();
  done;

  (* main wall hugin' loop *)
  while not (Robot.look () = `Exit) do

    if (Robot.look () == `Void)
    then (
      Robot.forward ();
      Robot.right ();
    );

    if (Robot.look () == `Rock)
    then (
      Robot.take ();
      Robot.forward ();
      Robot.left ();
      Robot.left ();
      Robot.drop ();
      Robot.left ();
    );

    if (Robot.look () == `Wall) or (Robot.look () == `Web)
    then
      Robot.left ();

  done;

  Robot.door_open ();
;;

download source file: laby.ml

Go little robot ant!