{-# Language QuasiQuotes, TemplateHaskell, BangPatterns, BlockArguments, LambdaCase, ImportQualifiedPost #-}
{-|
Module      : Main
Description : Day 21 solution
Copyright   : (c) Eric Mertens, 2023
License     : ISC
Maintainer  : emertens@gmail.com

<https://adventofcode.com/2023/day/21>

The input cases are real super special for part 2,
don't bother thinking about them too hard, just
extrapolate and check.

-}
module Main (main) where

import Advent (getInputArray, times, ordNub, arrIx)
import Advent.Coord (Coord(..), cardinal)
import Data.Array.Unboxed (UArray, bounds, assocs, amap)

main :: IO ()
IO ()
main =
 do input <- Int -> Int -> IO (UArray Coord Char)
getInputArray Int
2023 Int
21
    let start = [Coord] -> Coord
forall a. HasCallStack => [a] -> a
head [ Coord
start | (Coord
start, Char
'S') <- UArray Coord Char -> [(Coord, Char)]
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> [(i, e)]
assocs UArray Coord Char
input]
    let input' = (Char -> Bool) -> UArray Coord Char -> UArray Coord Bool
forall (a :: * -> * -> *) e' e i.
(IArray a e', IArray a e, Ix i) =>
(e' -> e) -> a i e' -> a i e
amap (\Char
x -> Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'S' Bool -> Bool -> Bool
|| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'.') UArray Coord Char
input :: UArray Coord Bool

    print $ length $ times 64 (ordNub . concatMap (step input')) [start]

    let t0 = [Coord] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Coord] -> Int) -> [Coord] -> Int
forall a b. (a -> b) -> a -> b
$ Int -> ([Coord] -> [Coord]) -> [Coord] -> [Coord]
forall a. Int -> (a -> a) -> a -> a
times (Int
65Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
131Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
0) ([Coord] -> [Coord]
forall a. Ord a => [a] -> [a]
ordNub ([Coord] -> [Coord]) -> ([Coord] -> [Coord]) -> [Coord] -> [Coord]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Coord -> [Coord]) -> [Coord] -> [Coord]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (UArray Coord Bool -> Coord -> [Coord]
step UArray Coord Bool
input')) [Coord
start]
    let t1 = [Coord] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Coord] -> Int) -> [Coord] -> Int
forall a b. (a -> b) -> a -> b
$ Int -> ([Coord] -> [Coord]) -> [Coord] -> [Coord]
forall a. Int -> (a -> a) -> a -> a
times (Int
65Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
131Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
1) ([Coord] -> [Coord]
forall a. Ord a => [a] -> [a]
ordNub ([Coord] -> [Coord]) -> ([Coord] -> [Coord]) -> [Coord] -> [Coord]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Coord -> [Coord]) -> [Coord] -> [Coord]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (UArray Coord Bool -> Coord -> [Coord]
step UArray Coord Bool
input')) [Coord
start]
    let t2 = [Coord] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Coord] -> Int) -> [Coord] -> Int
forall a b. (a -> b) -> a -> b
$ Int -> ([Coord] -> [Coord]) -> [Coord] -> [Coord]
forall a. Int -> (a -> a) -> a -> a
times (Int
65Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
131Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) ([Coord] -> [Coord]
forall a. Ord a => [a] -> [a]
ordNub ([Coord] -> [Coord]) -> ([Coord] -> [Coord]) -> [Coord] -> [Coord]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Coord -> [Coord]) -> [Coord] -> [Coord]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (UArray Coord Bool -> Coord -> [Coord]
step UArray Coord Bool
input')) [Coord
start]

    let d01 = Int
t1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
t0
    let d12 = Int
t2 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
t1
    let d01_12 = Int
d12 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
d01

    let f Int
x = Int
t0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (Int
t1Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
t0) Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
d01_12
    print (f (26501365 `quot` 131))

step :: UArray Coord Bool -> Coord -> [Coord]
step :: UArray Coord Bool -> Coord -> [Coord]
step UArray Coord Bool
input Coord
here =
  [ Coord
here'
  | Coord
here' <- Coord -> [Coord]
cardinal Coord
here
  , let (Coord
_, C Int
ymax Int
xmax) = UArray Coord Bool -> (Coord, Coord)
forall i. Ix i => UArray i Bool -> (i, i)
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> (i, i)
bounds UArray Coord Bool
input
  , let modIt :: Coord -> Coord
modIt (C Int
y Int
x) = Int -> Int -> Coord
C (Int
y Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` (Int
ymaxInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)) (Int
x Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` (Int
xmaxInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1))
  , let hereLogical :: Coord
hereLogical = Coord -> Coord
modIt Coord
here'
  , Bool
True <- UArray Coord Bool -> Coord -> [Bool]
forall (a :: * -> * -> *) e i (f :: * -> *).
(IArray a e, Ix i, Alternative f) =>
a i e -> i -> f e
arrIx UArray Coord Bool
input Coord
hereLogical
  ]