const std = @import("std");
const path = "../data/day12/input.txt";
const RetType = u20;
const Str = []const u8;
const CaveID = u12; // there are 11 caves in input + 1 for the doble cave bit
const CaveInfo = struct {
    ID: CaveID,
    paths: std.ArrayList(Str),
};
const Routes = std.StringHashMap(CaveInfo);
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);
    var counter: u4 = 0;
    while (lines.next()) |line| {
        var from_to = std.mem.tokenize(u8, line, "-");
        const left = from_to.next().?;
        const right = from_to.next().?;
        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.*.paths = std.ArrayList(Str).init(a);
                left_array.value_ptr.*.ID = @as(CaveID, 1) << counter;
                counter += 1;
            }
            try left_array.value_ptr.paths.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.*.paths = std.ArrayList(Str).init(a);
                right_array.value_ptr.*.ID = @as(CaveID, 1) << counter;
                counter += 1;
            }
            try right_array.value_ptr.paths.append(left);
        }
    }
    return ret;
}
const CacheKey = struct {
    root: CaveID,
    seen: CaveID,
};
const Cache = std.AutoHashMap(CacheKey, RetType);
pub fn second() anyerror!RetType {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    var cave = try parseInput(allocator);
    var seen: CaveID = 0;
    var cache = Cache.init(allocator);
    defer {
        var it = cave.valueIterator();
        while (it.next()) |arr_list| {
            arr_list.paths.deinit();
        }
        cave.deinit();
        cache.deinit();
    }
    return try genRoutes(seen, &cave, "start", &cache);
}
const double_cave = @as(CaveID, 1) << 11;
fn genRoutes(seen: CaveID, routes: *Routes, root: Str, cache: *Cache) anyerror!RetType {
    var sum: RetType = 0;
    const root_item = routes.get(root).?;
    if (cache.get(CacheKey{ .root = root_item.ID, .seen = seen })) |r| {
        return r;
    }
    for (root_item.paths.items) |item| {
        if (std.mem.eql(u8, item, "end")) {
            sum += 1;
            continue;
        }
        const next_item = routes.get(item).?;
        if (seen & next_item.ID == 0) {
            var mark = seen;
            if (root[0] > 96) mark |= root_item.ID;
            sum += try genRoutes(mark, routes, item, cache);
        } else if (seen & double_cave == 0) {
            var mark = seen;
            if (root[0] > 96) mark |= root_item.ID;
            sum += try genRoutes(mark | double_cave, routes, item, cache);
        }
    }
    try cache.put(CacheKey{ .root = root_item.ID, .seen = seen }, sum);
    return sum;
}
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());
}

### First version: (*_without_memo.zig)

trying all the paths increasing the counter on every `end` reach. I only collent

trying all the paths increasing the counter on every `end` reach. I only collect

### Final version
Instead of a `std.StringHashMap(void)` I have used a bitmap for representing
seen caves (this could be further simplified by only tracking lowercase caves.
In the second part I use an other bit for marking if double lowercase cave is
used or not.
The main optimization here is using memoization for storing the alredy generated
states.
First part is 1.2 ms, second part is 2.5ms (more than 100x faster).