Advent of Code 2025 in Charly

Day 12

This article is part of my series on implementing each Advent of Code 2025 challenge in my own programming language Charly.

Task

Today’s puzzle dropped us into a large cavern full of christmas trees and a bunch of differently shaped presents. The elves hand me a description of how each present is shaped, how much space is available below each christmas tree, and how many of each type of present must be placed below that tree.

For example:

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

The input starts with a list of standard present shapes. Each shape is given an index and shown as a small 2D grid of # and . characters. A # marks a unit cell that the present occupies, while . marks empty space inside the shape’s bounding box.

After the shape list comes a list of rectangular regions under the christmas trees. Each region is described by its width and height (for example 12x5), followed by a list of counts that specifies how many presents of each shape index must be placed into that region.

Presents must be placed on the region’s unit grid and cannot be stacked. Shapes may be rotated and flipped. Occupied cells (#) from different presents may not overlap, but empty cells (.) do not block anything and can be shared with other shapes.

The task is to check each region and determine whether all required presents can fit. The final answer is how many of the listed regions are solvable.

Implementation

I began my attempt by determining the minimum total number of cells that each region must contain to be able to accommodate all occupied (#) cells from all required presents. If the region doesn’t have enough space to accommodate the occupied cells, then that means there is no way we could possibly arrange all the presents to make them fit.

const input_path = ARGV[1]
const lines = readfile(input_path).lines()

const (presents, regions) = parse_input(lines)

const valid_regions = regions.filter(->(region, region_id) {
    const (size, present_ids) = region
    const (x, y) = size

    const gridArea = x * y
    const minimumRequiredArea = present_ids.map(->(count, i) {
        count * presents[i].map(->(r) [...r].sum()).sum()
    }).sum()

    gridArea >= minimumRequiredArea
})

print("there are {valid_regions.length} regions that might fit the presents")

The next step would have been to attempt to place each present, in any possible orientation, flipped horizontally and vertically, in any possible position on the grid. You then would have to iterate over all possible combinations of those factors to figure out if the region is solvable or not. This approach could’ve been implemented as a DFS search over all possible present placements.

The validation input had regions with areas up to 50x50 with hundreds of presents that had to be placed. I did some napkin calculations and figured out that this would take an astronomical amount of time.

At this point it dawned on me that I must be missing some key part of how to solve this problem. There had to be an easier way of solving this than to just search the entire space of possible present placements.

I figured it couldn’t hurt to check whether all the regions that might be solvable are indeed solvable. I copied the count of regions that might be solvable, pasted it into the solution submission field and clicked Submit.

My guess turned out to be correct. The site accepted my answer and I got the star :P. I do realize that I’ve kind of cheesed today’s puzzle, but I’m satisfied with it.

There was no second part of the puzzle, just a short message congratulating you on your success.

Changes to the stdlib / VM

Modifications:

Methods added to the standard library:

You can find the individual commits below:

Copyright © 2024 - 2025 Leonard Schütz | Attributions This post was written by a human and reviewed and proof-read by LLMs