1 {-# LANGUAGE OverloadedStrings #-}
3 -- Using a summed-area table, e.g. see https://en.wikipedia.org/wiki/Summed-area_table
6 import qualified Data.Map.Strict as M
7 import Data.Map.Strict ((!))
8 import Data.Ord (comparing)
10 type Coord = (Integer, Integer) -- x, y
11 type Grid = M.Map Coord Integer
17 let g = makeGrid serialNumber
22 part1 grid = keyOfMaxValue sg
23 where sg = allSubCellPower 3 grid
25 part2 grid = maximumBy (comparing snd) [bestInGrid size grid | size <- [3..300]]
27 makeGrid :: Integer -> Grid
28 -- makeGrid key = M.fromList [((x, y), powerLevel x y key) | x <- [1..300], y <- [1..300] ]
29 makeGrid key = foldl' addSummedArea M.empty [((x, y), powerLevel x y key) | x <- [0..300], y <- [0..300] ]
31 addSummedArea :: Grid -> ((Integer, Integer), Integer) -> Grid
32 addSummedArea grid ((x, y), power) = M.insert (x, y) (power + upper + left - upperLeft) grid
33 where upper = M.findWithDefault 0 (x-1, y) grid
34 left = M.findWithDefault 0 (x, y-1) grid
35 upperLeft = M.findWithDefault 0 (x-1, y-1) grid
38 powerLevel :: Integer -> Integer -> Integer -> Integer
41 powerLevel x y key = ((interim `div` 100) `mod` 10) - 5
43 interim = ((rackID) * y + key) * rackID
45 subCellPower :: Integer -> Integer -> Integer -> Grid -> Integer
46 -- subCellPower size x y grid = sum [grid!(sx, sy) | sx <- [x..(x+size-1)], sy <- [y..(y+size-1)]]
47 subCellPower size x0 y0 grid = grid!(x,y) + grid!(x',y') - grid!(x,y') - grid!(x',y)
53 allSubCellPower :: Integer -> Grid -> Grid
54 allSubCellPower size grid = M.fromList [((x, y), subCellPower size x y grid)| x <- [1..(301-size)], y <- [1..(301-size)]]
57 keyAndMaxValue :: Ord b => M.Map a b -> (a, b)
58 keyAndMaxValue m = M.foldrWithKey mergeKV (M.findMin m) m
59 where mergeKV k v (bestK, bestV) =
60 if v > bestV then (k, v) else (bestK, bestV)
62 keyOfMaxValue :: Ord b => M.Map a b -> a
63 keyOfMaxValue m = fst $ keyAndMaxValue m
65 bestInGrid :: Integer -> Grid -> ((Integer, Integer, Integer), Integer)
66 bestInGrid size grid = ((x, y, size), p)
67 where ((x, y), p) = keyAndMaxValue $ allSubCellPower size grid