Day 9: Movie Theater

[4]

lily

2 days, 15 hours ago

Link

Not especially happy with my solution, but it does the job. Runs in just under a second on my machine. The idea is, if none of the lines between red tiles are overlapping with the rectangle, then...

Not especially happy with my solution, but it does the job. Runs in just under a second on my machine. The idea is, if none of the lines between red tiles are overlapping with the rectangle, then the rectangle is inside the loop. The time complexity of this seems pretty bad, but I unfortunately don't have the time to figure out how to make it more efficient right now.

Solution (Lily)

import (abs) math

var tiles_x: List[Integer] = []
var tiles_y: List[Integer] = []
var tile_count = 0

for line in File.read_to_string("inputs/day_09.txt").split("\n"): {
    var parts = line.split(",")
    tiles_x.push(parts[0].parse_i().unwrap())
    tiles_y.push(parts[1].parse_i().unwrap())
    tile_count += 1
}

var lines = List.fill(tile_count, (|index|
    var next_index = index + 1
    if next_index == tile_count: {
        next_index = 0
    }

    var x1 = tiles_x[index]
    var y1 = tiles_y[index]
    var x2 = tiles_x[next_index]
    var y2 = tiles_y[next_index]

    if x1 == x2: {
        return (y1 <= y2 ? <[x1, x2, y1, y2]> : <[x1, x2, y2, y1]>)
    }

    (x1 < x2 ? <[x1, x2, y1, y2]> : <[x2, x1, y1, y2]>)
))

var max_index = tile_count - 1

var largest_area_all_tiles = 0
var largest_area_red_and_green_tiles = 0

for i in 0...max_index: {
    for j in i + 1...max_index: {
        var x1 = tiles_x[i]
        var y1 = tiles_y[i]
        var x2 = tiles_x[j]
        var y2 = tiles_y[j]

        var area = (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1)

        if area > largest_area_all_tiles: {
            largest_area_all_tiles = area
        }

        if area <= largest_area_red_and_green_tiles: {
            continue
        }

        if x1 > x2: {
            var temp = x1
            x1 = x2
            x2 = temp
        }

        if y1 > y2: {
            var temp = y1
            y1 = y2
            y2 = temp
        }

        var inside = true
        for line in lines: {
            if line[1] > x1 && line[0] < x2 && line[3] > y1 && line[2] < y2: {
                inside = false
                break
            }
        }

        if inside: {
            largest_area_red_and_green_tiles = area
        }
    }
}

print("Part 1: {}\nPart 2: {}".format(
    largest_area_all_tiles, largest_area_red_and_green_tiles
))

3 votes

[3]
Berdes
2 days, 9 hours ago
Link Parent
I thought about the same idea (checking if we're crossing lines), but I feared that it could yield false positives in cases where we have two lines without any gap between them. Something like...
I thought about the same idea (checking if we're crossing lines), but I feared that it could yield false positives in cases where we have two lines without any gap between them. Something like this:
```
0,3
2,3
2,10
3,10
3,0
5,0

   1
   |
   2------3
5---------4
|
6
```
with the inside on the right side.

As often, the inputs tend to have nice properties not mentioned in the problem statement that allow for some approaches that don't work in the general case.
2 votes
1. lily
  2 days, 8 hours ago (edited 2 days, 7 hours ago)
  Link Parent
  The general case of this would be pretty tricky, yeah (and probably pretty slow, at least with a naive approach... my solution isn't the fastest as it is). I can confirm my program returns the...
  
  The general case of this would be pretty tricky, yeah (and probably pretty slow, at least with a naive approach... my solution isn't the fastest as it is). I can confirm my program returns the wrong answer for your test input here. Since these kinds of quirks in the input are generally consistent across all inputs for a given puzzle, though, I don't mind taking advantage of them where possible.
  
  1 vote
2. jzimbel
  22 hours, 40 minutes ago
  Link Parent
  Yeah, I was worried about this and a few other possible pitfalls while working on my solution. I spent a substantial amount of time writing checks to confirm all of the following: perimeter does...
  
  Yeah, I was worried about this and a few other possible pitfalls while working on my solution.
  
  I spent a substantial amount of time writing checks to confirm all of the following:
  
  perimeter does not cross itself
  
  every red tile is a corner of the shape--no 3 consecutive red tiles are collinear
  
  input walks the perimeter in clockwise direction ^{(this didn't end up mattering all that much)}
  
  perimeter never touches itself--every perimeter tile is adjacent to exactly 2 other perimeter tiles
  
  1 vote

[5]

Berdes

2 days, 9 hours ago

Link

First day where I don't immediately see how to solve the problem efficiently. In the end, my idea of compressing the coordinates for visualization purposes turned out to actually be a key idea to...

First day where I don't immediately see how to solve the problem efficiently. In the end, my idea of compressing the coordinates for visualization purposes turned out to actually be a key idea to quickly solve part 2.

Unfortunately, I had a stupid bug in my computation for the size of rectangles (doing abs(a-b+1) instead of abs(a-b)+1), and that didn't matter for either examples nor for part 1. If it wasn't for @lily's posted solution, which allowed me to figure out that none of the rectangles matched the size of the expected answer, I don't know how I would have found this bug.

After fixing the bug, I got the right answer in ~9ms.

Another idea for part 2 is that all the outside points are visible from the border of the map. So it's sufficient to keep track of the min and max x for all y and y for all x. Then, it's possible to check whether the edges of the rectangle are contained within those min/max values. Without coordinate compression, this approach takes ~1s. With coordinate compression, it's down to ~5ms.

Solution (Rust)

use aoc_2025::timed_run;
use std::collections::HashMap;
use std::io;
use std::vec::Vec;

struct Point {
  x: usize,
  y: usize,
}

fn side_length(a: usize, b: usize) -> usize {
  if a < b {
    b - a + 1
  } else {
    a - b + 1
  }
}

impl Point {
  fn square_with(&self, other: &Self) -> usize {
    side_length(self.x, other.x) * side_length(self.y, other.y)
  }
}

struct Input {
  points: Vec<Point>,
}

impl Input {
  fn read_from_stdin() -> Input {
    Input {
      points: io::stdin()
        .lines()
        .map(|l| {
          let ns = l
            .unwrap()
            .split(',')
            .map(|n| n.parse::<usize>().unwrap())
            .collect::<Vec<_>>();
          assert_eq!(ns.len(), 2);
          Point { x: ns[0], y: ns[1] }
        })
        .collect(),
    }
  }
}

fn part1(input: &Input) -> u64 {
  let mut ret = 0;
  for i in 0..input.points.len() {
    for j in i + 1..input.points.len() {
      ret = ret.max(input.points[i].square_with(&input.points[j]));
    }
  }
  ret as u64
}

// Compresses the coordinates such that any gap larger than 2 will end up as a gap of size 2.
fn remap_coords<F: Fn(&Point) -> usize>(input: &Input, f: F) -> (HashMap<usize, usize>, usize) {
  let mut ret = HashMap::new();
  let mut coords = vec![];
  for p in &input.points {
    coords.push(f(p));
  }
  coords.sort();
  let mut new_coord = 0;
  ret.insert(coords[0], new_coord);
  for i in 1..coords.len() {
    let prev = coords[i - 1];
    let cur = coords[i];
    if prev == cur {
      continue;
    }
    new_coord += if prev + 2 <= cur { 2 } else { 1 };
    ret.insert(coords[i], new_coord);
  }
  (ret, new_coord)
}

fn part2(input: &Input) -> u64 {
  let (new_x, max_x) = remap_coords(input, |p| p.x);
  let (new_y, max_y) = remap_coords(input, |p| p.y);
  let remap_point = |p: &Point| Point {
    x: *new_x.get(&p.x).unwrap(),
    y: *new_y.get(&p.y).unwrap(),
  };
  // Create the perimeter in the map.
  let mut map = vec![vec![b'.'; max_y + 1]; max_x + 1];
  for i in 1..=input.points.len() {
    let prev = remap_point(&input.points[i - 1]);
    let cur = remap_point(&input.points[i % input.points.len()]);
    if prev.x == cur.x {
      for y in prev.y.min(cur.y)..=prev.y.max(cur.y) {
        map[prev.x][y] = b'#';
      }
    } else {
      for x in prev.x.min(cur.x)..=prev.x.max(cur.x) {
        map[x][prev.y] = b'#';
      }
    }
  }
  // Fill the inside of the perimeter.
  let mut to_color = vec![if max_x < 100 {
    Point { x: 1, y: 3 }
  } else {
    Point { x: 100, y: 180 }
  }];
  while !to_color.is_empty() {
    let p = to_color.pop().unwrap();
    if std::mem::replace(&mut map[p.x][p.y], b'#') != b'.' {
      continue;
    }
    for np in [
      Point { x: p.x - 1, y: p.y },
      Point { x: p.x + 1, y: p.y },
      Point { x: p.x, y: p.y - 1 },
      Point { x: p.x, y: p.y + 1 },
    ] {
      if map[np.x][np.y] == b'.' {
        to_color.push(np);
      }
    }
  }
  // Find the largest rectangle that fits fully inside the perimeter.
  let mut ret = 0;
  for i in 0..input.points.len() {
    'next_point: for j in i + 1..input.points.len() {
      let pi = &input.points[i];
      let pj = &input.points[j];
      let new_size = pi.square_with(pj);
      if new_size <= ret {
        continue;
      }
      let ri = remap_point(pi);
      let rj = remap_point(pj);
      let min = Point {
        x: ri.x.min(rj.x),
        y: ri.y.min(rj.y),
      };
      let max = Point {
        x: ri.x.max(rj.x),
        y: ri.y.max(rj.y),
      };
      for x in min.x..=max.x {
        if map[x][min.y] == b'.' || map[x][max.y] == b'.' {
          continue 'next_point;
        }
      }
      for y in min.y..=max.y {
        if map[min.x][y] == b'.' || map[max.x][y] == b'.' {
          continue 'next_point;
        }
      }
      ret = new_size;
    }
  }
  ret as u64
}

fn part2_slow(input: &Input) -> u64 {
  let mut max_x_val = 0;
  let mut max_y_val = 0;
  for p in &input.points {
    max_x_val = max_x_val.max(p.x);
    max_y_val = max_y_val.max(p.y);
  }
  // Get the min/max values for each x and y coordinates. This doesn't work in the general case,
  // but should work with the kind of input we have.
  let mut min_x = vec![max_x_val; max_y_val + 1];
  let mut max_x = vec![0; max_y_val + 1];
  let mut min_y = vec![max_y_val; max_x_val + 1];
  let mut max_y = vec![0; max_x_val + 1];
  for i in 1..=input.points.len() {
    let prev = &input.points[i - 1];
    let cur = &input.points[i % input.points.len()];
    let min = Point {
      x: prev.x.min(cur.x),
      y: prev.y.min(cur.y),
    };
    let max = Point {
      x: prev.x.max(cur.x),
      y: prev.y.max(cur.y),
    };
    if prev.x == cur.x {
      min_y[prev.x] = min_y[prev.x].min(min.y);
      max_y[prev.x] = max_y[prev.x].max(max.y);
      for y in min.y..=max.y {
        min_x[y] = min_x[y].min(min.x);
        max_x[y] = max_x[y].max(max.x);
      }
    } else {
      assert_eq!(prev.y, cur.y);
      min_x[prev.y] = min_x[prev.y].min(min.x);
      max_x[prev.y] = max_x[prev.y].max(max.x);
      for x in min.x..=max.x {
        min_y[x] = min_y[x].min(min.y);
        max_y[x] = max_y[x].max(max.y);
      }
    }
  }
  // Find the largest rectangle that fits fully inside the boundaries.
  let mut ret = 0;
  for i in 0..input.points.len() {
    'next_point: for j in i + 1..input.points.len() {
      let pi = &input.points[i];
      let pj = &input.points[j];
      let new_size = pi.square_with(pj);
      if new_size <= ret {
        continue;
      }
      let min = Point {
        x: pi.x.min(pj.x),
        y: pi.y.min(pj.y),
      };
      let max = Point {
        x: pi.x.max(pj.x),
        y: pi.y.max(pj.y),
      };
      for x in min.x..=max.x {
        if min.y < min_y[x] || max.y > max_y[x] {
          continue 'next_point;
        }
      }
      for y in min.y..=max.y {
        if min.x < min_x[y] || max.x > max_x[y] {
          continue 'next_point;
        }
      }
      ret = new_size;
    }
  }
  ret as u64
}

fn part2_combined(input: &Input) -> u64 {
  let (new_x, max_x) = remap_coords(input, |p| p.x);
  let (new_y, max_y) = remap_coords(input, |p| p.y);
  let remap_point = |p: &Point| Point {
    x: *new_x.get(&p.x).unwrap(),
    y: *new_y.get(&p.y).unwrap(),
  };
  let mut max_x_val = 0;
  let mut max_y_val = 0;
  for p in &input.points {
    let rp = remap_point(p);
    max_x_val = max_x_val.max(rp.x);
    max_y_val = max_y_val.max(rp.y);
  }
  // Get the min/max values for each x and y coordinates. This doesn't work in the general case,
  // but should work with the kind of input we have.
  let mut min_x = vec![max_x_val; max_y_val + 1];
  let mut max_x = vec![0; max_y_val + 1];
  let mut min_y = vec![max_y_val; max_x_val + 1];
  let mut max_y = vec![0; max_x_val + 1];
  for i in 1..=input.points.len() {
    let prev = remap_point(&input.points[i - 1]);
    let cur = remap_point(&input.points[i % input.points.len()]);
    let min = Point {
      x: prev.x.min(cur.x),
      y: prev.y.min(cur.y),
    };
    let max = Point {
      x: prev.x.max(cur.x),
      y: prev.y.max(cur.y),
    };
    if prev.x == cur.x {
      min_y[prev.x] = min_y[prev.x].min(min.y);
      max_y[prev.x] = max_y[prev.x].max(max.y);
      for y in min.y..=max.y {
        min_x[y] = min_x[y].min(min.x);
        max_x[y] = max_x[y].max(max.x);
      }
    } else {
      assert_eq!(prev.y, cur.y);
      min_x[prev.y] = min_x[prev.y].min(min.x);
      max_x[prev.y] = max_x[prev.y].max(max.x);
      for x in min.x..=max.x {
        min_y[x] = min_y[x].min(min.y);
        max_y[x] = max_y[x].max(max.y);
      }
    }
  }
  // Find the largest rectangle that fits fully inside the boundaries.
  let mut ret = 0;
  for i in 0..input.points.len() {
    'next_point: for j in i + 1..input.points.len() {
      let pi = &input.points[i];
      let pj = &input.points[j];
      let new_size = pi.square_with(pj);
      if new_size <= ret {
        continue;
      }
      let ri = remap_point(pi);
      let rj = remap_point(pj);
      let min = Point {
        x: ri.x.min(rj.x),
        y: ri.y.min(rj.y),
      };
      let max = Point {
        x: ri.x.max(rj.x),
        y: ri.y.max(rj.y),
      };
      for x in min.x..=max.x {
        if min.y < min_y[x] || max.y > max_y[x] {
          continue 'next_point;
        }
      }
      for y in min.y..=max.y {
        if min.x < min_x[y] || max.x > max_x[y] {
          continue 'next_point;
        }
      }
      ret = new_size;
    }
  }
  ret as u64
}

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

3 votes

[4]
fidwell
2 days, 5 hours ago
Link Parent
I had this idea too, mostly because I wanted to visualize the output, and it's too big to print uncompressed. It didn't lead me to any insights though. Can you explain what you thought?

my idea of compressing the coordinates for visualization purposes turned out to actually be a key idea to quickly solve part 2.

I had this idea too, mostly because I wanted to visualize the output, and it's too big to print uncompressed. It didn't lead me to any insights though. Can you explain what you thought?

1 vote
1. [3]
  Berdes
  2 days ago
  Link Parent
  The idea was that building an in-memory map of all the points that are inside vs outside would require way too much memory using the provided coordinates. However, the compressed model fits in a...
  
  The idea was that building an in-memory map of all the points that are inside vs outside would require way too much memory using the provided coordinates. However, the compressed model fits in a 500x500 map, which is trivial to fit in memory. If the compression is correctly done, then a rectangle that is fully inside in the compressed version is also going to be fully inside in the uncompressed version. Thus, it's possible to use the naïve approach of just testing all possible rectangles and checking if they are contained in the perimeter. You just need to be careful to use the real coordinates to compute the area of the rectangle instead of the compressed coordinates.
  
  2 votes
  1. fidwell
    2 days ago
    Link Parent
    I see. I wound up representing everything as a hash set of known coordinates, instead of simulating the whole grid. So, at least for my solution, compressing the coordinates wouldn't have made any...
    
    I see. I wound up representing everything as a hash set of known coordinates, instead of simulating the whole grid. So, at least for my solution, compressing the coordinates wouldn't have made any practical difference.
    
    1 vote
  2. mawelborn
    1 day, 20 hours ago
    Link Parent
    I love the idea of compressing the coordinate space to be able to represent it as a full grid instead of sparse set of points. That's so clever!
    
    I love the idea of compressing the coordinate space to be able to represent it as a full grid instead of sparse set of points. That's so clever!

mawelborn

1 day, 21 hours ago (edited 1 day, 20 hours ago)

Link

Wow, I don't think I've seen such a jump in difficulty between Part 01 and Part 02. The first part was trivially easy, and the second part I have basically given up on a pleasing solution... or...

Wow, I don't think I've seen such a jump in difficulty between Part 01 and Part 02. The first part was trivially easy, and the second part I have basically given up on a pleasing solution... or even a general one.

Given the large search space, I knew the in-memory representation had to be sparse, and I'd likely need to take some shortcuts based on my particular input. I ran a validator and confirmed that no 2 consecutive red tiles are adjacent and no 3 consecutive red tiles are collinear. Based on that I figured it's likely a rectangle is "inside" if it doesn't intersect any edges.

My original approach was to use set intersection to test every edge simultaneously (or at least let the CPython set intersection code do it for me which I hoped would be fast). Alas no. This is catastrophically slow given the size of the grid (and is still running). I afterwards switched to a sparser line/box intersection check for each edge that completes in ~10 seconds.

There are many adversarial inputs for which my solution doesn't work. Even for the sample input it gets the right answer but using the wrong corner tiles. The selected rectangle is technically "outside." It feels hacky and unearned; plus I just kind of don't like it code-wise.

:/

Part 1

Tile = namedtuple("Tile", ["x", "y"])


def solve(input: str) -> int:
    return max(map(area, combinations(red_tiles(input), r=2)))


def red_tiles(input: str) -> Iterator[Tile]:
    for line in input.split():
        yield Tile(*map(int, line.split(",")))


def area(a_b: tuple[Tile, Tile]) -> int:
    a, b = a_b
    return (
        (abs(a.x - b.x) + 1)
        *
        (abs(a.y - b.y) + 1)
    )

Part 2

Tile = namedtuple("Tile", ["x", "y"])


def solve(input: str) -> int:
    red_tiles_ = tuple(red_tiles(input))
    edges = tuple(pairwise(red_tiles_)) + ((red_tiles_[-1], red_tiles_[0]),)
    largest_rectangles = sorted(combinations(red_tiles_, r=2), key=area, reverse=True)

    for corners in largest_rectangles:
        c0, c1 = corners

        for e0, e1 in edges:
            if e0.x == e1.x:
                if min(c0.x, c1.x) < e0.x < max(c0.x, c1.x):
                    if not (
                        (max(e0.y, e1.y) <= min(c0.y, c1.y))
                        or (min(e0.y, e1.y) >= max(c0.y, c1.y))
                    ):
                        break
            else:
                if min(c0.y, c1.y) < e0.y < max(c0.y, c1.y):
                    if not (
                        (max(e0.x, e1.x) <= min(c0.x, c1.x))
                        or (min(e0.x, e1.x) >= max(c0.x, c1.x))
                    ):
                        break
        else:
            return area(corners)


def red_tiles(input: str) -> Iterator[Tile]:
    for line in input.split():
        yield Tile(*map(int, line.split(",")))


def area(a_b: tuple[Tile, Tile]) -> int:
    a, b = a_b
    return (
        (abs(a.x - b.x) + 1)
        *
        (abs(a.y - b.y) + 1)
    )

1 vote

[3]

thecakeisalime

1 day, 18 hours ago

Link

Part 1: less than 5 minutes. Part 2: several hours of frustrating coding, just to finally import a library that does all the hard parts. I saw someone mention Shapely in a Reddit post, and figured...

Part 1: less than 5 minutes. Part 2: several hours of frustrating coding, just to finally import a library that does all the hard parts. I saw someone mention Shapely in a Reddit post, and figured that I'd learn a lot more by playing around with a new library than just brute forcing a solution poorly.

Tomorrow's goal is to discover the best python library for the job without first reading AoC threads on Tildes or Reddit. If Part 2 was any indication, I think it's well past the point where I can solve the upcoming challenges with barebones Python.

Part 1 and 2 [Python]

from shapely.geometry import Polygon, box

def parse_input(lines: list[str]) -> list[tuple[int,int]]:
  return [tuple(map(int, l.split(','))) for l in lines]

def area(tile1: tuple[int, int], tile2: tuple[int, int]) -> int:
  x1,y1 = tile1
  x2,y2 = tile2
  return (abs(x1-x2)+1)*(abs(y1-y2)+1)

def green_area(greenTiles, tile1: tuple[int, int], tile2: tuple[int, int]) -> int:
  x1,y1 = tile1
  x2,y2 = tile2
  if greenTiles.contains(box(
    min(x1, x2), min(y1, y2),
    max(x1, x2), max(y1, y2)
  )):
    return area(tile1, tile2)
  return 0


def part_one(tiles: list[tuple[int,int]]) -> int:
  return max(area(a, b) for i, a in enumerate(tiles) for b in tiles[i+1:])

def part_two(tiles: list[tuple[int,int]]) -> int:
  greenTiles = Polygon(tiles)
  return max(green_area(greenTiles, a, b) for i, a in enumerate(tiles) for b in tiles[i+1:])

def main() -> None:
  with open('09.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(input))

if __name__ == '__main__':
  main()

1 vote

thecakeisalime
1 day, 18 hours ago
Link Parent
I've never done graphical stuff before, so this is pretty basic, but I've plotted the whole floor and all of the valid rectangles. It's pretty crowded, since there's so many rectangles, so you...

I've never done graphical stuff before, so this is pretty basic, but I've plotted the whole floor and all of the valid rectangles. It's pretty crowded, since there's so many rectangles, so you can't tell which is the largest, but the shape of the floor is kinda spoilery information (if you've made it this far into the comments and are still trying to avoid spoilers).

Sample data visualization

"Real" data visualization

1 vote
imperialismus
1 day, 17 hours ago
Link Parent
Thanks for the hint about Shapely. I wasn't able to solve yesterday, got encouraged by today's part 1 being trivial, then failed to solve part 2 after lots of effort. I was about ready to admit...

Thanks for the hint about Shapely. I wasn't able to solve yesterday, got encouraged by today's part 1 being trivial, then failed to solve part 2 after lots of effort. I was about ready to admit that maybe I've reached the difficulty spike where I can't solve these things in a reasonable time, but after finding that library I was at least able to get a working solution. I'm writing this just as next day's puzzle goes live, so I'll at least give that one a look without being completely deflated!

1 vote

scarecrw

1 day, 13 hours ago

Link

Catching up on the last couple of days. This one went alright, though I was just lazy and figured at ~500 points I could probably get away with an n^3 solution. I believe I could get it to n^2logn...

Catching up on the last couple of days. This one went alright, though I was just lazy and figured at ~500 points I could probably get away with an n^3 solution. I believe I could get it to n^2logn without too much trouble if I had some more powerful data structures, but I already felt like a cheated on day 8 already by using a pre-made union-find.

Prolog Solution

:- ['src/util.pl'].
:- initialization(main).

main:-
    phrase_from_file(input(Points), 'inputs/day09.txt'),
    solve_1(Points, Result1),
    write("Part 1: "), write(Result1), nl,
    solve_2(Points, Result2),
    write("Part 2: "), write(Result2), nl,
    halt.

solve_2(Points, Result):-
    findall((I1, I2, P1, P2), (nth0(I1, Points, P1), nth0(I2, Points, P2), I1 < I2), PointPairs),
    [H|T] = Points,
    append(T, [H], ShiftedPoints),
    maplist([P1, P2, R]>>(R = (P1, P2)), Points, ShiftedPoints, LineSegs),
    include(valid_part_2_rect(LineSegs), PointPairs, ValidPointPairs),
    maplist([(_, _, P1, P2), A]>>rectangle_area((P1, P2), A), ValidPointPairs, Areas),
    max_list(Areas, Result).

valid_part_2_rect(LineSegs, (I1, I2, X1-Y1, X2-Y2)):-
    sort([X1, X2], [MinX, MaxX]),
    sort([Y1, Y2], [MinY, MaxY]),
    all(no_intersects_rect(MinX, MaxX, MinY, MaxY), LineSegs).

no_intersects_rect(MinX, MaxX, MinY, MaxY, (X1-Y1, X2-Y2)):-
    (X1 =< MinX, X2 =< MinX), !.
no_intersects_rect(MinX, MaxX, MinY, MaxY, (X1-Y1, X2-Y2)):-
    (Y1 =< MinY, Y2 =< MinY), !.
no_intersects_rect(MinX, MaxX, MinY, MaxY, (X1-Y1, X2-Y2)):-
    (X1 >= MaxX, X2 >= MaxX), !.
no_intersects_rect(MinX, MaxX, MinY, MaxY, (X1-Y1, X2-Y2)):-
    (Y1 >= MaxY, Y2 >= MaxY), !.

solve_1(Points, Result):-
    findall((P1, P2), (member(P1, Points), member(P2, Points)), PointPairs),
    maplist(rectangle_area, PointPairs, Areas),
    max_list(Areas, Result).

rectangle_area((X1-Y1, X2-Y2), Area):-
    Area is (abs(X2 - X1) + 1) * (abs(Y2 - Y1) + 1).

input([Point|Rest]) -->
    point_dcg(Point),
    "\n",
    input(Rest).
input([Point]) --> point_dcg(Point).

point_dcg(Point) --> 
    number_dcg(X),
    ",",
    number_dcg(Y),
    { Point = X-Y }.

1 vote

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

14 comments