Day 12

This input looks quite complex, so lets start by defining some types to fit the input into:

type Region = (Int, Int, [Int])

type Shape = M.Map (Int, Int) Char
area = M.size . M.filter (== '#')

Onto parsing:

import           Data.List.Split (splitOn)
import qualified Data.Map        as M

We are using <*> here, which stands for sequential application. We are applying two functions onto the input, one to parse regions and one to parse shapes:

parse :: String -> ([Shape], [Region])
parse = ((,) <$> sps <*> regs) . splitOn "\n\n"
  where
    regs = map parseReg . lines . last
    sps = map parseShape . init

Parsing a region is then simply:

parseReg :: String -> Region
parseReg l = (x, y, map read idxs)
  where
    (dims : idxs) = words l
    [x, y] = map read . splitOn "x" $ init dims

And to parse a shape (we are using a map to represent a shape):

parseShape :: String -> Shape
parseShape n =
  M.fromList
    [ ((x, y), c)
    | (x, r) <- zip [0 ..] (tail (lines n)),
      (y, c) <- zip [0 ..] r
    ]

Moving onto the solution itself.

Part 1

At first glance, this problem seems quite difficult. There is not an optimal algorithm that I know of, and backtracking with rotations could take quite a while. So it would make sense to reduce the problem space as much as possible right away. One way to do that is to simply check if all shapes can fit within their respective regions. And turns out that is sufficient to solve this day’s problem!

p1 (sps, regs) = length $ filter fits regs
  where
    fits (x, y, cs) =
      (x * y) >= sum (zipWith (*) (map area sps) cs)

Historically, the last day of AOC has always been quite simple.

Finally, a main function to wrap it all up:

main = do
  n <- parse <$> getContents
  print $ p1 n