Home > Uncategorized > Lights off

Lights off

Looking for another puzzle i found the lights off problem at codechef. Wolfram math world suggests a novel approach for solving it. At the core is a linear equations solver. The LinearEqSolver at hackage provides this functionallity for haskell.

The package LinearEqSolver is actually a wrapper that uses external libraries; Z3, CVC4, and MathSAT. I used CVC4 which I downloaded here and installed.

Equipped with a fine solver like this, all we need to do is to construct the matrix in the equation M x = b. Each row in M is a binary matrix Aij which represents the positions of the board that are flipped if the position i,j is pressed. This is the code that constructs Aij:

indices n = [(i,j) | i <- [0..n-1], j <- [0..n-1]]

makeA n i j = 
    map f (indices n)
    f (i',j') = case (abs(i'-i),abs(j'-j)) of
                  (0,0) -> 1
                  (1,0) -> 1
                  (0,1) -> 1
                  _     -> 0

Using this code we can then construct M:

makeM n = map (-2:) (makeM' n)
  where makeM' n = map (uncurry (makeA n)) (indices n)

Note that this code adds an extra column filled with -2. The reason for this is that we are solving a system of linear equations modulo 2. The transformation from modulo to an ordinary lineary equation problem is given here.

Now we can wrap everything up into a solver function.

solve n b = do
    s <- solve' n b
    case s of
      Just x -> return $ map (\x -> mod x 2) $ tail $ x
      _ -> return []
    solve' n b = solveIntegerLinearEqs CVC4 (makeM n) b

Testing the problem give at wolfram math world

test = solve 3 board
  where board = [0,1,0,1,1,0,0,1,1]

yields [1,1,1,0,0,0,0,0,1] which is also the solution presented at wolfram.

Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

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: