const std = @import("std");

pub fn main() !void {
    try std.fmt.format(std.io.getStdOut().writer(), "day 11 pt1: {}\n", .{try solve_pt1(std.heap.page_allocator, puzzle_input)});
    try std.fmt.format(std.io.getStdOut().writer(), "day 11 pt2: {}\n", .{try solve_pt2(std.heap.page_allocator, puzzle_input)});
}

const Coord = struct {
    x: usize,
    y: usize,
};

inline fn get(grid: []const u8, width: usize, x: usize, y: usize) u8 {
    return grid[y*(width+1) + x];
}

fn solve_pt1(a: std.mem.Allocator, input: []const u8) !u64 {
    return solve(a, input, 2);
}
fn solve_pt2(a: std.mem.Allocator, input: []const u8) !u64 {
    return solve(a, input, 1000000);
}
fn solve(a: std.mem.Allocator, input: []const u8, multiplier: usize) !u64 {
    const width: usize = std.mem.indexOfScalar(u8, input, '\n') orelse return error.BadInput;
    const height: usize = (input.len / width + 1) - 1;
    // std.log.warn("width {} height {}", .{width, height});
    const x_adjust = try a.alloc(usize, width);
    defer a.free(x_adjust);
    const y_adjust = try a.alloc(usize, height);
    defer a.free(y_adjust);
    var galaxies = std.ArrayList(Coord).init(a);
    defer galaxies.deinit();
    var x_adj: usize = 0;
    for (0..width) |x| {
        var allspace = true;
        for (0..height) |y| {
            const ch = get(input, width, x, y);
            if (ch == '#') {
                try galaxies.append(.{.x = x, .y = y});
                allspace = false;
            }
        }
        if (allspace) {
            x_adj += (multiplier-1);
        }
        x_adjust[x] = x_adj;
    }
    var y_adj:usize = 0;
    for (0..height) |y| {
        var allspace = true;
        for (0..width) |x| {
            const ch = get(input, width, x, y);
            if (ch == '#') {
                allspace = false;
            }
        }
        if (allspace) {
            y_adj += (multiplier-1);
        }
        y_adjust[y] = y_adj;
    }

    for (galaxies.items) |*gal| {
        const x = gal.x;
        const y = gal.y;
        gal.* = .{
            .x = x + x_adjust[x],
            .y = y + y_adjust[y],
        };
    }

    var sum: usize = 0;
    for (0..galaxies.items.len) |ix1| {
        for (ix1..galaxies.items.len) |ix2| {
            const g1 = galaxies.items[ix1];
            const g2 = galaxies.items[ix2];
            const x_diff = @max(g1.x, g2.x) - @min(g1.x, g2.x);
            const y_diff = @max(g1.y, g2.y) - @min(g1.y, g2.y);
            sum += x_diff + y_diff;
        }
    }

    return sum;
}

test "pt1" {
    try std.testing.expectEqual(@as(u64, 374), try solve_pt1(std.testing.allocator, test_input));
}
test "pt2" {
    try std.testing.expectEqual(@as(u64, 1030), try solve(std.testing.allocator, test_input, 10));
}
test "pt2_2" {
    try std.testing.expectEqual(@as(u64, 8410), try solve(std.testing.allocator, test_input, 100));
}

const test_input = 
\\...#......
\\.......#..
\\#.........
\\..........
\\......#...
\\.#........
\\.........#
\\..........
\\.......#..
\\#...#.....
;

const puzzle_input = @embedFile("day11.in");