const std = @import("std");

const path = "data/day19/input.txt";

const RetType = i16;

const SkipType = u29;

const rotations = 8 * 3;
const overlap = 12;

const CoordType = i16;
const ScanLine = [3]CoordType;

const scanners = 29;
const ScanData = [scanners][]ScanLine;

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    var timer = try std.time.Timer.start();
    const ret = try second(arena.allocator());
    const t = timer.lap() / 1000;

    try std.testing.expectEqual(@as(RetType, 9668), ret);

    std.debug.print("Day 19b result: {d} \t\ttime: {d}us\n", .{ ret, t });
}

pub fn second(allocator: ?std.mem.Allocator) !RetType {
    const sd = try parseInput(allocator.?);
    defer {
        for (sd) |s| {
            allocator.?.free(s);
        }
    }

    var scnrs: [scanners]ScanLine = undefined;

    var absolutes = std.AutoArrayHashMap(ScanLine, void).init(allocator.?);
    defer absolutes.deinit();

    for (sd[sd.len - 1]) |sl| {
        try absolutes.put(sl, {});
    }

    var skip: SkipType = 0;
    skip |= 1 << sd.len - 1;

    scnrs[sd.len - 1] = ScanLine{ 0, 0, 0 };

    start: while (skip & ~@as(SkipType, 0) != ~@as(SkipType, 0)) {
        for (sd) |scanner, idx| {
            if (skip & @as(SkipType, 1) << @intCast(u5, idx) != 0) continue;

            var rot: u5 = 0;
            rot: while (rot < rotations) : (rot += 1) {
                var offsets = std.AutoHashMap(ScanLine, u4).init(allocator.?);
                defer offsets.deinit();

                var match_counter: usize = 0;

                for (scanner) |sl, line_counter| {
                    const rl = rotate(sl, rot);
                    for (absolutes.keys()) |abs| {
                        const offset = sub(rl, abs);

                        if ((try std.math.absInt(offset[0])) < 1000 and (try std.math.absInt(offset[1])) < 1000 and (try std.math.absInt(offset[2])) < 1000) {
                            continue;
                        }

                        const res = try offsets.getOrPut(offset);
                        if (res.found_existing) {
                            res.value_ptr.* += 1;
                            match_counter += 1;
                        } else {
                            res.value_ptr.* = 1;
                        }

                        if (res.value_ptr.* >= overlap) {
                            scnrs[idx] = offset;
                            for (scanner) |line| {
                                try absolutes.put(sub(rotate(line, rot), offset), {});
                            }
                            skip |= @as(SkipType, 1) << @intCast(u5, idx);
                            continue :start;
                        }
                    }
                    if (match_counter + (scanner.len - line_counter) < overlap) {
                        continue :rot;
                    }
                    if (line_counter > 6 and match_counter == 0) {
                        continue :rot;
                    }
                }
            }
        }
    }

    var ret: RetType = 0;
    for (scnrs) |first| {
        for (scnrs) |sec| {
            const xdiff = try std.math.absInt(first[0] - sec[0]);
            const ydiff = try std.math.absInt(first[1] - sec[1]);
            const zdiff = try std.math.absInt(first[2] - sec[2]);
            const sum = xdiff + ydiff + zdiff;
            if (sum > ret) {
                ret = sum;
            }
        }
    }

    return ret;
}

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 "day19b" {
    try std.testing.expectEqual(@as(RetType, 9668), try second(std.testing.allocator));
}