.days = 10,

    .days = 11,

    const day11 = @import("day11.zig");

    _ = @import("day11.zig");

const std = @import("std");
const PATH = "inputs/day11.txt";
pub fn first(allocator: std.mem.Allocator) !usize {
    return try shortestPath(allocator, 1);
}
pub fn second(allocator: std.mem.Allocator) !usize {
    return try shortestPath(allocator, 999_999);
}
test "day11a" {
    try std.testing.expectEqual(@as(usize, 9605127), try first(std.testing.allocator));
}
test "day11b" {
    try std.testing.expectEqual(@as(usize, 458191688761), try second(std.testing.allocator));
}
const Galaxy = enum {
    empty,
    galaxy,
};
const Image = [][]Galaxy;
const IMAGE_SIZE = 140;
fn parseInput(allocator: std.mem.Allocator, input: []const u8) !Image {
    var lines = std.mem.splitScalar(u8, input, '\n');
    var image = try std.ArrayList([]Galaxy).initCapacity(allocator, IMAGE_SIZE);
    // defer image.deinit();
    var imline = std.ArrayList(Galaxy).init(allocator);
    defer imline.deinit();
    while (lines.next()) |line| {
        if (line.len == 0) continue;
        try imline.ensureTotalCapacity(IMAGE_SIZE);
        for (line) |item| {
            switch (item) {
                '.' => imline.appendAssumeCapacity(.empty),
                '#' => imline.appendAssumeCapacity(.galaxy),
                else => unreachable,
            }
        }
        image.appendAssumeCapacity(try imline.toOwnedSlice());
    }
    // std.debug.print("rows: {any} cols: {any}\n", .{ image.items.len, image.items[0].len });
    return image.items;
}
fn emptyCols(allocator: std.mem.Allocator, image: Image) !std.ArrayList(usize) {
    var empty_cols = std.ArrayList(usize).init(allocator);
    // defer empty_cols.deinit();
    std.debug.assert(image.len > 0);
    const cols = image[0].len;
    // collect empty column numbers
    COLS: for (0..cols) |col| {
        for (image, 0..) |_, row| {
            switch (image[row][col]) {
                .empty => {},
                .galaxy => continue :COLS,
            }
        }
        try empty_cols.append(col);
    }
    return empty_cols;
}
fn emptyRows(allocator: std.mem.Allocator, image: Image) !std.ArrayList(usize) {
    var empty_rows = std.ArrayList(usize).init(allocator);
    // defer empty_rows.deinit();
    // collect empty row numbers
    ROWS: for (image, 0..) |line, row| {
        for (line) |ch|
            switch (ch) {
                .empty => {},
                .galaxy => continue :ROWS,
            };
        try empty_rows.append(row);
    }
    return empty_rows;
}
fn inRange(slice: []usize, min: usize, max: usize) usize {
    var count: usize = 0;
    for (slice) |item| {
        if (item > min and item < max) count += 1;
    }
    return count;
}
const Coord = [2]usize;
fn findGalaxies(allocator: std.mem.Allocator, in: Image) !std.ArrayList(Coord) {
    var gals = std.ArrayList(Coord).init(allocator);
    // defer gals.deinit();
    for (in, 0..) |line, row| {
        for (line, 0..) |item, col| {
            switch (item) {
                .empty => {},
                .galaxy => {
                    try gals.append(.{ row, col });
                },
            }
        }
    }
    return gals;
}
fn shortestPath(allocator: std.mem.Allocator, exp_value: usize) !usize {
    const input = try std.fs.cwd().readFileAlloc(allocator, PATH, 512 * 512);
    defer allocator.free(input);
    const image = try parseInput(allocator, input);
    defer {
        for (image) |i| {
            allocator.free(i);
        }
        allocator.free(image);
    }
    const erows = try emptyRows(allocator, image);
    defer erows.deinit();
    const ecols = try emptyCols(allocator, image);
    defer ecols.deinit();
    const galaxies = try findGalaxies(allocator, image);
    defer galaxies.deinit();
    var path: usize = 0;
    for (galaxies.items, 0..) |g, frst| {
        for (frst + 1..galaxies.items.len) |scnd| {
            const xmin = @min(g[0], galaxies.items[scnd][0]);
            const xmax = @max(g[0], galaxies.items[scnd][0]);
            const xdiff = xmax - xmin;
            const ymin = @min(g[1], galaxies.items[scnd][1]);
            const ymax = @max(g[1], galaxies.items[scnd][1]);
            const ydiff = ymax - ymin;
            const exp_rows = inRange(erows.items, xmin, xmax);
            const exp_cols = inRange(ecols.items, ymin, ymax);
            const distance = xdiff + ydiff + exp_rows * exp_value + exp_cols * exp_value;
            // std.debug.print("{d}->{d} ~ {d}\n", .{ frst, scnd, distance });
            path += distance;
        }
    }
    return path;
}
const test_input1 =
    \\...#......
    \\.......#..
    \\#.........
    \\..........
    \\......#...
    \\.#........
    \\.........#
    \\..........
    \\.......#..
    \\#...#.....
;