const day12a = @import("day12a.zig");
const day12b = @import("day12b.zig");

    _ = try day12a.first();
    _ = try day12b.second();

const std = @import("std");
const path = "../data/day12/input.txt";
const RetType = u18;
const Str = []const u8;
const Routes = std.StringHashMap(std.ArrayList(Str));
const Seen = std.StringHashMap(u2);
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 second() 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 (seenTooMuch(seen, root)) {
        return 0;
    }
    // add lowercase to seen
    if ((root[0] > 96) and (!std.mem.eql(u8, root, "end"))) {
        const ptr = seen.getPtr(root);
        if (ptr == null) {
            try seen.put(root, 1);
        } else {
            ptr.?.* +|= 1;
        }
    }
    // take all the routes
    for (routes.get(root).?.items) |item| {
        sum += try genRoutes(seen, routes, item);
    }
    // reuse caves
    const ptr = seen.getPtr(root);
    if (ptr != null) {
        ptr.?.* -= 1;
    }
    return sum;
}
fn seenTooMuch(seen: *Seen, root: Str) bool {
    const v = seen.get(root) orelse return false;
    if (v >= 2) {
        return true;
    }
    if (v == 0) {
        return false;
    }
    if (v == 1) {
        var it = seen.iterator();
        while (it.next()) |entry| {
            if (std.mem.eql(u8, entry.key_ptr.*, root)) continue;
            if (entry.value_ptr.* > 1) {
                return true;
            }
        }
    }
    return false;
}
pub fn main() anyerror!void {
    var timer = try std.time.Timer.start();
    const ret = try second();
    const t = timer.lap() / 1000;
    try std.testing.expectEqual(@as(RetType, 134862), ret);
    std.debug.print("Day 12b result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
test "day12b" {
    try std.testing.expectEqual(@as(RetType, 134862), try second());
}

const days = 11;

const days = 12;