Advent of Code 2025 - Day 12

bjorng

Erlang Core Team

My solution first checks whether the presents can fit into a region based on area alone. Turns out that eliminated more than half of the regions. I then started to design in my head a brute-force algorithm to check the other regions. Before implementing it, though, I thought that I should check my solution on the Advent of Code site. I thought that I would get “this is not correct; it is too high”, but it turned out to be the correct answer.

defmodule Day12 do
  def part1(input) do
    {presents, regions} = parse(input)

    regions
    |> Enum.reject(fn region ->
      presents_fit?(region, presents)
    end)
    |> Enum.count
  end

  defp presents_fit?(region, presents) do
    num_units = Enum.map(presents, fn {index, [shape | _]} ->
      Enum.reduce(shape, [], &(&1++&2))
      |> Enum.count(&(&1 === ?\#))
      |> then(&{index, &1})
    end)
    |> Map.new

    {{width, height}, qs} = region
    area = width * height

    qs
    |> Enum.with_index
    |> Enum.map(fn {q, index} ->
      q * Map.get(num_units, index)
    end)
    |> Enum.sum
    |> then(fn needed ->
      if needed > area do
        # Can't possibly fit.
        true
      else
        # Might fit; must check.
        brute_force_solution(region, presents)
      end
    end)
  end

  defp brute_force_solution(_region, _presents) do
    # Turns out that for all inputs the presents will always fit.
    false
  end

  defp rot(grid) do
    Enum.zip_with(grid, &Enum.reverse/1)
  end

  defp hflip(grid) do
    Enum.map(grid, &Enum.reverse/1)
  end

  defp vflip(grid) do
    Enum.reverse(grid)
  end

  defp transpose(list) do
    Enum.zip_with(list, &Function.identity/1)
  end

  defp parse(input) do
    {presents, [regions]} = Enum.split(input, length(input) - 1)

    presents = Enum.map(presents, fn present ->
      [index | grid] = String.split(present, "\n", trim: true)

      grid = Enum.map(grid, &String.to_charlist/1)

      grids = Enum.flat_map_reduce(1..4, grid, fn _, grid ->
        {[grid, hflip(grid), vflip(grid)], rot(grid)}
      end)
      |> elem(0)
      |> Enum.uniq

      index = index
      |> String.trim(":")
      |> String.to_integer

      if true do
        IO.puts("#{index}:")
        grids
        |> transpose
        |> Enum.each(fn grid ->
          Enum.each(grid, &IO.write("#{&1}  "))
          IO.puts ""
        end)
        IO.puts ""
      end

      {index, grids}
    end)

    regions = regions
    |> String.split("\n", trim: true)
    |> Enum.map(fn region ->
      [size, qs] = String.split(region, ": ")

      size = size
      |> String.split("x")
      |> Enum.map(&String.to_integer(&1))
      |> List.to_tuple

      qs = String.split(qs, " ")
      |> Enum.map(&String.to_integer(&1))
      {size, qs}
    end)
    |> Enum.sort

    {presents, regions}
  end
end

6 comments

#advent-of-code #2025

1 566 6

2025-12-12 18:44:28 UTC

Showing Posts 1 to 6

Show Best Posts
Show All (oldest first)
Show All (newest first)

lud

Hahaha I just did that too, and did not even implement the whole thing.

Can you tell me much time the real solution takes? I was afraid because I feel like shapes can be arranged in any order, multiplied by the 4 rotations, 4 flipped rotations, and at any index. I suck at maths but that felt like billions of billions of possibilities because of the lack of ordering.

Post #1

hauleth

Everyone did it that way, as problem as stated (even in simplified form where every present is rectangle) is NP-hard. So good luck, have fun, you will probably need to wait till thermal death of the Universe to see any progress.

Parser

{areas, boxes} =
  puzzle_input
  |> String.split("\n\n")
  |> List.pop_at(-1)

areas =
  areas
  |> String.split("\n")
  |> Enum.map(fn raw ->
    [area | counts] = String.split(raw)

    area =
      area
      |> String.trim(":") 
      |> String.split("x")
      |> Enum.map(&String.to_integer/1)
      |> Enum.product()

    counts = Enum.map(counts, &String.to_integer/1)

    {area, counts}
  end)

boxes =
  boxes
  |> Enum.map(fn <<_::binary-3>> <> rest ->
    rest
    |> String.to_charlist()
    |> Enum.count(&(&1 == ?#))
  end)

Part 1

areas
|> Enum.count(fn {max, counts} ->
  counts
  |> Enum.zip_with(boxes, &*/2)
  |> Enum.sum()
  |> then(& &1 <= max)
end)

Post #2

lud

Yeah ok that’s what I was thinking

Post #3

bjorng

Erlang Core Team

I just designed it in my head. I never implemented it, but I think would have worked and it might be fun to implement.

No, I don’t think there are billions and billions of possibilities.

My idea was to do a breadth first search using a priority queue. The frontier would be the unoccupied positions next to all previously placed shapes, and it would start out at a corner. The priority queue is ordered by the area covered by all previously placed shapes. Therefore, if a solution is found, it will be a solution that covers the least number of units.

There are not always eight possible orientations. One shape had only two possible orientations, three had four orientations, and two had eight (for my input). Some orientations can be excluded when placed if there would be an embedded unreachable unit.

According to the page you linked to, the problem is NP-hard if the rectangles being packed have varying width and height. As far as I understand, packing identical rectangles in a rectangle is not NP-hard.

Post #4

lud

And for each state in the queue you must enqueue a new state for every piece*permutation. It can grow quickly. In aoc in general I just keep 10k or 20k items in the queue and it works.

I found some people with the actual solution claiming less than 3 minutes runtime in python so I guess it’s not that hard. Gosh I’m way too lazy to give it a try now

Post #5

rvnash

Yeah, like others, my “solution” isn’t worth posting here because it only checks to see if the number of tiles can fit in provided area. It doesn’t look at shapes, flips, or rotations. Good enough, I’m done.

I just wanted to thank @lud , @bjorng , @hauleth and others here for providing your code for me to look at. All of you have such great and elegant understanding of functional programming and Elixir, I feel like I learn a lot reading your code. Now if I could only apply what I learn in my own code . Anyway thanks.

Someday, after the holidays, I’m going to go back to Day 10 Part 2. That’s the only one I could not crack on my own, having to resort to a third-party solver. I have some more ideas that I want to try.

Happy Holidays!

Post #6

— All posts loaded —