const std = @import("std");
pub const log_level: std.log.Level = .info;

pub fn main() !void {
    try std.fmt.format(std.io.getStdOut().writer(), "Day 8 pt1: {}\n", .{try solve_pt1(std.heap.page_allocator, puzzle_input)});
    try std.fmt.format(std.io.getStdOut().writer(), "Day 8 pt2: {}\n", .{try solve_pt2(std.heap.page_allocator, puzzle_input)});
}
const NodeValue = struct {
    left: []const u8,
    right: []const u8,
};

fn solve_pt1(a: std.mem.Allocator, input: []const u8) !u64 {
    var spl = std.mem.split(u8, input, "\n\n");
    const instructions = spl.first();
    const nodes_str = spl.next() orelse return error.NoNodes;
    var spl2 = std.mem.split(u8, nodes_str, "\n");
    var nodes = std.StringHashMap(NodeValue).init(a);
    defer nodes.deinit();
    while (spl2.next()) |node_line| {
        var toks = std.mem.tokenize(u8, node_line, " (,)=");
        const key = toks.next() orelse return error.NoKey;
        const left = toks.next() orelse return error.NoLeft;
        const right = toks.next() orelse return error.NoRight;
        try nodes.putNoClobber(key, .{
            .left = left,
            .right = right,
        });
    }

    var steps: u64 = 0;
    var pos: []const u8 = "AAA";
    while (!std.mem.eql(u8, pos, "ZZZ")) {
        for (instructions) |inst| {
            const node_value = nodes.get(pos).?;
            pos = switch (inst) {
                'R' => node_value.right,
                'L' => node_value.left,
                else => return error.InvalidDirection,
            };
            steps += 1;
        }
    }
    return steps;
}
test "pt1" {
    try std.testing.expectEqual(@as(u64, 6), try solve_pt1(std.testing.allocator, test_input));
}
const HistEntry = struct {
    node: []const u8,
    step: u64,
};
const Path = struct {
    // current position
    pos: []const u8,

    // list of the _endpoints_ we have reached.
    endpoints: std.ArrayList(HistEntry),

    // at n*cycle + offset this path is finished where n is integer > 0
    offset: ?u64 = null,
    cycle: ?u64 = null,

    fn init(a: std.mem.Allocator, start: []const u8) !Path {
        return .{
            .pos = start,
            .endpoints = std.ArrayList(HistEntry).init(a),
        };
    }

    fn visit(self: *Path, node: []const u8) void {
        self.pos = node;
    }

    fn check(self: *Path, step: u64) !void {
        if (self.cycle != null) return; // we already found the cycle for this one

        if (self.pos[2] == 'Z') { // we hit an endpoint
            for (self.endpoints.items) |hi| { // did we aleady hit this endpoint?
                if (std.mem.eql(u8, hi.node, self.pos)) {
                    self.offset = hi.step;
                    self.cycle = step - hi.step;
                    return;
                }
            }
            try self.endpoints.append(.{ .node = self.pos, .step = step });
        }
    }
};
fn solve_pt2(a: std.mem.Allocator, input: []const u8) !u64 {
    var spl = std.mem.split(u8, input, "\n\n");
    const instructions = spl.first();
    const nodes_str = spl.next() orelse return error.NoNodes;
    var spl2 = std.mem.split(u8, nodes_str, "\n");
    var nodes = std.StringHashMap(NodeValue).init(a);
    defer nodes.deinit();
    while (spl2.next()) |node_line| {
        var toks = std.mem.tokenize(u8, node_line, " (,)=");
        const key = toks.next() orelse return error.NoKey;
        const left = toks.next() orelse return error.NoLeft;
        const right = toks.next() orelse return error.NoRight;
        try nodes.putNoClobber(key, .{
            .left = left,
            .right = right,
        });
    }

    var pos: []Path = blk: {
        var pl = std.ArrayList(Path).init(a);
        defer pl.deinit();
        var ki = nodes.keyIterator();
        while (ki.next()) |k| {
            if (k.*[2] == 'A') { // ends with an A
                std.log.info("start pos {s}", .{k.*});
                try pl.append(try Path.init(a, k.*));
            }
        }
        break :blk try pl.toOwnedSlice();
    };
    defer a.free(pos);

    var log = std.time.timestamp() + 10;

    var steps: u64 = 0;
    while (!ends(pos)) {
        // > repeat the whole sequence of instructions as necessary
        // always repeat the whole set
        for (instructions) |inst| {
            for (pos) |*p| {
                const node_value = nodes.get(p.pos).?;
                p.visit(switch (inst) {
                    'R' => node_value.right,
                    'L' => node_value.left,
                    else => return error.InvalidDirection,
                });
            }
        }
        steps += instructions.len;

        // logging...
        const now = std.time.timestamp();
        if (now > log) {
            for (pos) |p| {
                std.log.info("pos {s}", .{p.pos});
            }
            log = now + 10;
        }

        // now check for cycles
        for (pos) |*p| {
            try p.check(steps);
        }
        // now... check if we have detected a cycle on _all_ tracks
        for (pos) |p| {
            if (p.cycle == null) break;
        } else {
            std.log.info("all routes have cycled, using LCM", .{});
            // great, so we haven't reached the end but we can probably calculate it.
            var l = lcm(pos[0].cycle.?, pos[1].cycle.?);
            for (pos[2..]) |p| {
                l = lcm(l, p.cycle.?);
            }
            // so, this is our answer?
            return l;
        }
    }
    return steps;
}

fn ends(pos: []Path) bool {
    for (pos) |p| {
        if (p.pos[2] != 'Z') {
            return false;
        }
    } else {
        std.log.err("ends true", .{});
        for (pos) |p| {
            std.log.err("{s}", .{p.pos});
        }
        return true;
    }
}
fn lcm(a: u64, b: u64) u64 {
    return (a * b) / std.math.gcd(a, b);
}
test "pt2" {
    try std.testing.expectEqual(@as(u64, 6), try solve_pt2(std.testing.allocator, test_input2));
}
const test_input =
    \\LLR
    \\
    \\AAA = (BBB, BBB)
    \\BBB = (AAA, ZZZ)
    \\ZZZ = (ZZZ, ZZZ)
;
const test_input2 =
    \\LR
    \\
    \\11A = (11B, XXX)
    \\11B = (XXX, 11Z)
    \\11Z = (11B, XXX)
    \\22A = (22B, XXX)
    \\22B = (22C, 22C)
    \\22C = (22Z, 22Z)
    \\22Z = (22B, 22B)
    \\XXX = (XXX, XXX)
;
const puzzle_input = @embedFile("day8.in");