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

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

-}
module Main where

import Advent (format)
import Advent.Coord (Coord(..), cardinal)
import Advent.Search (bfsOn)
import Data.Bits (Bits(popCount))

data Entry = Entry { Entry -> Int
entrySteps :: !Int, Entry -> Coord
entryCoord :: Coord }
  deriving (Entry -> Entry -> Bool
(Entry -> Entry -> Bool) -> (Entry -> Entry -> Bool) -> Eq Entry
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Entry -> Entry -> Bool
== :: Entry -> Entry -> Bool
$c/= :: Entry -> Entry -> Bool
/= :: Entry -> Entry -> Bool
Eq, Int -> Entry -> ShowS
[Entry] -> ShowS
Entry -> String
(Int -> Entry -> ShowS)
-> (Entry -> String) -> ([Entry] -> ShowS) -> Show Entry
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Entry -> ShowS
showsPrec :: Int -> Entry -> ShowS
$cshow :: Entry -> String
show :: Entry -> String
$cshowList :: [Entry] -> ShowS
showList :: [Entry] -> ShowS
Show)

-- | >>> :main
-- 92
-- 124
main :: IO ()
IO ()
main =
 do Int
input <- [format|2016 13 %u%n|]
    let entries :: [Entry]
entries = (Entry -> Coord) -> (Entry -> [Entry]) -> Entry -> [Entry]
forall r a. Ord r => (a -> r) -> (a -> [a]) -> a -> [a]
bfsOn Entry -> Coord
entryCoord (Int -> Entry -> [Entry]
nextEntries Int
input) Entry
initialEntry
    Int -> IO ()
forall a. Show a => a -> IO ()
print (Int -> IO ()) -> Int -> IO ()
forall a b. (a -> b) -> a -> b
$ [Int] -> Int
forall a. HasCallStack => [a] -> a
head [Int
steps | Entry Int
steps (C Int
39 Int
31) <- [Entry]
entries]
    Int -> IO ()
forall a. Show a => a -> IO ()
print (Int -> IO ()) -> Int -> IO ()
forall a b. (a -> b) -> a -> b
$ [Int] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Int] -> Int) -> [Int] -> Int
forall a b. (a -> b) -> a -> b
$ (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
50) ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$ (Entry -> Int) -> [Entry] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map Entry -> Int
entrySteps [Entry]
entries

initialEntry :: Entry
initialEntry :: Entry
initialEntry = Int -> Coord -> Entry
Entry Int
0 (Int -> Int -> Coord
C Int
1 Int
1)

isValidCoord :: Int -> Coord -> Bool
isValidCoord :: Int -> Coord -> Bool
isValidCoord Int
input (C Int
y Int
x) =
  Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 Bool -> Bool -> Bool
&& Int
y Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 Bool -> Bool -> Bool
&&
  Int -> Bool
forall a. Integral a => a -> Bool
even (Int -> Int
forall a. Bits a => a -> Int
popCount (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
3Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
y Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
input))

nextEntries :: Int -> Entry -> [Entry]
nextEntries :: Int -> Entry -> [Entry]
nextEntries Int
input (Entry Int
steps Coord
coord) =
  [Int -> Coord -> Entry
Entry (Int
stepsInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Coord
c | Coord
c <- Coord -> [Coord]
cardinal Coord
coord, Int -> Coord -> Bool
isValidCoord Int
input Coord
c]