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

<https://adventofcode.com/2018/day/14>
-}
module Main (main) where

import Advent.Format (format)
import Data.Char (digitToInt)
import Data.List (findIndex, isPrefixOf, tails, foldl')
import Data.Maybe (fromJust)
import Data.Sequence (Seq)
import Data.Sequence qualified as Seq

-- | Print the answers to day 14
--
-- >>> :main
-- 7116398711
-- 20316365
main :: IO ()
IO ()
main =
  do Int
input <- [format|2018 14 %u%n|]
     String -> IO ()
putStrLn (Int -> String
part1 Int
input)
     Int -> IO ()
forall a. Show a => a -> IO ()
print (Int -> Int
part2 Int
input)

-- | Find the next 10 recipies after dropping the first @input@ recipies.
--
-- >>> part1 5
-- "0124515891"
-- >>> part1 18
-- "9251071085"
-- >>> part1 2018
-- "5941429882"
part1 :: Int -> String
part1 :: Int -> String
part1 Int
input = (Int -> String) -> [Int] -> String
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Int -> String
forall a. Show a => a -> String
show (Int -> [Int] -> [Int]
forall a. Int -> [a] -> [a]
take Int
10 (Int -> [Int] -> [Int]
forall a. Int -> [a] -> [a]
drop Int
input [Int]
entries))

-- | Find the index of the first occurrence of a list of recipies
--
-- >>> part2 51589
-- 9
-- >>> part2 92510
-- 18
-- >>> part2 59414
-- 2018
part2 :: Int -> Int
part2 :: Int -> Int
part2 Int
input = Maybe Int -> Int
forall a. HasCallStack => Maybe a -> a
fromJust (([Int] -> Bool) -> [[Int]] -> Maybe Int
forall a. (a -> Bool) -> [a] -> Maybe Int
findIndex (Int -> [Int]
toDigits Int
input [Int] -> [Int] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
`isPrefixOf`) ([Int] -> [[Int]]
forall a. [a] -> [[a]]
tails [Int]
entries))

data Cooks = Cooks !Int !Int !(Seq Int)
  deriving Int -> Cooks -> ShowS
[Cooks] -> ShowS
Cooks -> String
(Int -> Cooks -> ShowS)
-> (Cooks -> String) -> ([Cooks] -> ShowS) -> Show Cooks
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Cooks -> ShowS
showsPrec :: Int -> Cooks -> ShowS
$cshow :: Cooks -> String
show :: Cooks -> String
$cshowList :: [Cooks] -> ShowS
showList :: [Cooks] -> ShowS
Show

-- | Infinite list of recipies created by the elves.
--
-- >>> take 12 entries
-- [3,7,1,0,1,0,1,2,4,5,1,5]
entries :: [Int]
entries :: [Int]
entries = Int
3 Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: Int
7 Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: Cooks -> [Int]
generate (Int -> Int -> Seq Int -> Cooks
Cooks Int
0 Int
1 ([Int] -> Seq Int
forall a. [a] -> Seq a
Seq.fromList [Int
3,Int
7]))

-- | Turn an integer into a list of its digits
--
-- >>> toDigits 0
-- [0]
-- >>> toDigits 5
-- [5]
-- >>> toDigits 15
-- [1,5]
toDigits :: Int -> [Int]
toDigits :: Int -> [Int]
toDigits = (Char -> Int) -> String -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map Char -> Int
digitToInt (String -> [Int]) -> (Int -> String) -> Int -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> String
forall a. Show a => a -> String
show

-- | Generate the infinite list of recipies created by the elves.
generate :: Cooks -> [Int]
generate :: Cooks -> [Int]
generate (Cooks Int
elf1 Int
elf2 Seq Int
recipies) =
  [Int]
news [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++ Cooks -> [Int]
generate (Int -> Int -> Seq Int -> Cooks
Cooks Int
elf1' Int
elf2' Seq Int
recipies')
  where
    elf1r :: Int
elf1r = Seq Int -> Int -> Int
forall a. Seq a -> Int -> a
Seq.index Seq Int
recipies Int
elf1
    elf2r :: Int
elf2r = Seq Int -> Int -> Int
forall a. Seq a -> Int -> a
Seq.index Seq Int
recipies Int
elf2

    news :: [Int]
news = Int -> [Int]
toDigits (Int
elf1r Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
elf2r)
    recipies' :: Seq Int
recipies' = (Seq Int -> Int -> Seq Int) -> Seq Int -> [Int] -> Seq Int
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Seq Int -> Int -> Seq Int
forall a. Seq a -> a -> Seq a
(Seq.|>) Seq Int
recipies [Int]
news

    elf1' :: Int
elf1' = Int -> Int -> Int
nextPos Int
elf1 Int
elf1r
    elf2' :: Int
elf2' = Int -> Int -> Int
nextPos Int
elf2 Int
elf2r
    nextPos :: Int -> Int -> Int
nextPos Int
i Int
r = (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` Seq Int -> Int
forall a. Seq a -> Int
Seq.length Seq Int
recipies'