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

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

-}
module Main where

import Advent
import Data.Map qualified as Map
import Data.Vector.Unboxed (Vector)
import Data.Vector.Unboxed qualified as V

main :: IO ()
IO ()
main =
  do [Int]
input <- [format|2017 6 %u&%t%n|]
     (Int, Int) -> IO ()
forall a. Show a => a -> IO ()
print (Vector Int -> (Int, Int)
solve ([Int] -> Vector Int
forall a. Unbox a => [a] -> Vector a
V.fromList [Int]
input))

-- | Compute both parts of Day 6
--
-- >>> solve (V.fromList [0,2,7,0])
-- (5,4)
solve :: Vector Int -> (Int,Int)
solve :: Vector Int -> (Int, Int)
solve = [Vector Int] -> (Int, Int)
forall a. Ord a => [a] -> (Int, Int)
findLoop ([Vector Int] -> (Int, Int))
-> (Vector Int -> [Vector Int]) -> Vector Int -> (Int, Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Vector Int -> Vector Int) -> Vector Int -> [Vector Int]
forall a. (a -> a) -> a -> [a]
iterate Vector Int -> Vector Int
step

-- | Computes the steps until a state repeats and also the length of the loop
--
-- >>> findLoop [1,2,3,4,5,6,7,5]
-- (7,3)
-- >>> findLoop [1,1]
-- (1,1)
-- >>> findLoop [0,1,1]
-- (2,1)
findLoop :: Ord a => [a] -> (Int,Int)
findLoop :: forall a. Ord a => [a] -> (Int, Int)
findLoop = Map a Int -> [a] -> (Int, Int)
forall {k}. Ord k => Map k Int -> [k] -> (Int, Int)
go Map a Int
forall k a. Map k a
Map.empty
  where
    go :: Map k Int -> [k] -> (Int, Int)
go Map k Int
seen (k
x:[k]
xs) =
      let n :: Int
n = Map k Int -> Int
forall k a. Map k a -> Int
Map.size Map k Int
seen in
      case k -> Map k Int -> Maybe Int
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
x Map k Int
seen of
        Maybe Int
Nothing -> Map k Int -> [k] -> (Int, Int)
go (k -> Int -> Map k Int -> Map k Int
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
x Int
n Map k Int
seen) [k]
xs
        Just Int
i  -> (Int
n, Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i)

-- | Given a vector representing the memory banks compute the new memory bank
-- layout.
--
-- >>> step (V.fromList [0,2,7,0])
-- [2,4,1,2]
-- >>> step (V.fromList [2,4,1,2])
-- [3,1,2,3]
-- >>> step (V.fromList [3,1,2,3])
-- [0,2,3,4]
step :: Vector Int -> Vector Int
step :: Vector Int -> Vector Int
step Vector Int
xs = (Int -> Int -> Int) -> Vector Int -> [(Int, Int)] -> Vector Int
forall a b.
Unbox a =>
(a -> b -> a) -> Vector a -> [(Int, b)] -> Vector a
V.accum Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) Vector Int
xs ((Int
i, -Int
mx) (Int, Int) -> [(Int, Int)] -> [(Int, Int)]
forall a. a -> [a] -> [a]
: [ (Int
jInt -> Int -> Int
forall a. Integral a => a -> a -> a
`rem`Int
n, Int
1) | Int
j <- [Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1 .. Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
mx]])
  where
    mx :: Int
mx     = Vector Int -> Int
forall a. (Unbox a, Ord a) => Vector a -> a
V.maximum Vector Int
xs
    Just Int
i = Int -> Vector Int -> Maybe Int
forall a. (Unbox a, Eq a) => a -> Vector a -> Maybe Int
V.elemIndex Int
mx Vector Int
xs
    n :: Int
n      = Vector Int -> Int
forall a. Unbox a => Vector a -> Int
V.length Vector Int
xs