ansaurus

Question

Has anyone solved a programming puzzle similar to this?

Answer 1

+4 A:

The main insight is this: when determining what's in row 3, you don't care about what's in row 1, just what's in row 2.

So let's call how to build a 64x1 layer a "row scenario". You say that there are about 3300 row scenarios. That's not so bad.

Let's compute a function:

f(s, r) = the number of ways to put row scenario number "s" into row "r", and legally fill all the rows above "r".

(I'm counting with row "1" at the top, and row "10" at the bottom)

STOP READING NOW IF YOU WANT TO AVOID SPOILERS.

Now clearly (numbering our rows from 1 to 10):

f(s, 1) = 1

for all values of "s".

Also, and this is where the insight comes in, (Using Mathematica-ish notation)

f(s, r) = Sum[ f(i, r-1) * fits(s, i) , {i, 1, 3328} ]

where "fits" is a function that takes two scenario numbers and returns "1" if you can legally stack those two rows on top of each other and "0" if you can't. This uses the insight because the number of legal ways to place scenario depends only on the number of ways to place scenarios above it that are compatible according to "fits".

Now, fits can be precomputed and stored in a 3328 by 3328 array of bytes. That's only about 10 Meg of memory. (Less if you get fancy and store it as a bit array)

The answer then is obviously just

Sum[ f(i, 10) , {i, 1, 3328} ]

Daniel Martin 2009-05-27 02:22:02

Answer 2

+2 A:

I solved a similar problem for a programming contest tiling a long hallway with tiles of various shapes. I used dynamic programming: given any panel, there is a way to construct it by laying down one row at a time. Each row can have finitely many shapes at its end. So for each number of rows, for each shape, I compute how many ways there are to make that row. (For the bottom row, there is exactly one way to make each shape.) Then the shape of each row determines the number of shapes that the next row can take (i.e. never line up the spaces). This number is finite for each row and in fact because you have only two sizes of bricks, it is going to be small. So you wind up spending constant time per row and the program finishes quickly.

To represent a shape I would just make a list of 4's and 6's, then use this list as a key in a table to store the number of ways to make that shape in row i, for each i.

Norman Ramsey 2009-05-27 02:58:51

Answer 3

+1 A:

Here is my answer. It's Haskell, among other things, you get bignums for free.

EDIT: It now actually solves the problem in a reasonable amount of time.

MORE EDITS: With a sparse matrix it takes a half a second on my computer.

You compute each possible way to tile a row. Let's say there are N ways to tile a row. Make an NxN matrix. Element i,j is 1 if row i can appear next to row j, 0 otherwise. Start with a vector containing N 1s. Multiply the matrix by the vector a number of times equal to the height of the wall minus 1, then sum the resulting vector.

module Main where
import Data.Array.Unboxed
import Data.List
import System.Environment
import Text.Printf
import qualified Data.Foldable as F
import Data.Word
import Data.Bits

-- This records the index of the holes in a bit field
type Row = Word64

-- This generates the possible rows for given block sizes and row length
genRows :: [Int] -> Int -> [Row]
genRows xs n = map (permToRow 0 1) $ concatMap comboPerms $ combos xs n
  where
    combos [] 0 = return []
    combos [] _ = [] -- failure
    combos (x:xs) n =
      do c <- [0..(n `div` x)]
         rest <- combos xs (n - x*c)
         return (if c > 0 then (x, c):rest else rest)
    comboPerms [] = return []
    comboPerms bs =
      do (b, brest) <- choose bs
         rest <- comboPerms brest
         return (b:rest)
    choose bs = map (\(x, _) -> (x, remove x bs)) bs
    remove x (bc@(y, c):bs) =
      if x == y
         then if c > 1
                 then (x, c - 1):bs
                 else bs
         else bc:(remove x bs)
    remove _ [] = error "no item to remove"
    permToRow a _ [] = a
    permToRow a _ [_] = a
    permToRow a n (c:cs) =
      permToRow (a .|. m) m cs where m = n `shiftL` c

-- Test if two rows of blocks are compatible
-- i.e. they do not have a hole in common
rowCompat :: Row -> Row -> Bool
rowCompat x y = x .&. y == 0

-- It's a sparse matrix with boolean entries
type Matrix = Array Int [Int]
type Vector = UArray Int Word64

-- Creates a matrix of row compatibilities
compatMatrix :: [Row] -> Matrix
compatMatrix rows = listArray (1, n) $ map elts [1..n] where
  elts :: Int -> [Int]
  elts i = [j | j <- [1..n], rowCompat (arows ! i) (arows ! j)]
  arows = listArray (1, n) rows :: UArray Int Row
  n = length rows

-- Multiply matrix by vector, O(N^2)
mulMatVec :: Matrix -> Vector -> Vector
mulMatVec m v = array (bounds v)
    [(i, sum [v ! j | j <- m ! i]) | i <- [1..n]]
  where n = snd $ bounds v

initVec :: Int -> Vector
initVec n = array (1, n) $ zip [1..n] (repeat 1)

main = do
  args <- getArgs
  if length args < 3
    then putStrLn "usage: blocks WIDTH HEIGHT [BLOCKSIZE...]"
    else do
      let (width:height:sizes) = map read args :: [Int]
      printf "Width: %i\nHeight %i\nBlock lengths: %s\n" width height
             $ intercalate ", " $ map show sizes
      let rows = genRows sizes width
      let rowc = length rows
      printf "Row tilings: %i\n" rowc
      if null rows
        then return ()
        else do
          let m = compatMatrix rows
          printf "Matrix density: %i/%i\n"
                 (sum (map length (elems m))) (rowc^2)
          printf "Wall tilings: %i\n" $ sum $ elems
                  $ iterate (mulMatVec m) (initVec (length rows))
                            !! (height - 1)

And the results...

$ time ./a.out 64 10 4 6
Width: 64
Height 10
Block lengths: 4, 6
Row tilings: 3329
Matrix density: 37120/11082241
Wall tilings: 806844323190414

real    0m0.451s
user    0m0.423s
sys     0m0.012s

Okay, 500 ms, I can live with that.

Dietrich Epp 2009-05-29 10:35:48

ansaurus

tags:

views:

answers:

Has anyone solved a programming puzzle similar to this?

related questions