「碰撞了幾分鐘後，你走進一個寬敞、明亮、滿是聖誕樹的洞穴！」
本文翻譯自英文原文。
Github: GCaggianese/AoC-2025/D12
題目 第 12 天：Christmas Tree Farm
這個專案解決小型網格上的受限 packing problem。
給定：
- 一組固定的 3×3 binary pieces（
#= 佔用，.= 空） - 一系列 board sizes
- 對每個 board size，一個或多個 scenarios，指定每種 piece 必須放幾份
程式會判斷哪些 scenarios 可行，也就是 required pieces 是否能在 board 上 不重疊地放置，允許旋轉但不允許鏡射。
問題結構
輸入分成兩個邏輯區段。
1. Piece definitions
每個 piece 定義為 3×3 grid：
0:
###
##.
##.
1:
###
##.
.##
Pieces 依出現順序編號（0, 1, 2, ...）。
內部表示：
#-> 1.-> 0- 每個 piece 表示為 occupied coordinates 的集合
2. Requirement scenarios
每行為某個 board size 定義一個 scenario：
4x4: 0 0 0 0 2 0
12x5: 1 0 1 0 2 2
12x5: 1 0 1 0 3 2
意義：
- Board size 是
HxW - 數字指定每個 piece 要放幾份
- 多行使用相同 board size 是獨立 scenarios，不是錯誤
演算法概覽
這不是幾何 solver。所有東西都化約成 bitmask logic。
核心想法
- Board 上每個 cell 對應到整數中的一個 bit
- Piece 的一種 placement 是一個 bitmask，occupied cells 對應的 bits 會被設為 1
- 兩個 placements 重疊 iff
mask1 & mask2 != 0
步驟
- 將每個 3×3 piece 轉成座標集合
- 產生所有唯一旋轉（0°、90°、180°、270°）
- 對給定 board size，產生每個 piece 的所有合法 placements
- 將每個 placement 轉成 board-sized bitmask
-
對每個 scenario：
- 將 piece counts 展開成 piece IDs 列表
- 依 placement 數量排序 pieces（fail-fast heuristic）
- 使用 DFS + memoization 嘗試在不重疊的情況下放置所有 pieces
為什麼用 Bitmasks?
它們把空間推理變成布林代數。
- 重疊檢查：
O(1) - 狀態 memoization：
(piece_index, occupied_mask) - 清楚分離 geometry 與 search
這是以下問題的標準方法：
- Polyomino tiling
- Exact cover problems
- 小型網格上的 constraint satisfaction
Python 實作
建立環境：
mamba env create -f environment.yml
mamba activate D12
執行 solver：
python -m D12
它會：
- 解析
input.txt - 列出所有 pieces
- 列出所有 requirement scenarios
- 印出有多少 scenarios 可行
- 輸出可行 cases 的 indices
筆記與限制
- Pieces 永遠是 3×3
- 允許旋轉，不允許鏡射
- Boards 是空的（沒有 blocked cells）
- Solver 檢查的是是否存在解，不是解的數量