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

<https://adventofcode.com/2017/day/3>

Day 3 asks questions about Ulam's Spiral <https://en.wikipedia.org/wiki/Ulam_spiral>

-}
module Main where

import Advent (format, partialSums)
import Advent.Coord
import Data.List (mapAccumL)
import Data.Maybe (mapMaybe)
import Data.Map qualified as Map

main :: IO ()
IO ()
main =
  do Int
n <- [format|2017 3 %u%n|]
     Int -> IO ()
forall a. Show a => a -> IO ()
print (Int -> Int
part1 Int
n)
     Int -> IO ()
forall a. Show a => a -> IO ()
print (Int -> Int
part2 Int
n)


-- | Coordinates in the spiral order starting with the origin
--
-- >>> [C 0 0,C 1 0,C 1 1,C 0 1,C (-1) 1] `Data.List.isPrefixOf` coords
-- True
coords :: [Coord]
coords :: [Coord]
coords = [Coord] -> [Coord]
forall a. Num a => [a] -> [a]
partialSums [Coord]
movements
  where
    directions :: [Coord]
directions = [Coord
south, Coord
east, Coord
north, Coord
west]

    movements :: [Coord]
movements =
      do (Coord
d,Int
n) <- [Coord] -> [Coord]
forall a. HasCallStack => [a] -> [a]
cycle [Coord]
directions [Coord] -> [Int] -> [(Coord, Int)]
forall a b. [a] -> [b] -> [(a, b)]
`zip` (Int -> Int -> [Int]
forall a. Int -> a -> [a]
replicate Int
2 (Int -> [Int]) -> [Int] -> [Int]
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< [Int
1..])
         Int -> Coord -> [Coord]
forall a. Int -> a -> [a]
replicate Int
n Coord
d


-- | Find manhattan distance of nth visited coordinate using 1-based counting
--
-- >>> part1 1
-- 0
-- >>> part1 12
-- 3
-- >>> part1 23
-- 2
-- >>> part1 1024
-- 31
part1 :: Int -> Int
part1 :: Int -> Int
part1 Int
input = Coord -> Coord -> Int
manhattan Coord
origin ([Coord]
coords [Coord] -> Int -> Coord
forall a. HasCallStack => [a] -> Int -> a
!! (Int
inputInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1))


-- | Infinite list of the writes done when populating the cells
-- in spiral order by using the sum of the earlier populated
-- neighbors.
--
-- >>> [1,1,2,4,5,10,11,23,25,26,54,57,59,122,133,142,147,304,330,351,362,747,806] `Data.List.isPrefixOf` part2writes
-- True
part2writes :: [Int]
part2writes :: [Int]
part2writes = Int
1 Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: (Map Coord Int, [Int]) -> [Int]
forall a b. (a, b) -> b
snd ((Map Coord Int -> Coord -> (Map Coord Int, Int))
-> Map Coord Int -> [Coord] -> (Map Coord Int, [Int])
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL Map Coord Int -> Coord -> (Map Coord Int, Int)
forall {b}. Num b => Map Coord b -> Coord -> (Map Coord b, b)
go (Coord -> Int -> Map Coord Int
forall k a. k -> a -> Map k a
Map.singleton Coord
origin Int
1) ([Coord] -> [Coord]
forall a. HasCallStack => [a] -> [a]
tail [Coord]
coords))
  where
    go :: Map Coord b -> Coord -> (Map Coord b, b)
go Map Coord b
m Coord
c = (Coord -> b -> Map Coord b -> Map Coord b
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert Coord
c b
here Map Coord b
m, b
here)
      where
        here :: b
here = [b] -> b
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ((Coord -> Maybe b) -> [Coord] -> [b]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (Coord -> Map Coord b -> Maybe b
forall k a. Ord k => k -> Map k a -> Maybe a
`Map.lookup` Map Coord b
m) (Coord -> [Coord]
neighbors Coord
c))

-- | Returns the first value written in part 2 of the problem that is larger
-- than the given input value.
part2 :: Int -> Int
part2 :: Int -> Int
part2 Int
input = [Int] -> Int
forall a. HasCallStack => [a] -> a
head ((Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
input) [Int]
part2writes)