Day 12: Christmas Tree Farm

Day 12: Christmas Tree Farm

Day 12: Christmas Tree Farm

Part 1

defmodule AdventOfCode2025Day12Part1 do
  import Bitwise

  def run(input) do
    {shapes, regions} = parse(input)
    Enum.count(regions, &fits?(&1, shapes))
  end

  defp parse(input) do
    blocks = input |> String.trim() |> String.split(~r/\r?\n\s*\r?\n/)
    {region_block, shape_blocks} = List.pop_at(blocks, -1)

    shapes =
      shape_blocks
      |> Enum.map(fn block ->
        [header | rows] = String.split(block, ~r/\r?\n/, trim: true)
        id = header |> String.trim_trailing(":") |> String.to_integer()

        cells =
          for {row, y} <- Enum.with_index(rows),
              {?#, x} <- Enum.with_index(String.to_charlist(row)),
              do: {x, y}

        {id, cells}
      end)
      |> Enum.sort_by(&elem(&1, 0))
      |> Enum.map(&elem(&1, 1))

    regions =
      region_block
      |> String.split(~r/\r?\n/, trim: true)
      |> Enum.map(fn line ->
        [w, h | counts] = Regex.scan(~r/\d+/, line) |> List.flatten()
        {String.to_integer(w), String.to_integer(h), Enum.map(counts, &String.to_integer/1)}
      end)

    {shapes, regions}
  end

  defp fits?({w, h, counts}, shapes) do
    needed =
      Enum.zip_with(shapes, counts, fn cells, count -> length(cells) * count end)
      |> Enum.sum()

    tile_size =
      shapes
      |> Enum.flat_map(fn cells -> Enum.map(cells, fn {x, y} -> max(x, y) + 1 end) end)
      |> Enum.max()

    cond do
      needed > w * h -> false
      div(w, tile_size) * div(h, tile_size) >= Enum.sum(counts) -> true
      true -> exact_fit?(shapes, counts, w, h, needed)
    end
  end

  defp orientations(cells) do
    for reflected <- [false, true], turns <- 0..3 do
      cells
      |> Enum.map(fn {x, y} ->
        point = {if(reflected, do: -x, else: x), y}
        Enum.reduce(1..turns//1, point, fn _, {a, b} -> {-b, a} end)
      end)
      |> normalize()
    end
    |> Enum.uniq()
  end

  defp normalize(cells) do
    min_x = cells |> Enum.map(&elem(&1, 0)) |> Enum.min()
    min_y = cells |> Enum.map(&elem(&1, 1)) |> Enum.min()
    cells |> Enum.map(fn {x, y} -> {x - min_x, y - min_y} end) |> Enum.sort()
  end

  defp exact_fit?(shapes, counts, w, h, needed) do
    by_cell =
      shapes
      |> Enum.with_index()
      |> Enum.reduce(%{}, fn {cells, id}, acc ->
        if Enum.at(counts, id) == 0 do
          acc
        else
          Enum.reduce(orientations(cells), acc, fn variant, acc ->
            width = variant |> Enum.map(&elem(&1, 0)) |> Enum.max() |> Kernel.+(1)
            height = variant |> Enum.map(&elem(&1, 1)) |> Enum.max() |> Kernel.+(1)

            positions =
              for y <- 0..(h - height)//1, x <- 0..(w - width)//1 do
                indices = Enum.map(variant, fn {dx, dy} -> (y + dy) * w + x + dx end)
                mask = Enum.reduce(indices, 0, fn i, mask -> mask ||| 1 <<< i end)
                {indices, mask}
              end

            Enum.reduce(positions, acc, fn {indices, mask}, acc ->
              Enum.reduce(indices, acc, fn i, acc ->
                Map.update(acc, i, [{id, mask, length(cells)}], fn list ->
                  [{id, mask, length(cells)} | list]
                end)
              end)
            end)
          end)
        end
      end)

    {result, _memo} = search(0, List.to_tuple(counts), w * h, needed, by_cell, MapSet.new())
    result
  end

  defp search(_board, _counts, _free, 0, _by_cell, memo), do: {true, memo}

  defp search(board, counts, free, needed, by_cell, memo) do
    key = {board, counts}

    if MapSet.member?(memo, key) do
      {false, memo}
    else
      cell = first_free(board, 0)

      {found, memo} =
        by_cell
        |> Map.get(cell, [])
        |> Enum.reduce_while({false, memo}, fn {id, mask, size}, {false, memo} ->
          if elem(counts, id) > 0 and (board &&& mask) == 0 do
            remaining = put_elem(counts, id, elem(counts, id) - 1)

            case search(board ||| mask, remaining, free - size, needed - size, by_cell, memo) do
              {true, memo} -> {:halt, {true, memo}}
              {false, memo} -> {:cont, {false, memo}}
            end
          else
            {:cont, {false, memo}}
          end
        end)

      {found, memo} =
        if not found and free > needed do
          search(board ||| 1 <<< cell, counts, free - 1, needed, by_cell, memo)
        else
          {found, memo}
        end

      if found, do: {true, memo}, else: {false, MapSet.put(memo, key)}
    end
  end

  defp first_free(board, cell) do
    if (board &&& 1 <<< cell) == 0, do: cell, else: first_free(board, cell + 1)
  end
end

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
"""

AdventOfCode2025Day12Part1.run(example)

Part 2

No additional code is required. Collect 23 stars by completing both parts of Days 1–11 and Part 1 of Day 12, then press the button on the puzzle page to earn the final star.