const std = @import("std");
const mem = std.mem;
const math = std.math;
const path = "../data/day22/input.txt";
const Cuboid = struct {
    state: bool,
    xmin: isize,
    xmax: isize,
    ymin: isize,
    ymax: isize,
    zmin: isize,
    zmax: isize,
};
const Cubes = []Cuboid;
const SubCubeType = i3;
const SubCubes = std.AutoArrayHashMap(Cuboid, SubCubeType);
pub fn main() !void {
    var timer = try std.time.Timer.start();
    const ret = try second();
    const t = timer.lap() / 1000;
    try std.testing.expectEqual(@as(isize, 1267133912086024), ret);
    std.debug.print("Day 22b result: {d}time: {d}µs\n", .{ ret, t });
}
pub fn second() !isize {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    const input = try parseInput(allocator);
    defer allocator.free(input);
    // original and subcubes
    var cubes = SubCubes.init(allocator);
    defer cubes.deinit();
    for (input) |cube| {
        var overlaps = std.AutoHashMap(Cuboid, SubCubeType).init(allocator);
        defer overlaps.deinit();
        var it = cubes.iterator();
        while (it.next()) |orig| {
            const ovrlp = overlap(cube, orig.key_ptr.*) orelse continue;
            // this way we do not count a subcube twice
            const res = try overlaps.getOrPut(ovrlp);
            if (res.found_existing) {
                res.value_ptr.* -= orig.value_ptr.*;
            } else {
                res.value_ptr.* = -orig.value_ptr.*;
            }
        }
        // add cubes from input to overlaps array
        if (cube.state) try cubes.put(cube, 1);
        // set the main array values based on overlaps
        var oit = overlaps.iterator();
        while (oit.next()) |o| {
            const item = try cubes.getOrPut(o.key_ptr.*);
            if (item.found_existing) {
                item.value_ptr.* += o.value_ptr.*;
            } else {
                item.value_ptr.* = o.value_ptr.*;
            }
        }
    }
    var sum: isize = 0;
    var it = cubes.iterator();
    while (it.next()) |c| {
        const cube = c.key_ptr.*;
        sum += c.value_ptr.* *
            (cube.xmax - cube.xmin + 1) *
            (cube.ymax - cube.ymin + 1) *
            (cube.zmax - cube.zmin + 1);
    }
    return sum;
}
fn overlap(a: Cuboid, b: Cuboid) ?Cuboid {
    if ((a.xmax < b.xmin or a.xmin > b.xmax) or
        (a.ymax < b.ymin or a.ymin > b.ymax) or
        (a.zmax < b.zmin or a.zmin > b.zmax)) return null;
    return Cuboid{ .state = false, .xmin = math.max(a.xmin, b.xmin), .xmax = math.min(a.xmax, b.xmax), .ymin = math.max(a.ymin, b.ymin), .ymax = math.min(a.ymax, b.ymax), .zmin = math.max(a.zmin, b.zmin), .zmax = math.min(a.zmax, b.zmax) };
}
fn parseInput(a: mem.Allocator) !Cubes {
    const input = @embedFile(path);
    var lines = mem.split(u8, input, "\n");
    var ret = std.ArrayList(Cuboid).init(a);
    while (lines.next()) |line| {
        if (line.len == 0) break;
        var cube: Cuboid = undefined;
        var st_coord = mem.tokenize(u8, line, " ");
        // set cuboid state
        if (mem.eql(u8, st_coord.next().?, "on")) cube.state = true else cube.state = false;
        var axes = mem.tokenize(u8, st_coord.next().?, ",");
        var cntr: u2 = 0;
        while (axes.next()) |ax| : (cntr += 1) {
            const axis = ax[2..]; // strip x=, y=, z=
            var min_max = mem.tokenize(u8, axis, "..");
            // coordinates
            if (cntr == 0) {
                cube.xmin = try std.fmt.parseInt(isize, min_max.next().?, 10);
                cube.xmax = try std.fmt.parseInt(isize, min_max.next().?, 10);
            }
            if (cntr == 1) {
                cube.ymin = try std.fmt.parseInt(isize, min_max.next().?, 10);
                cube.ymax = try std.fmt.parseInt(isize, min_max.next().?, 10);
            }
            if (cntr == 2) {
                cube.zmin = try std.fmt.parseInt(isize, min_max.next().?, 10);
                cube.zmax = try std.fmt.parseInt(isize, min_max.next().?, 10);
            }
        }
        try ret.append(cube);
    }
    return ret.toOwnedSlice();
}
test "day22b" {
    try std.testing.expectEqual(@as(isize, 1267133912086024), try second());
}

### Day 22b first solution: day22b_coord_comp.zig ~9 seconds

much faster.
TODO: C++ version takes 220ms, but the zig one is 9s. Why?

much faster, but it is still not fast enough.
### Final version
We use create subcube only when two cubes are intersecting and switch the cubes
on and off based on the new input. This way we keep the number of cubes low
(~7000 cubes vs. the 840*840*840 items in the previous version).
We keep the subcubes in `std.AutoArrayHashMap` so iterating is fast. Running
time is ~95ms.