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

<https://adventofcode.com/2019/day/16>

-}
module Main (main) where

import Advent (format)
import Data.Char (digitToInt)
import Data.Vector.Unboxed qualified as V

-- | >>> :main
-- 27229269
-- 26857164
main :: IO ()
IO ()
main =
  do [Char]
inp <- [format|2019 16 %s%n|]
     let ns :: Vector Int
ns = [Char] -> Vector Int
digits [Char]
inp

     [Char] -> IO ()
putStrLn ([Char] -> IO ()) -> [Char] -> IO ()
forall a b. (a -> b) -> a -> b
$ (Int -> [Char]) -> [Int] -> [Char]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Int -> [Char]
forall a. Show a => a -> [Char]
show ([Int] -> [Char]) -> [Int] -> [Char]
forall a b. (a -> b) -> a -> b
$ Vector Int -> [Int]
forall a. Unbox a => Vector a -> [a]
V.toList (Vector Int -> [Int]) -> Vector Int -> [Int]
forall a b. (a -> b) -> a -> b
$ Int -> Vector Int -> Vector Int
forall a. Unbox a => Int -> Vector a -> Vector a
V.take Int
8 (Vector Int -> Vector Int) -> Vector Int -> Vector Int
forall a b. (a -> b) -> a -> b
$ (Vector Int -> Vector Int) -> Vector Int -> [Vector Int]
forall a. (a -> a) -> a -> [a]
iterate (Int -> Vector Int -> Vector Int
fft Int
0) Vector Int
ns [Vector Int] -> Int -> Vector Int
forall a. HasCallStack => [a] -> Int -> a
!! Int
100

     let offset :: Int
offset = [Char] -> Int
forall a. Read a => [Char] -> a
read (Int -> [Char] -> [Char]
forall a. Int -> [a] -> [a]
take Int
7 [Char]
inp)

     let ns' :: Vector Int
ns' = [Vector Int] -> Vector Int
forall a. Unbox a => [Vector a] -> Vector a
V.concat (Int -> Vector Int -> [Vector Int]
forall a. Int -> a -> [a]
replicate Int
10000 Vector Int
ns)
     [Char] -> IO ()
putStrLn ([Char] -> IO ()) -> [Char] -> IO ()
forall a b. (a -> b) -> a -> b
$ (Int -> [Char]) -> [Int] -> [Char]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Int -> [Char]
forall a. Show a => a -> [Char]
show ([Int] -> [Char]) -> [Int] -> [Char]
forall a b. (a -> b) -> a -> b
$ Vector Int -> [Int]
forall a. Unbox a => Vector a -> [a]
V.toList (Vector Int -> [Int]) -> Vector Int -> [Int]
forall a b. (a -> b) -> a -> b
$ Int -> Vector Int -> Vector Int
forall a. Unbox a => Int -> Vector a -> Vector a
V.take Int
8 (Vector Int -> Vector Int) -> Vector Int -> Vector Int
forall a b. (a -> b) -> a -> b
$ Int -> Vector Int -> Vector Int
forall a. Unbox a => Int -> Vector a -> Vector a
V.drop Int
offset (Vector Int -> Vector Int) -> Vector Int -> Vector Int
forall a b. (a -> b) -> a -> b
$ (Vector Int -> Vector Int) -> Vector Int -> [Vector Int]
forall a. (a -> a) -> a -> [a]
iterate (Int -> Vector Int -> Vector Int
fft Int
offset) Vector Int
ns' [Vector Int] -> Int -> Vector Int
forall a. HasCallStack => [a] -> Int -> a
!! Int
100

digits :: String -> V.Vector Int
digits :: [Char] -> Vector Int
digits = [Int] -> Vector Int
forall a. Unbox a => [a] -> Vector a
V.fromList ([Int] -> Vector Int) -> ([Char] -> [Int]) -> [Char] -> Vector Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Char -> Int) -> [Char] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map Char -> Int
digitToInt

fft :: Int -> V.Vector Int -> V.Vector Int
fft :: Int -> Vector Int -> Vector Int
fft Int
offset Vector Int
xs = Int -> (Int -> Int) -> Vector Int
forall a. Unbox a => Int -> (Int -> a) -> Vector a
V.generate (Vector Int -> Int
forall a. Unbox a => Vector a -> Int
V.length Vector Int
xs) Int -> Int
one
  where
    n :: Int
n = Vector Int -> Int
forall a. Unbox a => Vector a -> Int
V.length Vector Int
xs
    ps :: Vector Int
ps = (Int -> Int -> Int) -> Int -> Vector Int -> Vector Int
forall a b.
(Unbox a, Unbox b) =>
(a -> b -> a) -> a -> Vector b -> Vector a
V.scanl Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) Int
0 Vector Int
xs
    factors :: Int -> [Region]
factors Int
i = (Region -> Bool) -> [Region] -> [Region]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (\(Region Int
_ Int
a Int
_) -> Int
a Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n) (Int -> [Region]
regions Int
i)

    one :: Int -> Int
one Int
i
      | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
offset = Int
0
      | Bool
otherwise = Int -> Int
forall a. Num a => a -> a
abs (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [ Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Vector Int
ps Vector Int -> Int -> Int
forall a. Unbox a => Vector a -> Int -> a
V.! Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
n Int
end Int -> Int -> Int
forall a. Num a => a -> a -> a
- Vector Int
ps Vector Int -> Int -> Int
forall a. Unbox a => Vector a -> Int -> a
V.! Int
start)
                               | Region Int
m Int
start Int
end <- Int -> [Region]
factors Int
i]
                          Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` Int
10

data Region = Region !Int !Int !Int
  deriving Int -> Region -> [Char] -> [Char]
[Region] -> [Char] -> [Char]
Region -> [Char]
(Int -> Region -> [Char] -> [Char])
-> (Region -> [Char])
-> ([Region] -> [Char] -> [Char])
-> Show Region
forall a.
(Int -> a -> [Char] -> [Char])
-> (a -> [Char]) -> ([a] -> [Char] -> [Char]) -> Show a
$cshowsPrec :: Int -> Region -> [Char] -> [Char]
showsPrec :: Int -> Region -> [Char] -> [Char]
$cshow :: Region -> [Char]
show :: Region -> [Char]
$cshowList :: [Region] -> [Char] -> [Char]
showList :: [Region] -> [Char] -> [Char]
Show

regions :: Int -> [Region]
regions :: Int -> [Region]
regions Int
i = Int -> [Region]
go Int
0
  where
    n :: Int
n = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
    go :: Int -> [Region]
go Int
offset = Int -> Int -> Int -> Region
Region Int
1 (Int
offset Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i) (Int
offset Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n)
              Region -> [Region] -> [Region]
forall a. a -> [a] -> [a]
: Int -> Int -> Int -> Region
Region (-Int
1) (Int
offset Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Int
offset Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n)
              Region -> [Region] -> [Region]
forall a. a -> [a] -> [a]
: Int -> [Region]
go (Int
offset Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
4 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
n)