const std = @import("std");
const path = "../data/day12/input.txt";
const RetType = u13;
const Str = []const u8;
const Routes = std.StringHashMap(std.ArrayList(Str));
const Seen = std.StringHashMap(void);
fn parseInput(a: std.mem.Allocator) anyerror!Routes {
    const input = @embedFile(path);
    var lines = std.mem.tokenize(u8, input, "\n");
    var ret = Routes.init(a);
    while (lines.next()) |line| {
        var from_to = std.mem.tokenize(u8, line, "-");
        const left = from_to.next().?;
        const right = from_to.next().?;
        // discard invalid routes
        if (!std.mem.eql(u8, right, "start") and (!std.mem.eql(u8, left, "end"))) {
            var left_array = try ret.getOrPut(left);
            if (!left_array.found_existing) {
                left_array.value_ptr.* = std.ArrayList(Str).init(a);
            }
            try left_array.value_ptr.append(right);
        }
        if (!std.mem.eql(u8, left, "start") and (!std.mem.eql(u8, right, "end"))) {
            var right_array = try ret.getOrPut(right);
            if (!right_array.found_existing) {
                right_array.value_ptr.* = std.ArrayList(Str).init(a);
            }
            try right_array.value_ptr.append(left);
        }
    }
    return ret;
}
pub fn first() anyerror!RetType {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    var cave = try parseInput(allocator);
    var seen = Seen.init(allocator);
    defer {
        var it = cave.valueIterator();
        while (it.next()) |arr_list| {
            arr_list.deinit();
        }
        cave.deinit();
        seen.deinit();
    }
    return try genRoutes(&seen, &cave, "start");
}
fn genRoutes(seen: *Seen, routes: *Routes, root: Str) anyerror!RetType {
    var sum: RetType = 0;
    // reached "end", return
    if (std.mem.eql(u8, root, "end")) {
        sum += 1;
        return sum;
    }
    // already visited, no-go
    if (seen.contains(root)) {
        return 0;
    }
    // add lowercase to seen
    if ((root[0] > 96) and (!std.mem.eql(u8, root, "end"))) {
        try seen.put(root, {});
    }
    // take all the routes
    for (routes.get(root).?.items) |item| {
        sum += try genRoutes(seen, routes, item);
    }
    // reuse caves
    _ = seen.remove(root);
    return sum;
}
pub fn main() anyerror!void {
    var timer = try std.time.Timer.start();
    const ret = try first();
    const t = timer.lap() / 1000;
    try std.testing.expectEqual(@as(RetType, 5212), ret);
    std.debug.print("Day 12a result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
test "day12a" {
    try std.testing.expectEqual(@as(RetType, 5212), try first());
}

pf-pk
ZQ-iz
iz-NY
ZQ-end
pf-gx
pk-ZQ
ZQ-dc
NY-start
NY-pf
NY-gx
ag-ZQ
pf-start
start-gx
BN-ag
iz-pf
ag-FD
pk-NY
gx-pk
end-BN
ag-pf
iz-pk
pk-ag
iz-end
iz-BN