Advent Of Code 2025 Day 9

const std = @import("std");
const parseInt = std.fmt.parseInt;

const Coords = struct { x: u64, y: u64 };
const Edge = struct {
    x1: u64,
    y1: u64,
    x2: u64,
    y2: u64,
    horizontal: bool,
};

fn partOne(stdout: *std.Io.Writer, allocator: std.mem.Allocator) !void {
    const file = try std.fs.cwd().openFile("data.txt", .{ .mode = .read_only });
    defer file.close();

    var file_buffer: [4096]u8 = undefined;
    var file_reader = file.reader(&file_buffer);
    const reader = &file_reader.interface;

    var list: std.ArrayList(Coords) = .empty;
    defer list.deinit(allocator);

    while (reader.takeDelimiterExclusive('\n')) |line| {
        reader.toss(1);

        var it = std.mem.tokenizeAny(u8, line, ",");
        const first_str = it.next().?;
        const x = try parseInt(u64, first_str, 10);
        const second_str = it.next().?;
        const y = try parseInt(u64, second_str, 10);

        const coord = Coords{ .x = x, .y = y };
        try list.append(allocator, coord);
    } else |err| switch (err) {
        error.EndOfStream => {},
        else => return err,
    }

    var largest_area: u64 = 0;

    for (list.items, 0..) |first, i| {
        for (list.items, 0..) |second, j| {
            if (i == j) continue;

            const dx = if (first.x > second.x) first.x - second.x + 1 else second.x - first.x + 1;
            const dy = if (first.y > second.y) first.y - second.y + 1 else second.y - first.y + 1;

            const area = dx * dy;
            if (area > largest_area) largest_area = area;
        }
    }

    try stdout.print("Largest area: {d}\n", .{largest_area});
    try stdout.flush();
}

fn pointOnEdge(x: u64, y: u64, edges: []Edge) bool {
    for (edges) |e| {
        if (e.horizontal) {
            if (y == e.y1 and x >= e.x1 and x <= e.x2) return true;
        } else {
            if (x == e.x1 and y >= e.y1 and y <= e.y2) return true;
        }
    }
    return false;
}

fn pointInPolygon(x: u64, y: u64, edges: []Edge) bool {
    if (pointOnEdge(x, y, edges)) return true;

    var inside: bool = false;

    for (edges) |e| {
        if (e.horizontal) continue;

        const ey = y;
        const y0 = e.y1;
        const y1 = e.y2;
        if (!(y0 <= ey and ey < y1)) continue;

        if (e.x1 > x) inside = !inside;
    }
    return inside;
}

fn overlapsPositive(a0: u64, a1: u64, b0: u64, b1: u64) bool {
    const left = if (a0 > b0) a0 else b0;
    const right = if (a1 < b1) a1 else b1;

    return right > left;
}

fn rectangleInsidePolygon(
    xmin: u64,
    ymin: u64,
    xmax: u64,
    ymax: u64,
    edges: []Edge,
) bool {
    if (xmin > xmax or ymin > ymax) return false;

    const mx = xmin + (xmax - xmin) / 2;
    const my = ymin + (ymax - ymin) / 2;
    if (!pointInPolygon(mx, my, edges)) return false;

    for (edges) |e| {
        if (e.horizontal) {
            if ((e.y1 > ymin) and (e.y1 < ymax)) {
                if (overlapsPositive(e.x1, e.x2, xmin, xmax)) return false;
            }
        } else {
            if ((e.x1 > xmin) and (e.x1 < xmax)) {
                if (overlapsPositive(e.y1, e.y2, ymin, ymax)) return false;
            }
        }
    }

    return true;
}

fn partTwo(stdout: *std.Io.Writer, allocator: std.mem.Allocator) !void {
    const file = try std.fs.cwd().openFile("data.txt", .{ .mode = .read_only });
    defer file.close();

    var file_buffer: [4096]u8 = undefined;
    var file_reader = file.reader(&file_buffer);
    const reader = &file_reader.interface;

    var list: std.ArrayList(Coords) = .empty;
    defer list.deinit(allocator);

    while (reader.takeDelimiterExclusive('\n')) |line| {
        reader.toss(1);

        var it = std.mem.tokenizeAny(u8, line, ",");
        const first_str = it.next().?;
        const x = try parseInt(u64, first_str, 10);
        const second_str = it.next().?;
        const y = try parseInt(u64, second_str, 10);

        const coord = Coords{ .x = x, .y = y };
        try list.append(allocator, coord);
    } else |err| switch (err) {
        error.EndOfStream => {},
        else => return err,
    }

    var edges: std.ArrayList(Edge) = .empty;
    defer edges.deinit(allocator);

    const n = list.items.len;
    var i: usize = 0;
    while (i < n) : (i += 1) {
        const j = if (i + 1 == n) 0 else i + 1;
        const a = list.items[i];
        const b = list.items[j];

        if (a.x != b.x and a.y != b.y) {
            return error.InvalidEdge;
        }

        if (a.x == b.x) {
            const y0 = if (a.y <= b.y) a.y else b.y;
            const y1 = if (a.y <= b.y) b.y else a.y;
            try edges.append(allocator, Edge{
                .x1 = a.x,
                .y1 = y0,
                .x2 = a.x,
                .y2 = y1,
                .horizontal = false,
            });
        } else {
            const x0 = if (a.x <= b.x) a.x else b.x;
            const x1 = if (a.x <= b.x) b.x else a.x;
            try edges.append(allocator, Edge{
                .x1 = x0,
                .y1 = a.y,
                .x2 = x1,
                .y2 = a.y,
                .horizontal = true,
            });
        }
    }

    var largest_area: u64 = 0;
    for (list.items, 0..) |a, idx| {
        for (list.items[idx + 1 ..]) |b| {
            const xmin = if (a.x < b.x) a.x else b.x;
            const xmax = if (a.x < b.x) b.x else a.x;
            const ymin = if (a.y < b.y) a.y else b.y;
            const ymax = if (a.y < b.y) b.y else a.y;

            if (rectangleInsidePolygon(xmin, ymin, xmax, ymax, edges.items)) {
                const area = (xmax - xmin + 1) * (ymax - ymin + 1);
                if (area > largest_area) largest_area = area;
            }
        }
    }

    try stdout.print("Largest area: {d}\n", .{largest_area});
    try stdout.flush();
}

pub fn main() !void {
    var stdout_buffer: [1024]u8 = undefined;
    var stdout_writer = std.fs.File.stdout().writer(&stdout_buffer);
    const stdout = &stdout_writer.interface;
    const day: u8 = 9;
    try stdout.print("Start of Day {d} Part 1\n", .{day});
    try stdout.print("--" ** 20 ++ "\n", .{});
    try stdout.flush();
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();
    try partOne(stdout, allocator);
    try stdout.print("--" ** 20 ++ "\n", .{});
    try stdout.print("Start of Day {d} Part 2\n", .{day});
    try stdout.print("--" ** 20 ++ "\n", .{});
    try stdout.flush();
    try partTwo(stdout, allocator);
}