Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25
Part 1
It's nice to not be dealing with a 2D array after yesterday's ordeal. Day 12 asks us to parse some directions and emulate a ship's movement while tracking its position and orientation.
Our approach is fairly simple. Track the ship's position as an (x,y), as well as its orientation. We choose to represent direction as a integer between 0 and 3. Rotation can then be easily expressed as modular arithmetic on this integer.
import D12input
-- input :: [(String, String)]
-- 0 is north, 1 is east, 2 is south, 3 is west
dd :: [(Int, Int)]
dd = [(0, 1), (1, 0), (0, -1), (-1, 0)]
rotateRight :: String -> Int -> Int
rotateRight "90" d = mod (d + 1) 4
rotateRight "180" d = mod (d + 2) 4
rotateRight "270" d = mod (d + 3) 4
rotateLeft :: String -> Int -> Int
rotateLeft "90" = rotateRight "270"
rotateLeft "180" = rotateRight "180"
rotateLeft "270" = rotateRight "90"
moveForward :: Int -> (Int, Int, Int) -> (Int, Int, Int)
moveForward n (x, y, d) =
let (dx, dy) = dd !! d
in (x + n*dx, y + n*dy, d)
execute :: [(String, String)] -> (Int, Int, Int) -> (Int, Int, Int)
execute [] state = state
execute ((c,v):cvs) (x,y,d)
| c == "N" = execute cvs (x, y+n, d)
| c == "S" = execute cvs (x, y-n, d)
| c == "E" = execute cvs (x+n, y, d)
| c == "W" = execute cvs (x-n, y, d)
| c == "L" = execute cvs (x, y, rotateLeft v d)
| c == "R" = execute cvs (x, y, rotateRight v d)
| c == "F" = execute cvs (moveForward n (x, y, d))
where n = read v :: Int
solve :: Int
solve = let (x, y, _) = execute input (0, 0, 1)
in (abs x + abs y)
main :: IO ()
main = print $ solve
The rest of solution is a fairly straightforward implementation of the problem specification. This theme of "execute a series of commands" is something we've seen before, so we again implement it via recursion, passing the state we need to track (coordinates and direction) as we go.
Part 2
Part 2 is very similar, but we need to interpret most commands as moving a waypoint instead of moving the ship itself.
Unfortunately, we need to abandon our cute trick of mapping the directions onto [0..3], as we need to be able to move in directions other than north/south/east/west. The approach is the same, though: recurse through the sequence of commands, passing the state (now the ship coordinates and the waypoint coordinates) along. When we reach the end of the program, we return the final state, and use it in the solve function to compute what the problem asks for.
import D12input
-- input :: [(String, String)]
type WRelCoords = (Int, Int)
type SAbsCoords = (Int, Int)
rotateRight :: String -> WRelCoords -> WRelCoords
rotateRight "90" (x,y) = (y,-x)
rotateRight "180" (x,y) = (-x,-y)
rotateRight "270" (x,y) = (-y,x)
rotateLeft :: String -> WRelCoords -> WRelCoords
rotateLeft "90" = rotateRight "270"
rotateLeft "180" = rotateRight "180"
rotateLeft "270" = rotateRight "90"
moveForward :: Int -> WRelCoords -> SAbsCoords -> SAbsCoords
moveForward n (dx, dy) (x, y) = (x + n*dx, y + n*dy)
execute :: [(String, String)] -> (WRelCoords, SAbsCoords) -> (WRelCoords, SAbsCoords)
execute [] state = state
execute ((c,v):cvs) ((dx, dy), (x, y))
| c == "N" = execute cvs ((dx, dy+n), (x, y))
| c == "S" = execute cvs ((dx, dy-n), (x, y))
| c == "E" = execute cvs ((dx+n, dy), (x, y))
| c == "W" = execute cvs ((dx-n, dy), (x, y))
| c == "L" = execute cvs (rotateLeft v (dx,dy), (x, y))
| c == "R" = execute cvs (rotateRight v (dx,dy), (x, y))
| c == "F" = execute cvs ((dx, dy), moveForward n (dx, dy) (x, y))
where n = read v :: Int
solve :: Int
solve = let (_, (x, y)) = execute input ((10, 1), (0, 0))
in (abs x + abs y)
main :: IO ()
main = print $ solve
moveForward is actually simpler than in part 1, because we are directly tracking the "velocity vector" (which is what the waypoint really represents), instead of needing to infer it from the direction.
Rotation is slightly more complex, but since the input only gives 90, 180, or 270 as the rotation angle, we can still express it as very simple formulae. Of course, if that were not the case, we would need to borrow some concept from trigonomotery (2D rotation by an arbitrary angle).
Finally, it is worth noting that part 2 is actually just a generalization of part 1, and we can restore our answer to part 1 by passing (1, 0) as the initial waypoint location.
Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25