{-# Language QuasiQuotes, ImportQualifiedPost, TemplateHaskell #-}
{-|
Module      : Main
Description : Day 1 solution
Copyright   : (c) Eric Mertens, 2021
License     : ISC
Maintainer  : emertens@gmail.com

<https://adventofcode.com/2016/day/1>

-}
module Main where

import Advent (format, partialSums, stageTH)
import Advent.Coord (Coord, manhattan, north, origin, turnLeft, turnRight)
import Data.List (mapAccumL)
import Data.Set qualified as Set

data D = DL | DR

stageTH

-- | >>> :main
-- 241
-- Just 116
main :: IO ()
IO ()
main =
 do [(D, Int)]
cmds <- [format|2016 1 (@D%d)&(, )%n|]
    let path :: [Coord]
path = [(D, Int)] -> [Coord]
computePath [(D, Int)]
cmds
    Int -> IO ()
forall a. Show a => a -> IO ()
print ([Coord] -> Int
part1 [Coord]
path)
    Maybe Int -> IO ()
forall a. Show a => a -> IO ()
print ([Coord] -> Maybe Int
part2 [Coord]
path)

-- | Given a list of steps determine the ultimate Manhattan-distance from
-- the starting position.
part1 :: [Coord] -> Int
part1 :: [Coord] -> Int
part1 = Coord -> Coord -> Int
manhattan Coord
origin (Coord -> Int) -> ([Coord] -> Coord) -> [Coord] -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Coord] -> Coord
forall a. HasCallStack => [a] -> a
last

part2 :: [Coord] -> Maybe Int
part2 :: [Coord] -> Maybe Int
part2 = (Coord -> Int) -> Maybe Coord -> Maybe Int
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Coord -> Coord -> Int
manhattan Coord
origin) (Maybe Coord -> Maybe Int)
-> ([Coord] -> Maybe Coord) -> [Coord] -> Maybe Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Coord] -> Maybe Coord
forall a. Ord a => [a] -> Maybe a
duplicate

computePath :: [(D,Int)] -> [Coord]
computePath :: [(D, Int)] -> [Coord]
computePath = [Coord] -> [Coord]
forall a. Num a => [a] -> [a]
partialSums ([Coord] -> [Coord])
-> ([(D, Int)] -> [Coord]) -> [(D, Int)] -> [Coord]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Coord -> [(D, Int)] -> [Coord]
toSteps Coord
north

-- | Find the first duplicate element in a list
duplicate :: Ord a => [a] -> Maybe a
duplicate :: forall a. Ord a => [a] -> Maybe a
duplicate = Set a -> [a] -> Maybe a
forall {a}. Ord a => Set a -> [a] -> Maybe a
aux Set a
forall a. Set a
Set.empty
  where
    aux :: Set a -> [a] -> Maybe a
aux Set a
_    [] = Maybe a
forall a. Maybe a
Nothing
    aux Set a
seen (a
x:[a]
xs)
      | a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member a
x Set a
seen = a -> Maybe a
forall a. a -> Maybe a
Just a
x
      | Bool
otherwise         = Set a -> [a] -> Maybe a
aux (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
x Set a
seen) [a]
xs

-- | Compute steps taken by following a list of commands
toSteps ::
  Coord     {- ^ initial direction  -} ->
  [(D,Int)] {- ^ commands           -} ->
  [Coord]   {- ^ list of directions -}
toSteps :: Coord -> [(D, Int)] -> [Coord]
toSteps Coord
dir0 [(D, Int)]
cmds = [[Coord]] -> [Coord]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ((Coord, [[Coord]]) -> [[Coord]]
forall a b. (a, b) -> b
snd ((Coord -> (D, Int) -> (Coord, [Coord]))
-> Coord -> [(D, Int)] -> (Coord, [[Coord]])
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL Coord -> (D, Int) -> (Coord, [Coord])
aux Coord
dir0 [(D, Int)]
cmds))
  where
    aux :: Coord -> (D, Int) -> (Coord, [Coord])
aux Coord
dir (D
lr, Int
steps) =
      let dir' :: Coord
dir' = D -> Coord -> Coord
turn D
lr Coord
dir
      in (Coord
dir', Int -> Coord -> [Coord]
forall a. Int -> a -> [a]
replicate Int
steps Coord
dir')

turn :: D -> Coord -> Coord
turn :: D -> Coord -> Coord
turn D
DL = Coord -> Coord
turnLeft
turn D
DR = Coord -> Coord
turnRight