const std = @import("std");
const path = "../data/day18/input.txt";
const explode_limit = 4;
const Str = []const u8;
const SnailType = u6;
const SnailItem = union(enum) {
    num: SnailType,
    pair: *SnailNumber,
};
const SnailNumber = struct {
    left: ?SnailItem = null,
    right: ?SnailItem = null,
    parent: ?*SnailNumber = null,
    fn add(self: *@This(), a: std.mem.Allocator, input: *Str) !*SnailNumber {
        var pos: usize = 1;
        const next = try parseSnail(a, input, null, &pos);
        const root = try a.create(SnailNumber);
        root.left = SnailItem{ .pair = self };
        root.right = SnailItem{ .pair = next };
        root.parent = null; // segfaults without this line :-(
        self.parent = root;
        next.parent = root;
        return root;
    }
};
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(usize, 3675), ret);
    std.debug.print("Day 18a result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
pub fn first() !usize {
    const input = @embedFile(path);
    var in = std.mem.tokenize(u8, input, "\n");
    const gpa = std.heap.page_allocator;
    var arena = std.heap.ArenaAllocator.init(gpa);
    const allocator = arena.allocator();
    defer arena.deinit();
    var ret: *SnailNumber = undefined;
    var idx: usize = 0;
    while (in.next()) |line| : (idx += 1) {
        if (idx == 0) {
            var pos: usize = 1;
            ret = try parseSnail(allocator, &line[0..], null, &pos);
        } else {
            ret = try ret.add(allocator, &line[0..]);
            try reduce(allocator, ret);
        }
    }
    return magnitude(ret);
}
fn reduce(a: std.mem.Allocator, sn: *SnailNumber) anyerror!void {
    // printSnailNumber(sn);
    // std.debug.print("\n", .{});
    if (checkExplode(a, sn, 0)) |node| {
        explode(a, node);
        try reduce(a, sn);
    } else if (checkSplit(a, sn)) |node| {
        try split(a, node);
        try reduce(a, sn);
    }
}
fn explode(a: std.mem.Allocator, node: *SnailNumber) void {
    // std.debug.print("\nexplode called: ", .{});
    // printSnailNumber(node);
    // std.debug.print("\n", .{});
    defer a.destroy(node); // free up abandoned node
    explodeLeft(node);
    explodeRight(node);
    const par = node.parent.?;
    if (par.left.? == .pair and par.left.?.pair == node) {
        par.left = SnailItem{ .num = 0 };
    } else {
        par.right = SnailItem{ .num = 0 };
    }
}
fn explodeLeft(node: *SnailNumber) void {
    const left = node.left.?.num;
    var prev = node;
    var it = node.parent;
    while (it) |par| : ({
        prev = par;
        it = par.parent;
    }) {
        if (par.left) |l| {
            switch (l) {
                // check if it is not the exploding node
                SnailItem.pair => |p| if (p != prev) break,
                else => break,
            }
        }
    }
    target: while (it) |target| {
        // These must be _pointers_! Removing the & makes them local, so the changes
        // do not happen when they should.
        for ([2]*?SnailItem{ &target.right, &target.left }) |t| {
            if (t.*) |*child| {
                switch (child.*) {
                    SnailItem.pair => |c| {
                        if (c != prev) {
                            it = c;
                            continue :target;
                        }
                    },
                    SnailItem.num => |*c| {
                        c.* += left;
                        return;
                    },
                }
            }
        }
    }
}
fn explodeRight(node: *SnailNumber) void {
    const right = node.right.?.num;
    var prev = node;
    var it = node.parent;
    while (it) |par| : ({
        prev = par;
        it = par.parent;
    }) {
        if (par.right) |r| {
            switch (r) {
                // check if it is not the exploding node
                SnailItem.pair => |p| if (p != prev) break,
                else => break,
            }
        }
    }
    target: while (it) |target| {
        // These must be _pointers_! Removing the & makes them local, so the changes
        // do not happen when they should.
        for ([2]*?SnailItem{ &target.left, &target.right }) |t| {
            if (t.*) |*child| {
                switch (child.*) {
                    SnailItem.pair => |c| {
                        if (c != prev) {
                            it = c;
                            continue :target;
                        }
                    },
                    SnailItem.num => |*c| {
                        c.* += right;
                        return;
                    },
                }
            }
        }
    }
}
fn checkExplode(a: std.mem.Allocator, node: *SnailNumber, depth: u3) ?*SnailNumber {
    // std.debug.print("\ndepth: {d} checkExplode called: ", .{depth});
    // printSnailNumber(node);
    if (depth == explode_limit) return node;
    if (node.left) |l| {
        switch (l) {
            SnailItem.pair => |n| {
                const ret = checkExplode(a, n, depth + 1);
                if (ret != null) {
                    return ret;
                }
            },
            else => {},
        }
    }
    if (node.right) |r| {
        switch (r) {
            SnailItem.pair => |n| {
                const ret = checkExplode(a, n, depth + 1);
                if (ret != null) {
                    return ret;
                }
            },
            else => {},
        }
    }
    return null;
}
fn parseSnail(a: std.mem.Allocator, in: *Str, parent: ?*SnailNumber, pos: *usize) anyerror!*SnailNumber {
    // allocate and set up new node
    const node = try a.create(SnailNumber);
    node.parent = parent;
    var right: bool = false;
    while (pos.* < in.len) : (pos.* += 1) {
        var ch = in.*[pos.*];
        switch (ch) {
            ']' => {
                break;
            },
            '[' => {
                pos.* += 1;
                if (right) {
                    node.right = SnailItem{ .pair = try parseSnail(a, in, node, pos) };
                } else {
                    node.left = SnailItem{ .pair = try parseSnail(a, in, node, pos) };
                }
            },
            ',' => {
                right = true;
            },
            else => {
                if (right) {
                    node.right = SnailItem{ .num = try std.fmt.parseUnsigned(SnailType, in.*[pos.* .. pos.* + 1], 10) };
                } else {
                    node.left = SnailItem{ .num = try std.fmt.parseUnsigned(SnailType, in.*[pos.* .. pos.* + 1], 10) };
                }
            },
        }
    }
    return node;
}
fn split(a: std.mem.Allocator, node: *SnailNumber) !void {
    if (node.left) |l| {
        switch (l) {
            SnailItem.num => |val| {
                if (val > 9) {
                    const new = try a.create(SnailNumber);
                    new.left = SnailItem{ .num = val / 2 };
                    new.right = SnailItem{ .num = val - val / 2 };
                    new.parent = node;
                    node.left = SnailItem{ .pair = new };
                    return;
                }
            },
            else => {},
        }
    }
    if (node.right) |r| {
        switch (r) {
            SnailItem.num => |val| {
                if (val > 9) {
                    const new = try a.create(SnailNumber);
                    new.left = SnailItem{ .num = val / 2 };
                    new.right = SnailItem{ .num = val - val / 2 };
                    new.parent = node;
                    node.right = SnailItem{ .pair = new };
                    return;
                }
            },
            else => {},
        }
    }
}
fn checkSplit(a: std.mem.Allocator, node: *SnailNumber) ?*SnailNumber {
    // std.debug.print("\ncheckSplit: ", .{});
    // printSnailNumber(node);
    if (node.left) |l| {
        switch (l) {
            SnailItem.pair => |n| {
                const ret = checkSplit(a, n);
                if (ret != null) return ret;
            },
            SnailItem.num => |val| if (val > 9) return node,
        }
    }
    if (node.right) |r| {
        switch (r) {
            SnailItem.pair => |n| {
                const ret = checkSplit(a, n);
                if (ret != null) return ret;
            },
            SnailItem.num => |val| if (val > 9) return node,
        }
    }
    return null;
}
fn printSnailNumber(node: *SnailNumber) void {
    std.debug.print("[", .{});
    if (node.left) |l| {
        switch (l) {
            SnailItem.num => |value| std.debug.print("{d}", .{value}),
            SnailItem.pair => |n| printSnailNumber(n),
        }
    }
    std.debug.print(",", .{});
    if (node.right) |r| {
        switch (r) {
            SnailItem.num => |value| std.debug.print("{d}", .{value}),
            SnailItem.pair => |n| printSnailNumber(n),
        }
    }
    std.debug.print("]", .{});
}
fn magnitude(node: *SnailNumber) usize {
    var left: ?usize = null;
    var right: ?usize = null;
    if (node.left) |l| {
        switch (l) {
            SnailItem.num => |value| left = value,
            SnailItem.pair => |n| left = magnitude(n),
        }
    }
    if (node.right) |r| {
        switch (r) {
            SnailItem.num => |value| right = value,
            SnailItem.pair => |n| right = magnitude(n),
        }
    }
    if (left) |l| {
        if (right) |r| {
            return 3 * l + 2 * r;
        } else {
            return l;
        }
    }
    return right.?;
}
test "day18a" {
    try std.testing.expectEqual(@as(usize, 3675), try first());
}
// test "magnitude" {
//     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
//     const allocator = arena.allocator();
//     defer arena.deinit();
//     const in = [_]Str{
//         "[[9,1],[1,9]]",
//         "[[1,2],[[3,4],5]]",
//         "[[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]",
//     };
//     const out = [_]usize{
//         129,
//         143,
//         3488,
//     };
//     for (in) |str, idx| {
//         var pos: usize = 1;
//         const root = try parseSnail(allocator, &str[0..], null, &pos);
//         try std.testing.expectEqual(out[idx], magnitude(root));
//     }
// }
// test "reduce" {
//     const tc = [_][2]Str{
//         .{ "[[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]]", "[[[[0,7],4],[[7,8],[6,0]]],[8,1]]" },
//         .{ "[[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]],[7,[[[3,7],[4,3]],[[6,3],[8,8]]]]]", "[[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]" },
//         .{ "[[[[[7,7],[7,7]],[[8,7],[8,7]]],[[[7,0],[7,7]],9]],[[[[4,2],2],6],[8,7]]]", "[[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]" },
//         .{ "[1,1]", "[1,1]" },
//     };
//     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
//     const allocator = arena.allocator();
//     defer arena.deinit();
//     for (tc) |t| {
//         std.debug.print("\n\ninput:\t{s}", .{t[0]});
//         std.debug.print("\nwant:\t{s}\n", .{t[1]});
//         var pos: usize = 1;
//         const root = try parseSnail(allocator, &t[0][0..], null, &pos);
//         try reduce(allocator, root);
//         std.debug.print("got:\t", .{});
//         printSnailNumber(root);
//     }
// }
// test "explode" {
//     const tc = [_][2]Str{
//         .{ "[[[[[9,8],1],2],3],4]", "[[[[0,9],2],3],4]" },
//         .{ "[7,[6,[5,[4,[3,2]]]]]", "[7,[6,[5,[7,0]]]]" },
//         .{ "[[6,[5,[4,[3,2]]]],1]", "[[6,[5,[7,0]]],3]" },
//         .{ "[[3,[2,[1,[7,3]]]],[6,[5,[4,[3,2]]]]]", "[[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]]" },
//         .{ "[[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]]", "[[3,[2,[8,0]]],[9,[5,[7,0]]]]" },
//         .{ "[[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]]", "[[[[0,7],4],[7,[[8,4],9]]],[1,1]]" },
//         .{ "[[[[0,7],4],[7,[[8,4],9]]],[1,1]]", "[[[[0,7],4],[15,[0,13]]],[1,1]]" },
//         .{ "", "" },
//     };
//     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
//     const allocator = arena.allocator();
//     defer arena.deinit();
//     for (tc) |t| {
//         std.debug.print("\nwant:\t{s} input: {s}\n", .{ t[1], t[0] });
//         var pos: usize = 1;
//         const root = try parseSnail(allocator, &t[0][0..], null, &pos);
//         explode(allocator, checkExplode(allocator, root, 0).?);
//         std.debug.print("got:\t", .{});
//         printSnailNumber(root);
//         try std.testing.expect(1 == 1);
//     }
// }
// test "split" {
//     const tc = [_][2]Str{
//         .{ "[[[[0,7],4],[7,[[8,4],9]]],[1,1]]", "[[[[0,7],4],[[7,8],[0,13]]],[1,1]]" },
//     };
//     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
//     const allocator = arena.allocator();
//     defer arena.deinit();
//     for (tc) |t| {
//         std.debug.print("\nwant:\t{s} input: {s}\n", .{ t[1], t[0] });
//         var pos: usize = 1;
//         const root = try parseSnail(allocator, &t[0][0..], null, &pos);
//         explode(allocator, checkExplode(allocator, root, 0).?);
//         try split(allocator, checkSplit(allocator, root).?);
//         std.debug.print("got:\t", .{});
//         printSnailNumber(root);
//         try std.testing.expect(1 == 1);
//     }
// }