Advertisement

# 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