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

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

Elves sitting in a circle stealing presents.

-}
module Main where

import Advent (format)
import Data.Sequence (Seq)
import Data.Sequence qualified as Seq

-- | >>> :main
-- 1830117
-- 1417887
main :: IO ()
IO ()
main =
 do Int
elves <- [format|2016 19 %u%n|]
    let ring :: Seq Int
ring = [Int] -> Seq Int
forall a. [a] -> Seq a
Seq.fromList [Int
1..Int
elves]
    Int -> IO ()
forall a. Show a => a -> IO ()
print (Seq Int -> Int
forall a. Seq a -> a
part1 Seq Int
ring)
    Int -> IO ()
forall a. Show a => a -> IO ()
print (Seq Int -> Int
forall a. Seq a -> a
part2 Seq Int
ring)

part1 :: Seq a -> a
part1 :: forall a. Seq a -> a
part1 (a
x Seq.:<| Seq a
Seq.Empty) = a
x
part1 (a
x Seq.:<| a
_ Seq.:<| Seq a
xs) = Seq a -> a
forall a. Seq a -> a
part1 (Seq a
xs Seq a -> a -> Seq a
forall a. Seq a -> a -> Seq a
Seq.|> a
x)

part2 :: Seq a -> a
part2 :: forall a. Seq a -> a
part2 (a
x Seq.:<| Seq a
Seq.Empty) = a
x
part2 (a
x Seq.:<| Seq a
xs) = Seq a -> a
forall a. Seq a -> a
part2 (Seq a
xs' Seq a -> a -> Seq a
forall a. Seq a -> a -> Seq a
Seq.|> a
x)
  where
    xs' :: Seq a
xs' = Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
Seq.deleteAt (Int -> Int
forall {a}. Integral a => a -> a
half (Seq a -> Int
forall a. Seq a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Seq a
xs)) Seq a
xs
    half :: a -> a
half a
x = (a
xa -> a -> a
forall a. Num a => a -> a -> a
-a
1) a -> a -> a
forall a. Integral a => a -> a -> a
`quot` a
2