aoc/year2025/
day12.rs

1//! # Christmas Tree Farm
2//!
3//! There are 3 possibilities for each combination of region and presents.
4//!
5//! ## Best case
6//!
7//! All presents fit into the region with no overlap. Each present has its own 3x3 space.
8//! For example:
9//!
10//! ```none
11//!  AAABBBCCC
12//!  A....B.C.
13//!  AAABBBCCC
14//! ```
15//!
16//! ## Worst case
17//!
18//! The total number of tiles in the region is less than the total number of tiles in the presents,
19//! so even if the presents are packed to occupy 100% of the space, there is no possible way that
20//! they can fit. For example, the three shapes above contain 21 tiles, so they can never fit
21//! into the 6x3 region with 18 tiles below.
22//!
23//! ```none
24//!   ......
25//!   ......
26//!   ......
27//! ```
28//!
29//! ## Mixed case
30//!
31//! The presents can fit into the region with some clever arrangement. This problem is known as
32//! [polyomino tiling](https://en.wikipedia.org/wiki/Polyomino#Tiling_regions_with_sets_of_polyominoes)
33//! and is [NP-complete](https://en.wikipedia.org/wiki/NP-completeness). This is an extremely
34//! complex and challenging problem with no known polynomial-time solution.
35//!
36//! ## Solution
37//!
38//! For the *inputs provided*, all combinations of regions and presents fall into the first
39//! two cases (either trivially possible or impossible), so there is no need to even attempt
40//! the harder general case. Additionally, since each present is placed in its own 3x3 space,
41//! there is also no need to even consider the shape of the presents.
42use crate::util::iter::*;
43use crate::util::parse::*;
44
45pub fn parse(input: &str) -> &str {
46    input
47}
48
49/// Count regions that can contain the total number of presents
50/// each in their own 3x3 space with no overlap.
51pub fn part1(input: &str) -> usize {
52    input
53        .iter_unsigned::<u32>()
54        .skip(6)
55        .chunk::<8>()
56        .filter(|[w, h, presents @ ..]| (w / 3) * (h / 3) >= presents.iter().sum::<u32>())
57        .count()
58}
59
60pub fn part2(_input: &str) -> &'static str {
61    "n/a"
62}