2 votes

Day 12: Christmas Tree Farm

Automatically posted
Tags: advent of code.2025

Today's problem description: https://adventofcode.com/2025/day/12

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

6 comments

  1. [3]
    lily
    Link
    This was a strange one to end things off with. The problem, as described, seems incredibly hard - I'm not sure at all how I'd go about solving it. I spent about half an hour at first hopelessly...

    This was a strange one to end things off with. The problem, as described, seems incredibly hard - I'm not sure at all how I'd go about solving it. I spent about half an hour at first hopelessly writing a naive bruteforce search solution that had no chance of ever finishing, just to try and make some kind of progress. It turns out the input is really, really convenient, though, and so just checking for the absolute upper bound on required space is enough (not for the test input, only the real input). This seems to be intentional, given the puzzle's hover text. When taking advantage of that, the puzzle becomes trivial; the shape definitions can actually be completely ignored, even. Almost all of my code is just for parsing the input.

    Solution (Lily) 
    print("Part 1: {}".format(
    File
        .read_to_string("inputs/day_12.txt")
        .split("\n\n")[-1]
        .split("\n")
        .count(|line|
            var parts = line.split(": ")
            var size = parts[0].split("x")

            parts[1].split(" ").map(|count| count.parse_i().unwrap() * 9).fold(
                0, (|sum, count| sum + count)
            ) <= size[0].parse_i().unwrap() * size[1].parse_i().unwrap()
        )
))
    2 votes
    1. [2]
      jzimbel
      Link Parent
      Wait, where's the hover text? I can't find any, even after poking around in the page markup.

      Wait, where's the hover text? I can't find any, even after poking around in the page markup.

      1. lily
        Link Parent
        It's on the word "help" in the part 2 description. There's hidden hover text somewhere in the text for every puzzle; it's highlighted once you get all the stars.

        It's on the word "help" in the part 2 description. There's hidden hover text somewhere in the text for every puzzle; it's highlighted once you get all the stars.

        1 vote
  2. DeaconBlue
    Link
    LOL what a silly final puzzle. I went with an equally silly one-liner. Part 1 Console.WriteLine(File.ReadAllLines("redacted").Where(x => x.Contains('x')).Where(x =>...

    LOL what a silly final puzzle. I went with an equally silly one-liner.

    Part 1 
    Console.WriteLine(File.ReadAllLines("redacted").Where(x => x.Contains('x')).Where(x => (int.Parse(x.Split(':')[0].Split('x')[0]) * int.Parse(x.Split(':')[0].Split('x')[1])) >= (x.Split(':')[1].Split(' ').Where(y => !string.IsNullOrWhiteSpace(y)).ToList().Select(y => int.Parse(y)).Sum() * 9)).Count());
  3. thecakeisalime
    Link
    "Solving" the knapsack packing problem was a huge escalation from previous days, even if today is the last day, and was dreading trying to implement that. So instead, I decided I'd start by...

    "Solving" the knapsack packing problem was a huge escalation from previous days, even if today is the last day, and was dreading trying to implement that. So instead, I decided I'd start by calculating the upper and lower bounds of what the possible answers could be, since by now I've figured out that there's often a trick with the input that you can use to optimize these solutions. I was pleasantly surprised when I found they were equal. Of course, in what has become a daily occurrence for me, I still had the wrong answer; this time it was because I reversed the inequality signs. Once I fixed that though, I had the correct solution.

    Solution [Python] 
    def parse_input(lines: list[str]) -> tuple[dict[int, list[list[str]]], list[tuple[str, list[int]]]]:
  presents = {}
  regions = []
  shape = []

  for line in lines:
    if line.endswith(':'):
      shape = []
      presents[int(line[:-1])] = shape
    
    elif line and line[0] in '#.':
      shape.append(line)
    
    elif ':' in line:
      dimension, values = line.split(':')
      values = list(map(int, values.split()))
      regions.append((dimension, values))
  return presents, regions

def get_bounds(presents: dict[int, list[list[str]]], region: tuple[str, list[int]]):
  dimensions = tuple(map(int, region[0].split('x')))
  quantities = region[1]
  area = dimensions[0] * dimensions[1]

  size = 0
  nines = 0
  for i, q in enumerate(quantities):
    size += q * sum(p.count('#') for v in presents[i] for p in v)
    nines += q * 9
  return (nines <= area, size <= area)

def part_one(presents: dict[int, list[list[str]]], regions: list[tuple[str, list[int]]]) -> tuple[int, int]:
  bounds = tuple(map(sum, zip(*(get_bounds(presents, r) for r in regions))))
  return bounds

def part_two() -> str:
  return '*'

def main() -> None:
  with open('12.in') as file:
    lines = [line.rstrip() for line in file]

  input = parse_input(lines)
  print('Part 1:', part_one(*input))
  print('Part 2:', part_two())

if __name__ == '__main__':
  main()
  4. Berdes
    Link
    I got baited soooooo hard by this problem. I started implementing a solver for the general problem, believing that maybe the dimensions where small enough that a good implementation could work....

    I got baited soooooo hard by this problem. I started implementing a solver for the general problem, believing that maybe the dimensions where small enough that a good implementation could work. Obviously, I had a very quick explosion of states while trying to find a solution for any of the regions. So I implemented some additional logic to try and eliminate states that are strictly worse than other states I generated, which still wasn't enough. So I looked at culling states that had no hope of being filled and early exiting if I found a state that could trivially finish being filled. Magically, those two last optimizations where enough... because every single input immediately fits into one of those categories.

    Also, while trying some manual inputs with feasible dimensions, I saw that my solver clearly had some bugs because it could find a solution for a 39x6 region, but not for a 40x6 with the exact same shape requirements. :|

    Anyway, if anyone is interested, here is my solution after angrily deleting all the code related to the useless solver (there are still traces of optimizations that are clearly not necessary anymore):

    Solution (Rust) 
    use aoc_2025::timed_run;
use std::io;
use std::vec::Vec;

// Bitmask of the shape. Bit 0 is the top left, bit 2 the top right and bit 8 the bottom right.
#[derive(Clone, Copy)]
struct Shape(u16);

impl Shape {
  fn parse(ls: &[String]) -> Self {
    assert_eq!(ls.len(), 4);
    let mut ret = 0;
    let mut pos = 0;
    for x in 1..4 {
      assert_eq!(ls[x].len(), 3);
      for c in ls[x].chars() {
        match c {
          '#' => ret |= 1 << pos,
          '.' => {}
          _ => panic!("unexpected char {} in shape", c),
        }
        pos += 1;
      }
    }
    Shape(ret)
  }

  #[allow(dead_code)]
  fn to_string(&self) -> String {
    let mut ret = String::new();
    let mut tmp = self.0;
    for i in 0..9 {
      ret.push(if tmp & 1 == 1 { '#' } else { '.' });
      if i == 2 || i == 5 {
        ret.push('\n');
      }
      tmp >>= 1;
    }
    ret
  }
}

struct Region {
  width: u32,
  height: u32,
  shapes_count: Vec<u32>,
}

impl Region {
  fn parse(l: &str) -> Self {
    let (size, shapes) = l.split_once(": ").unwrap();
    let (width, height) = size.split_once('x').unwrap();
    Self {
      width: width.parse().unwrap(),
      height: height.parse().unwrap(),
      shapes_count: shapes
        .split(' ')
        .map(|s| s.parse::<u32>().unwrap())
        .collect(),
    }
  }

  #[allow(dead_code)]
  fn to_string(&self) -> String {
    format!("{}x{}: {:?}", self.width, self.height, self.shapes_count)
  }

  fn trivial_fit(&self, shapes: &Vec<Shape>) -> Option<bool> {
    let num_trivial_shapes = (self.height / 3) * (self.width / 3);
    let num_required_shapes = self.shapes_count.iter().fold(0, |a, b| a + b);
    if num_required_shapes <= num_trivial_shapes {
      return Some(true);
    }
    let num_required_spots = shapes
      .iter()
      .map(|shape| shape.0.count_ones())
      .zip(self.shapes_count.iter())
      .map(|(a, b)| a * b)
      .fold(0, |a, b| a + b);
    if num_required_spots > self.height * self.width {
      return Some(false);
    }
    None
  }
}

struct Input {
  shapes: Vec<Shape>,
  regions: Vec<Region>,
}

impl Input {
  fn read_from_stdin() -> Input {
    let lines = io::stdin().lines().map(|l| l.unwrap()).collect::<Vec<_>>();
    let mut iter = lines.rsplit(|l| l == "");
    let regions = iter
      .next()
      .unwrap()
      .iter()
      .map(|r| Region::parse(r))
      .collect::<Vec<_>>();
    let shapes = iter.map(|ls| Shape::parse(ls)).rev().collect::<Vec<_>>();
    for r in &regions {
      assert_eq!(r.shapes_count.len(), shapes.len());
      assert!(r.height > 2);
      assert!(r.width > 2);
    }
    Input { shapes, regions }
  }
}

fn part1(input: &Input) -> u64 {
  let mut ret = 0;
  for r in &input.regions {
    match r.trivial_fit(&input.shapes) {
      Some(true) => ret += 1,
      Some(false) => {}
      None => panic!("Cannot trivially solve {}", r.to_string()),
    }
  }
  ret
}

fn part2(_input: &Input) -> u64 {
  0
}

fn main() {
  let input = Input::read_from_stdin();
  timed_run("Part 1", || part1(&input));
  timed_run("Part 2", || part2(&input));
}