AoC1811p2.hs

import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU

power :: Int -> Int -> Int -> Int
power serial x y = hundreds - 5
  where
    hundreds = (multed `div` 100) `mod` 10
    multed = rackId * added
    added = serial + base
    base = rackId * y
    rackId = x + 10

pmemo :: Int -> (Int, (Int, Int, Int))
pmemo serial = maximum allVals
  where
    allVals = [ (get (x, y, n), (x, y, n))
              | n <- [0 .. 300], y <- [1.. 301 - n], x <- [1.. 301 - n] ]

    p0 = VU.replicate (301 * 301) 0
    p1 = VU.fromList [ power serial x y | y <- [1..300], x <- [1..300]]
    p300 = VU.singleton $ VU.sum p1

    table :: V.Vector (VU.Vector Int)
    table = V.fromList $ [p0, p1] ++ map buildTable [2..299] ++ [p300]

    coord n x y | x > 0 && x <= mult && y > 0 && y <= mult =
                      (x - 1) + (y - 1) * mult
                | otherwise = error $ "bad coords " ++ show (n,x,y)
      where
        mult = 301 - n
    get (x, y, n) = (table V.! n) VU.! coord n x y

    buildTable n = VU.fromList [ cost x y
                               | y <- [1 .. 301 - n], x <- [1 .. 301 - n]]
      where
        cost x y = get (x, y, n - 1)
                 + get (x + 1, y + 1, n - 1)
                 + get (x + n - 1, y, 1)
                 + get (x, y + n - 1, 1)
                 - get (x + 1, y + 1, n - 2)

main :: IO ()
main = print $ pmemo 18

{-

~/aoc/11$ ghc -O2 AoC1811p2.hs
[1 of 1] Compiling Main             ( AoC1811p2.hs, AoC1811p2.o )
Linking AoC1811p2 ...
~/aoc/11$ time ./AoC1811p2
(113,(90,269,16))

real    0m2.938s
user    0m2.172s
sys     0m0.750s

-}