More point-free
[advent-of-code-16.git] / 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 takeSteps = scanl move
57
58 -- Make one move, by updating direction then position
59 move :: Position -> Step -> Position
60 move (Position facing easting northing)
61 (Step turnInstr distance) =
62 Position facing' easting' northing'
63 where facing' = turn turnInstr facing
64 (easting', northing') = takeStep facing' distance easting northing
65
66 -- Turn right, left, or straight
67 turn :: Char -> Direction -> Direction
68 turn 'R' direction = turnCW direction
69 turn 'L' direction = turnACW direction
70 turn 'S' direction = direction
71
72 -- Move in the current direction
73 takeStep :: Direction -> Int -> Int -> Int -> (Int, Int)
74 takeStep North d e n = (e, n+d)
75 takeStep South d e n = (e, n-d)
76 takeStep West d e n = (e-d, n)
77 takeStep East d e n = (e+d, n)
78
79
80 -- | a `succ` that wraps
81 turnCW :: (Bounded a, Enum a, Eq a) => a -> a
82 turnCW dir | dir == maxBound = minBound
83 | otherwise = succ dir
84
85 -- | a `pred` that wraps
86 turnACW :: (Bounded a, Enum a, Eq a) => a -> a
87 turnACW dir | dir == minBound = maxBound
88 | otherwise = pred dir
89
90 -- All the prefixes of a list of items
91 prefixes = scanl addTerm []
92 where addTerm ps t = ps ++ [t]
93
94 -- The first item that exists in a prefix of the list to that point
95 firstRepeat positions =
96 last $ head $ dropWhile (\p -> (last p) `notElem` (tail $ reverse p))
97 (tail $ prefixes positions)