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

<https://adventofcode.com/2018/day/11>

This solution uses dynamic programming to efficiently compute
the area of an arbitrary square on the power-cell grid.

This efficiency is achieved using a summed-area table.
<https://en.wikipedia.org/wiki/Summed-area_table>

Once we've computed this table we're able compute the sum of
the elements contained in an arbitrary rectangle via addition
and subtraction of 4 elements.

-}
module Main (main) where

import Advent.Coord (Coord(C))
import Advent.Format (format)
import Data.Array.Unboxed qualified as A
import Data.Foldable (foldl')
import Data.List (intercalate)

type Grid = A.UArray Coord Int

dim :: Int
dim :: Int
dim = Int
300

-- | Print the answers to day 11
--
-- >>> :main
-- 241,40
-- 166,75,12
main :: IO ()
IO ()
main =
  do Int
serial <- [format|2018 11 %u%n|]
     let table :: Grid
table = (Coord -> Int) -> Grid
summedAreaTable (Int -> Coord -> Int
powerLevel Int
serial)
     String -> IO ()
putStrLn (Grid -> String
part1 Grid
table)
     String -> IO ()
putStrLn (Grid -> String
part2 Grid
table)

-- | Compute the position of the largest-valued 3-square
--
-- >>> part1 (summedAreaTable (powerLevel 18))
-- "33,45"
-- >>> part1 (summedAreaTable (powerLevel 42))
-- "21,61"
part1 :: Grid -> String
part1 :: Grid -> String
part1 Grid
areas =
  case Grid -> Int -> Int -> (Coord, Int)
maximumSquare Grid
areas Int
3 Int
3 of
    (C Int
y Int
x, Int
_) -> String -> [String] -> String
forall a. [a] -> [[a]] -> [a]
intercalate String
"," ((Int -> String) -> [Int] -> [String]
forall a b. (a -> b) -> [a] -> [b]
map Int -> String
forall a. Show a => a -> String
show [Int
x,Int
y])    

-- | Compute the position and size of the largest-valued square on the grid
--
-- >>> part2 (summedAreaTable (powerLevel 18))
-- "90,269,16"
-- >>> part2 (summedAreaTable (powerLevel 42))
-- "232,251,12"
part2 :: Grid -> String
part2 :: Grid -> String
part2 Grid
areas =
  case Grid -> Int -> Int -> (Coord, Int)
maximumSquare Grid
areas Int
1 Int
dim of
    (C Int
y Int
x, Int
s) -> String -> [String] -> String
forall a. [a] -> [[a]] -> [a]
intercalate String
"," ((Int -> String) -> [Int] -> [String]
forall a b. (a -> b) -> [a] -> [b]
map Int -> String
forall a. Show a => a -> String
show [Int
x,Int
y,Int
s])

-- | Compute power level of power cell given the cells coordinate
-- and the player's serial number.
--
-- >>> powerLevel 8 (C 5 3)
-- 4
-- >>> powerLevel 57 (C 79 122)
-- -5
-- >>> powerLevel 39 (C 196 217)
-- 0
-- >>> powerLevel 71 (C 153 101)
-- 4
powerLevel ::
  Int   {- ^ serial number   -} ->
  Coord {- ^ grid coordinate -} ->
  Int   {- ^ power level     -}
powerLevel :: Int -> Coord -> Int
powerLevel Int
serial (C Int
y Int
x) = (Int
rackid Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
y Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
serial) Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
rackid Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
100 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
10 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
5
  where
    rackid :: Int
rackid = Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
10

-- | Compute the coordinates and size of the square on the
-- given Grid that maximizes the sum of the contained power levels.
maximumSquare ::
  Grid         {- ^ summed area grid              -} ->
  Int          {- ^ candidate size lower bound    -} ->
  Int          {- ^ candidate size upper bound    -} ->
  (Coord, Int) {- ^ coordinate and size of square -}
maximumSquare :: Grid -> Int -> Int -> (Coord, Int)
maximumSquare Grid
areas Int
sizelo Int
sizehi =
  ((Coord, Int), Int) -> (Coord, Int)
forall a b. (a, b) -> a
fst (((Coord, Int), Int) -> (Coord, Int))
-> ((Coord, Int), Int) -> (Coord, Int)
forall a b. (a -> b) -> a -> b
$ [((Coord, Int), Int)] -> ((Coord, Int), Int)
maximize
    [((Int -> Int -> Coord
C Int
y Int
x, Int
size), Int
area)
      | Int
size <- [Int
sizelo .. Int
sizehi]
      , Int
x    <- [Int
1 .. Int
dimInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sizeInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1]
      , Int
y    <- [Int
1 .. Int
dimInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sizeInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1]
      , let !area :: Int
area = Grid -> Coord -> Int -> Int -> Int
rectangleSum Grid
areas (Int -> Int -> Coord
C Int
y Int
x) Int
size Int
size
      ]

  -- I'm using the loops package here because it saves time
  -- over generating a large list. In addition, maximumBy
  -- is less performant than writing maximize out with a strict
  -- fold.
  where
    maximize :: [((Coord, Int), Int)] -> ((Coord, Int), Int)
maximize = (((Coord, Int), Int) -> ((Coord, Int), Int) -> ((Coord, Int), Int))
-> ((Coord, Int), Int)
-> [((Coord, Int), Int)]
-> ((Coord, Int), Int)
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\((Coord, Int), Int)
x ((Coord, Int), Int)
y -> if ((Coord, Int), Int) -> Int
forall a b. (a, b) -> b
snd ((Coord, Int), Int)
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> ((Coord, Int), Int) -> Int
forall a b. (a, b) -> b
snd ((Coord, Int), Int)
y then ((Coord, Int), Int)
x else ((Coord, Int), Int)
y) ((Int -> Int -> Coord
C Int
0 Int
0, Int
0), Int
forall a. Bounded a => a
minBound)

-- | Compute the sum of the power levels contained in a rectangle
-- specified by its top-left corner coordinate, width, and height.
rectangleSum ::
  Grid  {- ^ summed area grid              -} ->
  Coord {- ^ top-left corner of rectangle  -} ->
  Int   {- ^ rectangle width               -} ->
  Int   {- ^ rectangle height              -} ->
  Int   {- ^ sum of power levels in region -}
rectangleSum :: Grid -> Coord -> Int -> Int -> Int
rectangleSum Grid
areas (C Int
y Int
x) Int
w Int
h
  = Grid
areas Grid -> Coord -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
A.! Int -> Int -> Coord
C (Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
hInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
wInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
  Int -> Int -> Int
forall a. Num a => a -> a -> a
- Grid
areas Grid -> Coord -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
A.! Int -> Int -> Coord
C (Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
hInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int
x  Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
  Int -> Int -> Int
forall a. Num a => a -> a -> a
- Grid
areas Grid -> Coord -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
A.! Int -> Int -> Coord
C (Int
y  Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
wInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
  Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Grid
areas Grid -> Coord -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
A.! Int -> Int -> Coord
C (Int
y  Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int
x  Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

-- | Compute the summed-area table given a function that maps
-- a coordinate to its value. This table can be used with 'rectangleSum'
-- to efficiently compute the area of a rectangular region of the grid.
--
-- Each position in this grid is the sum of the values of all power
-- levels above and to the left of the current position (inclusive).
--
-- See the module header for more information about summed-area tables
-- and what we're doing with one.
summedAreaTable ::
  (Coord -> Int) {- ^ value for coordinate -} ->
  Grid           {- ^ summed-area table    -}
summedAreaTable :: (Coord -> Int) -> Grid
summedAreaTable Coord -> Int
f = Array Coord Int -> Grid
forall (a :: * -> * -> *) e (a' :: * -> * -> *) i.
(IArray a e, IArray a' e, Ix i) =>
a i e -> a' i e
convert Array Coord Int
table -- convert to unboxed array
  where
  -- table is boxed to allow self-reference in definition
  table :: A.Array Coord Int
  table :: Array Coord Int
table = (Coord, Coord) -> [(Coord, Int)] -> Array Coord Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
(i, i) -> [(i, e)] -> a i e
A.array (Int -> Int -> Coord
C Int
0 Int
0, Int -> Int -> Coord
C Int
dim Int
dim)
        ([(Coord, Int)] -> Array Coord Int)
-> [(Coord, Int)] -> Array Coord Int
forall a b. (a -> b) -> a -> b
$ [[(Coord, Int)]] -> [(Coord, Int)]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [ [ (Int -> Int -> Coord
C Int
0 Int
z, Int
0), (Int -> Int -> Coord
C Int
z Int
0, Int
0)] | Int
z <- [Int
0..Int
dim]]
        [(Coord, Int)] -> [(Coord, Int)] -> [(Coord, Int)]
forall a. [a] -> [a] -> [a]
++
        [ ( Int -> Int -> Coord
C Int
y Int
x
          , Coord -> Int
f (Int -> Int -> Coord
C Int
y Int
x)
          Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Array Coord Int
table Array Coord Int -> Coord -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
A.! Int -> Int -> Coord
C  Int
y    (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
          Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Array Coord Int
table Array Coord Int -> Coord -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
A.! Int -> Int -> Coord
C (Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)  Int
x
          Int -> Int -> Int
forall a. Num a => a -> a -> a
- Array Coord Int
table Array Coord Int -> Coord -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
A.! Int -> Int -> Coord
C (Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
          )
        | Int
x <- [Int
1..Int
dim]
        , Int
y <- [Int
1..Int
dim]
        ]

-- | Convert between different array representations.
convert :: (A.IArray a e, A.IArray a' e, A.Ix i) => a i e -> a' i e
convert :: forall (a :: * -> * -> *) e (a' :: * -> * -> *) i.
(IArray a e, IArray a' e, Ix i) =>
a i e -> a' i e
convert a i e
a = (i, i) -> [(i, e)] -> a' i e
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
(i, i) -> [(i, e)] -> a i e
A.array (a i e -> (i, i)
forall i. Ix i => a i e -> (i, i)
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> (i, i)
A.bounds a i e
a) (a i e -> [(i, e)]
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> [(i, e)]
A.assocs a i e
a)