advent01.hs

   1 import Data.List (sort)
   2 import Data.List.Split (splitOn)
   3
   4 -- turn direction, number of steps
   5 data Step = Step Char Int deriving (Show)
   6
   7 data Direction = North | East | South | West
   8     deriving (Enum, Show, Bounded, Eq)
   9
  10 -- direction, easting, northing
  11 data Position = Position Direction Int Int deriving (Show)
  12 -- Two positions are the same if they're in the same place,
  13 -- regardless of facing
  14 instance Eq Position where
  15     Position _ e n == Position _ e' n' = e == e' && n == n'
  16
  17 main :: IO ()
  18 main = do
  19         instructions <- readFile "advent01.txt"
  20         part1 instructions
  21         part2 instructions
  22
  23 part1 :: String -> IO ()
  24 part1 instructions = do
  25         let answer = finalDistance $ last $ stepsFromStart $ steps instructions
  26         print answer
  27
  28 part2 :: String -> IO ()
  29 part2 instructions = do
  30         let visited = finalDistance $ firstRepeat $ stepsFromStart $ expandSteps $ steps instructions
  31         print visited
  32
  33
  34 -- Extract the steps from the input string.
  35 steps :: String -> [Step]
  36 steps s = map readStep $ splitOn ", " s
  37     where readStep (d:l) = Step d (read l)
  38
  39 -- Take steps from the starting position
  40 stepsFromStart :: [Step] -> [Position]
  41 stepsFromStart = takeSteps (Position North 0 0)
  42
  43 -- Calculate manhattan distance from start to this state
  44 finalDistance :: Position -> Int
  45 finalDistance (Position _ e n) = (abs e) + (abs n)
  46
  47 -- For part 2: convert one step of many spaces to many steps of one space each
  48 expandSteps :: [Step] -> [Step]
  49 expandSteps =
  50     concatMap expandStep
  51     where expandStep (Step dir d) = (Step dir 1) : replicate (d - 1) (Step 'S' 1)
  52
  53 -- Execute a series of steps, keeping track of the positions after each step
  54 takeSteps :: Position -> [Step] -> [Position]
  55 takeSteps pos steps = scanl move pos steps
  56
  57 -- Make one move, by updating direction then position
  58 move :: Position -> Step -> Position
  59 move (Position facing easting northing)
  60     (Step turnInstr distance) =
  61     Position facing' easting' northing'
  62     where facing' = turn turnInstr facing
  63           (easting', northing') = takeStep facing' distance easting northing
  64
  65 -- Turn right, left, or straight
  66 turn :: Char -> Direction -> Direction
  67 turn 'R' direction = turnCW direction
  68 turn 'L' direction = turnACW direction
  69 turn 'S' direction = direction
  70
  71 -- Move in the current direction
  72 takeStep :: Direction -> Int -> Int -> Int -> (Int, Int)
  73 takeStep North d e n = (e, n+d)
  74 takeStep South d e n = (e, n-d)
  75 takeStep West  d e n = (e-d, n)
  76 takeStep East  d e n = (e+d, n)
  77
  78
  79 -- | a `succ` that wraps
  80 turnCW :: (Bounded a, Enum a, Eq a) => a -> a
  81 turnCW dir | dir == maxBound = minBound
  82          | otherwise = succ dir
  83
  84 -- | a `pred` that wraps
  85 turnACW :: (Bounded a, Enum a, Eq a) => a -> a
  86 turnACW dir | dir == minBound = maxBound
  87             | otherwise = pred dir
  88
  89 -- All the prefixes of a list of items
  90 prefixes = scanl addTerm []
  91     where addTerm ps t = ps ++ [t]
  92
  93 -- The first item that exists in a prefix of the list to that point
  94 firstRepeat positions =
  95     last $ head $ dropWhile (\p -> (last p) `notElem` (tail $ reverse p))
  96                             (tail $ prefixes positions)