Advertisement
rayl

Monkey Grid Puzzle

Aug 23rd, 2013
42
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import Data.Char (ord)
  2. import qualified Data.Set as S
  3. import qualified Data.Vector as V
  4.  
  5. type Coord = (Int,Int)
  6. type Done = S.Set Coord
  7. type Todo = [Coord]
  8.  
  9. main = putStrLn $ show n
  10.  
  11. n = loop 0 [(0,0)] S.empty
  12.  
  13. loop :: Int -> Todo -> Done -> Int
  14. loop n [] _ = n
  15. loop n (t:ts) d = loop (n + count t) (also t d ++ ts) (S.insert t d)
  16.  
  17. count :: Coord -> Int
  18. count (0,0) = 1
  19. count (0,_) = 4
  20. count (_,0) = 4
  21. count (x,y) = if x == y then 4 else 8
  22.  
  23. also :: Coord -> Done -> Todo
  24. also c d = filter (\k -> S.notMember k d) $
  25.            filter isAccessible $
  26.            filter inQuadrant $
  27.            next c
  28.  
  29. isAccessible :: Coord -> Bool
  30. isAccessible (x,y) = sumDigits <= 19
  31.   where
  32.     sumDigits = sums V.! x + sums V.! y
  33.  
  34. inQuadrant :: Coord -> Bool
  35. inQuadrant (x,y) = y <= x
  36.  
  37. next :: Coord -> Todo
  38. next (x,y) = [(x+1,y), (x,y+1)]
  39.  
  40. sums :: V.Vector Int
  41. sums = V.generate 300 sum1
  42.   where
  43.     sum1 n = sum $ map val (show n)
  44.     val x = ord x - ord '0'
Advertisement
RAW Paste Data Copied
Advertisement