Advent of Code 2025/9 'Movie Theater'' in C# by encse

You slide down the firepole in the corner of the playground and land in the North Pole base movie theater!
The movie theater has a big tile floor with an interesting pattern. Elves here are redecorating the theater by switching out some of the square tiles in the big grid they form. Some of the tiles are red; the Elves would like to find the largest rectangle that uses red tiles for two of its opposite corners. They even have a list of where the red tiles are located in the grid (your puzzle input).

Visit the website for the full story and full puzzle description.

This one really caused me a headache. I made a bug in the area function, at the beginning, which was not triggered in part one. Then came the strugling for hours which overloaded my mind. My head was full of intersection functions and ray casting and eye balling for errors, but it just didn't work.

I made a little python script that draws the input, which is a circle with a slot in the middle. Looked really special, I started to add heuristics to my solution, but of course this didn't help due to the bogus area function.

After the 200th read, I finally spotted my mistake and got the second star, but I got tired of the whole thing and couldn't really put this into a nice form.

shape

At the end, I started to read the solution thread and spotted that a simple AabbCollision function is enough. And somehow it clicked. Without the hint, I would have been on the wrong track for a much longer time for sure.

But at least the final result looks good in my opinion.

namespace AdventOfCode.Y2025.Day09;

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

record Rectangle(long top, long left, long bottom, long right);

[ProblemName("Movie Theater")]
class Solution : Solver {

    public object PartOne(string input) {
        var points = Parse(input);
        return (
             from r in RectanglesOrderedByArea(points)
             select Area(r)
         ).First();
    }

    public object PartTwo(string input) {
        var points = Parse(input);
        var segments = Boundary(points).ToArray();
        // AabbCollision enables rectangles inside or outside the
        // shape, but the input is set up in a way that big rectangles
        // are all inside, so this loop will find the correct one for actual
        // problems.
        return (
             from r in RectanglesOrderedByArea(points)
             where segments.All(s => !AabbCollision(r, s))
             select Area(r)
         ).First();
    }

    IEnumerable<Rectangle> RectanglesOrderedByArea(Complex[] points) =>
        from p1 in points
        from p2 in points 
        let r = RectangleFromPoints(p1, p2)
        orderby Area(r) descending
        select r;

    IEnumerable<Rectangle> Boundary(Complex[] corners) =>
        from pair in corners.Zip(corners.Prepend(corners.Last()))
        select RectangleFromPoints(pair.First, pair.Second);

    Rectangle RectangleFromPoints(Complex p1, Complex p2) {
        var top = Math.Min(p1.Imaginary, p2.Imaginary);
        var bottom = Math.Max(p1.Imaginary, p2.Imaginary);
        var left = Math.Min(p1.Real, p2.Real);
        var right = Math.Max(p1.Real, p2.Real);
        return new Rectangle((long)top, (long)left, (long)bottom, (long)right);
    }

    Complex[] Parse(string input) => (
        from line in input.Split("\n")
        let parts = line.Split(",").Select(int.Parse).ToArray()
        select parts[0] + Complex.ImaginaryOne * parts[1]
    ).ToArray();

    long Area(Rectangle r) => (r.bottom - r.top + 1) * (r.right - r.left + 1);

    // see https://kishimotostudios.com/articles/aabb_collision/
    bool AabbCollision(Rectangle a, Rectangle b) {
        var aIsToTheLeft = a.right <= b.left;
        var aIsToTheRight = a.left >= b.right;
        var aIsAbove = a.bottom <= b.top;
        var aIsBelow = a.top >= b.bottom;
        return !(aIsToTheRight || aIsToTheLeft || aIsAbove || aIsBelow);
    }
}

Please ☆ my repo if you like it!