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());
}