advent17.hs

   1 import Data.List (subsequences, (\\), sort, sortBy)
   2 import Data.Ord (comparing)
   3 import Data.ByteString.Char8 (pack)
   4 import Crypto.Hash (hash, Digest, MD5)
   5
   6
   7 type Position = (Int, Int)
   8 data Agendum = Agendum {position :: Position, path :: String, hsh :: String} deriving (Show, Eq)
   9 type Agenda = [Agendum]
  10
  11 -- input = "hijkl"
  12 -- input = "ihgpwlah"
  13
  14 input = "qljzarfv" -- my input
  15
  16
  17
  18 main :: IO ()
  19 main = do
  20     part1
  21     part2
  22
  23 initialAgenda = [Agendum {position=(1, 1), path="", hsh=(getHash "")}]
  24
  25
  26 part1 :: IO ()
  27 part1 = print $ path $ extractJust $ bfs initialAgenda
  28
  29 part2 :: IO ()
  30 part2 = print $ bfs2 initialAgenda 0
  31
  32
  33 getHash :: String -> String
  34 getHash path = show (hash $ pack (input ++ path) :: Digest MD5)
  35
  36
  37 extractJust :: Maybe Agendum -> Agendum
  38 extractJust Nothing = head initialAgenda
  39 extractJust (Just x) = x
  40
  41
  42 bfs :: Agenda -> Maybe Agendum
  43 bfs [] = Nothing
  44 bfs (current:agenda) =
  45     if isGoal current then Just current
  46     else bfs (agenda ++ (successors current))
  47
  48
  49 bfs2 :: Agenda -> Int -> Int
  50 bfs2 [] l = l
  51 bfs2 (current:agenda) l =
  52     if isGoal current then bfs2 agenda (length $ path $ current)
  53     else bfs2 (agenda ++ (successors current)) l
  54
  55
  56 isGoal :: Agendum -> Bool
  57 isGoal agendum = (position agendum) == (4, 4)
  58
  59 isLegalPos :: Position -> Bool
  60 isLegalPos p = fst p >= 1 && fst p <= 4 && snd p >= 1 && snd p <= 4
  61
  62 successors :: Agendum -> Agenda
  63 successors state = [Agendum {position = step p0 ld,
  64                              path = path0 ++ [ld],
  65                              hsh = getHash (path0 ++ [ld])} | ld <- legalDoors ]
  66     where
  67         p0 = position state
  68         path0 = path state
  69         h0 = hsh state
  70         doors = openDoors h0
  71         legalDoors = filter (isLegalPos . (step p0)) doors
  72
  73 openDoors hash = (u hash) ++ (d hash) ++ (l hash) ++ (r hash)
  74
  75 u hash = if hash!!0 `elem` "bcdef" then "U" else ""
  76 d hash = if hash!!1 `elem` "bcdef" then "D" else ""
  77 l hash = if hash!!2 `elem` "bcdef" then "L" else ""
  78 r hash = if hash!!3 `elem` "bcdef" then "R" else ""
  79
  80 step (r, c) 'U' = (r-1, c)
  81 step (r, c) 'D' = (r+1, c)
  82 step (r, c) 'L' = (r, c-1)
  83 step (r, c) 'R' = (r, c+1)
  84
  85
  86