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