Day 12 was the final day of this year's Advent of Code, and is the traditional only-one-part problem.

This is a polyomino-tiling problem, a variant of the exact cover problem, which is known to be NP-hard, and therefore there's no feasible algorithm to solve the general problem in a sensible time. But that's a problem to tackle in a bit. First is to read the input file.

Representation and Parsing

The input file is a complex thing. The first part is a description of some polyomino shapes. The second part is a set of regions to pack those polyominos into.

0:
###
##.
##.

1:
###
##.
.##

2:
.##
###
##.

3:
##.
###
##.

4:
###
#..
###

5:
###
.#.
###

4x4: 0 0 0 0 2 0
12x5: 1 0 1 0 2 2
12x5: 1 0 1 0 3 2

Representing these follows the data. A Tile is a Set of Positions. A TileSet is a Map from tile ID to Tile. A Region is a record storing the region's size and quantities of presents to pack into that region.

type Position = V2 Int -- row, column
type Tile = S.Set Position
type TileSet = M.Map Int Tile

data Region = Region { regionSize :: Position, presentQuantities :: [Int]} 
  deriving (Show, Eq)

Parsing the file is complex, with the need to detect all the blank lines and convert the ASCII-art images into sets of positions. That means a mix of straight parsing with Attoparsec and a more standard function to read the tile descriptions.

tilesRegionsP = (,) <$> tilesP <* blankLineP <*> regionsP
blankLineP = endOfLine *> endOfLine

tilesP = M.fromList <$> tileP `sepBy` blankLineP
tileP = (,) <$> decimal <* ":" <* endOfLine <*> tileGridP
tileGridP = gridify <$> tileRowP `sepBy` endOfLine
tileRowP = many1 tileCharP
tileCharP = (True <$ char '#') <|> (False <$ char '.')

gridify rows = S.unions [rowify r row | (r, row) <- zip [0..] rows]
  where rowify r row = S.fromList [V2 r c | (c, cell) <- zip [0..] row, cell]

regionsP = regionP `sepBy` endOfLine
regionP = Region <$> sizeP <* ": " <*> quantitiesP
sizeP = V2 <$> decimal <* "x" <*> decimal
quantitiesP = decimal `sepBy` " "

This is another case where the type system saved me. My first attempts didn't compile because of some mismatched types. Once I sorted those, the parser worked perfectly first time.

Solving the problem

I'll admit, I read the "trick" for solving this puzzle before I had to attempt it. The general problem is too difficult to solve, so you're not expected to solve that general problem. Instead, the actual task is to find the area of each region, and the total area occupied by all the presents in that region. If the presents take less area than available, assume they'll fit somehow.

That means I need to add up the area of all the presents in a region and compare it to the region size.

part1 :: TileSet -> [Region] -> Int
part1 tiles regions = length $ filter (allowed tiles) regions

allowed :: TileSet -> Region -> Bool
allowed tiles region = occupied <= available
  where occupied = occupiedSpaces tiles region
        V2 r c = region.regionSize
        available = r * c

occupiedSpaces :: TileSet -> Region -> Int
occupiedSpaces tiles region = 
  sum [ n * (S.size $ tiles M.! t) | (t, n) <- zip [0..] region.presentQuantities ]

And that's it. Day 12 solved, Advent of Code 2025 complete, 524 stars total.

Many thanks to Eric Wastl and team for another excellent year of puzzles.

Code

You can get the code from Codeberg.