const std = @import("std");
const path = "../data/day19/input.txt";
const RetType = u12;
const scanners = 29;
const SkipType = u29;
const rotations = 8 * 3;
const overlap = 12;
const CoordType = i16;
const ScanLine = [3]CoordType;
const ScanData = [scanners][]ScanLine;
pub fn main() !void {
var timer = try std.time.Timer.start();
const ret = try first();
const t = timer.lap() / 1000;
try std.testing.expectEqual(@as(RetType, 342), ret);
std.debug.print("Day 19a result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
pub fn first() !RetType {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
const sd = try parseInput(allocator);
defer {
for (sd) |s| {
allocator.free(s);
}
}
var skip: SkipType = 0;
var absolutes = std.AutoArrayHashMap(ScanLine, void).init(allocator);
defer absolutes.deinit();
for (sd[sd.len - 1]) |sl| {
try absolutes.put(sl, {});
}
skip |= 1 << sd.len - 1;
start: while (skip & ~@as(SkipType, 0) != ~@as(SkipType, 0)) {
for (sd) |s, idx| {
if (skip & @as(SkipType, 1) << @intCast(u5, idx) != 0) continue;
var rot: u5 = 0;
while (rot < rotations) : (rot += 1) {
var offsets = std.AutoHashMap(ScanLine, u4).init(allocator);
defer offsets.deinit();
for (s) |sl| {
for (absolutes.keys()) |abs| {
const tmp = sub(rotate(sl, rot), abs);
const res = try offsets.getOrPut(tmp);
if (res.found_existing) res.value_ptr.* += 1 else res.value_ptr.* = 1;
if (res.value_ptr.* >= overlap) {
for (s) |line| {
try absolutes.put(sub(rotate(line, rot), tmp), {});
}
skip |= @as(SkipType, 1) << @intCast(u5, idx);
continue :start;
}
}
}
}
}
}
return @intCast(RetType, absolutes.count());
}
fn parseInput(a: std.mem.Allocator) !ScanData {
const input = @embedFile(path);
var line = std.mem.split(u8, input, "\n");
var ret: ScanData = undefined;
var scanner: usize = 0;
while (scanner < scanners) : (scanner += 1) {
_ = line.next().?; // drop --- scanner...
var scanner_items = std.ArrayList(ScanLine).init(a);
defer scanner_items.deinit();
while (line.next()) |next| {
if (next.len == 0) break;
var tmp: ScanLine = undefined;
var crds = std.mem.tokenize(u8, next, ",");
var coord: usize = 0;
while (coord < 3) : (coord += 1) {
tmp[coord] = try std.fmt.parseInt(CoordType, crds.next().?, 10);
}
try scanner_items.append(tmp);
}
ret[scanner] = scanner_items.toOwnedSlice();
}
return ret;
}
fn sub(a: ScanLine, b: ScanLine) ScanLine {
return .{ a[0] - b[0], a[1] - b[1], a[2] - b[2] };
}
fn rotate(in: ScanLine, r: u5) ScanLine {
switch (r) {
// Fixed X
0 => return .{ in[0], in[1], in[2] },
1 => return .{ in[0], -in[2], in[1] },
2 => return .{ in[0], -in[1], -in[2] },
3 => return .{ in[0], in[2], -in[1] },
4 => return .{ -in[0], -in[1], in[2] },
5 => return .{ -in[0], -in[2], -in[1] },
6 => return .{ -in[0], in[1], -in[2] },
7 => return .{ -in[0], in[2], in[1] },
// Fixed Y
8 => return .{ in[1], in[0], -in[2] },
9 => return .{ in[1], -in[0], in[2] },
10 => return .{ in[1], in[2], in[0] },
11 => return .{ in[1], -in[2], -in[0] },
12 => return .{ -in[1], in[0], in[2] },
13 => return .{ -in[1], -in[0], -in[2] },
14 => return .{ -in[1], -in[2], in[0] },
15 => return .{ -in[1], in[2], -in[0] },
// Fixed Z
16 => return .{ in[2], in[0], in[1] },
17 => return .{ in[2], -in[0], -in[1] },
18 => return .{ in[2], -in[1], in[0] },
19 => return .{ in[2], in[1], -in[0] },
20 => return .{ -in[2], in[0], -in[1] },
21 => return .{ -in[2], -in[0], in[1] },
22 => return .{ -in[2], in[1], in[0] },
23 => return .{ -in[2], -in[1], -in[0] },
else => unreachable,
}
}
test "day19a" {
try std.testing.expectEqual(@as(RetType, 342), try first());
}