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}us\n", .{ ret, t });
}

test "day12a" {
    try std.testing.expectEqual(@as(RetType, 5212), try first(std.testing.allocator));
}