Day 8: Haunted Wasteland

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

  • Amy
    1·
    2 years ago

    Haskell

    There are quite a few implicit assumptions needed for this one, which I think is a bit unfair. (Even though it’s possible that knowing a solution exists implies those assumptions, I didn’t feel up to proving it). Nevertheless, a good example of how looking at the input data (especially after processing it a bit) can give a big hint to the solution.

    Solution 
    import Data.List
import Data.List.Split
import Data.Maybe

readInput s =
  let (a : _ : b) = lines s
   in (a, map readNode b)
  where
    readNode s =
      let [a, b] = splitOn " = " s
          [c, d] = splitOn ", " $ init $ tail b
       in (a, (c, d))

path (steps, nodes) start = scanl' next start (cycle steps)
  where
    next n step =
      let Just (l, r) = lookup n nodes
       in case step of 'L' -> l; 'R' -> r

part1 input = fromJust $ elemIndex "ZZZ" $ path input "AAA"

{-
  Each path must enter a cycle after an optional prefix.
  Note that all cycle lengths share a common factor (the number of steps),
  so we need to make a several assumptions for this to be solvable.
  A simple case is when each path contains a single terminal at offset
     d ≡ 0 (mod n)
  where n is the cycle length. In this case, terminals will align at
     t = lcm nᵢ.
  Fortunately, that holds for this input.
-}
part2 input@(_, nodes) = foldl1' lcm $ map terminalIndex starts
  where
    starts = filter ((== 'A') . last) $ map fst nodes
    terminalIndex = fromJust . findIndex ((== 'Z') . last) . path input

main = do
  input <- readInput <$> readFile "input08"
  print $ part1 input
  print $ part2 input