Problem

Read it here

tl;dr

You have a grid with red tiles at certain coordinates. Find the largest rectangle where two opposite corners are red tiles.

Part 1: What is the largest area of any rectangle you can make?

Example:

Red tiles at:

7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3

Visual representation:

..............
.......#...#..
..............
..#....#......
..............
..#......#....
..............
...#.....#.#..
..............

Possible rectangles:

• Area 24: between (2,5) and (9,7)
• Area 35: between (7,1) and (11,7)
• Area 6: between (7,3) and (2,3)
• Area 50: between (2,5) and (11,1) ← largest

Part 1 answer: 50

---

Part 2: The rectangle can only include red or green tiles.

• Red tiles are connected by straight lines of green tiles (adjacent red tiles in the list are connected by green tiles on the same row/column)
• The list wraps (first red tile connects to last red tile)
• All tiles inside the loop formed by red and green tiles are also green

Example green tiles:

..............
.......#XXX#..  (red tiles connected by green X's)
.......XXXXX..
..#XXXX#XXXX..
..XXXXXXXXXX..
..#XXXXXX#XX..
.........XXX..
.........#X#..
..............

Constraints:

• Rectangle must still have red tiles at opposite corners
• All other tiles in the rectangle must be red or green

Example rectangles:

• Area 15: between (7,3) and (11,1)
• Area 3: between (9,7) and (9,5)
• Area 24: between (9,5) and (2,3) ← largest

Part 2 answer: 24

---

My Solution (Handcrafted)

Part 1

Straightforward brute force — check all pairs of red tiles and calculate the area:

pub fn solve_1(filename: &str) -> u64 {
    let coordinates = Self::read_input(filename);

    let mut max_area = 0;
    for i in 0..coordinates.len() {
        for j in i + 1..coordinates.len() {
            let area = coordinates[i].area_with(&coordinates[j]);
            max_area = max(max_area, area);
        }
    }
    max_area
}

Part 2

This is where I struggled. I initially tried a boundary-tracing approach but couldn’t get the “inside” detection right, and pivoted to using flood filling approach. The solution works for the test input but took over 10 minutes to run for the actual input. With some guidance, I ended up using raycasting to determine if a point is inside the polygon.

The approach:

1. Build the polygon edges (lines connecting adjacent red tiles)
2. For each pair of red tiles, check if the rectangle formed is entirely inside the polygon
3. Use raycasting to check if points are inside

Raycasting logic: Cast a ray from the point to the left. Count how many vertical edges it crosses. If odd → inside. If even → outside.

fn is_inside_by_raycasting(x: usize, y: usize, vertical_edges: &[VerticalEdge]) -> bool {
    let mut crossings = 0;

    for edge in vertical_edges {
        // Check if ray at height y crosses this vertical edge
        if edge.x < x && edge.y_min < y && y <= edge.y_max {
            crossings += 1;
        }
    }

    crossings % 2 == 1
}

Optimization: Instead of checking every point in the rectangle, I only check the left and right edges at each unique Y coordinate of red tiles. I also cache inside/outside results to avoid redundant raycasting.

for &y in &unique_ys {
    if y < min_y || y > max_y { continue; }
    for x in [min_x, max_x] {
        if edge_nodes.contains(&Coordinate::new(x, y)) { continue; }
        if inside_coordinates.contains(&Coordinate::new(x, y)) { continue; }
        if outside_coordinates.contains(&Coordinate::new(x, y)) {
            all_inside = false;
            break 'outer;
        }
        if Self::is_inside_by_raycasting(x, y, &vertical_edges) {
            inside_coordinates.insert(Coordinate::new(x, y));
        } else {
            outside_coordinates.insert(Coordinate::new(x, y));
            all_inside = false;
            break 'outer;
        }
    }
}

---

Gemini’s Solution

Part 1

Same brute force approach — nothing fancy needed.

Part 2

Gemini uses a more thorough validation approach with three checks:

fn is_valid_rect(p1: &Point, p2: &Point, poly: &[Point]) -> bool {
    // 1. Check if the other two corners are inside or on boundary
    let c3 = (min_x as f64, max_y as f64);
    let c4 = (max_x as f64, min_y as f64);
    if !Self::is_inside_or_boundary(c3, poly) || !Self::is_inside_or_boundary(c4, poly) {
        return false;
    }

    // 2. Check if center is inside (prevents U-shape issues)
    let center = ((min_x + max_x) / 2.0, (min_y + max_y) / 2.0);
    if !Self::is_inside_or_boundary(center, poly) {
        return false;
    }

    // 3. Check if any polygon edge intersects the interior of the rectangle
    // ... edge intersection checks ...
}

Key insight from Gemini: Also check the center point and verify no polygon edges cut through the rectangle interior. This handles edge cases like U-shaped polygons.

Gemini’s raycasting uses floating-point math and handles edge cases more carefully:

fn is_inside_or_boundary(p: (f64, f64), poly: &[Point]) -> bool {
    // 1. Check boundary explicitly
    for i in 0..n {
        if Self::is_on_segment(p, &poly[i], &poly[(i + 1) % n]) {
            return true;
        }
    }

    // 2. Ray Casting for interior check
    let (px, py) = p;
    let mut inside = false;

    for i in 0..n {
        let y1 = p1.y as f64;
        let y2 = p2.y as f64;

        if py >= min_y && py < max_y {
            let intersect_x = x1 + (py - y1) * (x2 - x1) / (y2 - y1);
            if intersect_x > px {
                inside = !inside;
            }
        }
    }
    inside
}

---

Comparison

Aspect	My Solution	Gemini’s Solution
Part 1	Brute force	Brute force
Inside check	Raycasting on vertical edges	Raycasting with boundary check
Validation	Check left/right edges only	Check corners, center, and edges
Caching	Yes (inside/outside sets)	No
Math	Integer	Floating point with epsilon

---

Reflection

Part 1 was easy. Part 2 was a different story.

I initially tried a boundary-tracing approach — walk along the edges and fill in the interior. But the “inside” detection was tricky and I kept getting edge cases wrong. Eventually I had to lean on AI guidance to learn about the raycasting algorithm for point-in-polygon testing.

The raycasting idea is elegant: shoot a ray from a point, count how many edges it crosses. Odd = inside, even = outside. But getting the details right (which edge orientations to count, handling points exactly on edges) took some iteration.

Gemini’s solution is more defensive — it checks corners, center, AND verifies no polygon edges cut through the rectangle. My solution only checks the left/right boundary points, which is faster but assumes the polygon is well-behaved.

This was a humbling day. Sometimes you just have to admit you don’t know an algorithm and learn it.

Time spent: ~45 minutes (most of it on Part 2)