const DAYS = 8;

const DAYS = 9;

    const day09 = @import("day09.zig");

    _ = @import("day09.zig");

Tristram to AlphaCentauri = 34
Tristram to Snowdin = 100
Tristram to Tambi = 63
Tristram to Faerun = 108
Tristram to Norrath = 111
Tristram to Straylight = 89
Tristram to Arbre = 132
AlphaCentauri to Snowdin = 4
AlphaCentauri to Tambi = 79
AlphaCentauri to Faerun = 44
AlphaCentauri to Norrath = 147
AlphaCentauri to Straylight = 133
AlphaCentauri to Arbre = 74
Snowdin to Tambi = 105
Snowdin to Faerun = 95
Snowdin to Norrath = 48
Snowdin to Straylight = 88
Snowdin to Arbre = 7
Tambi to Faerun = 68
Tambi to Norrath = 134
Tambi to Straylight = 107
Tambi to Arbre = 40
Faerun to Norrath = 11
Faerun to Straylight = 66
Faerun to Arbre = 144
Norrath to Straylight = 115
Norrath to Arbre = 135
Straylight to Arbre = 127

const std = @import("std");
const Str = []const u8;
const PATH = "input/day09.txt";
const CostType = u10;
const RouteItem = struct {
    from: Str,
    to: Str,
    cost: CostType,
};
const Routes = []RouteItem;
const Visited = std.StringHashMap(void);
pub fn first(allocator: std.mem.Allocator) !usize {
    var arena = std.heap.ArenaAllocator.init(allocator);
    defer arena.deinit();
    var routes = try parseRoutes(allocator, @embedFile(PATH));
    defer allocator.free(routes);
    var min: usize = std.math.maxInt(usize);
    var i: usize = 0;
    while (i < 8) : (i += 1) {
        var visited = Visited.init(arena.allocator());
        defer visited.deinit();
        var sum: usize = 0;
        var next: Str = if (i == 0) routes[i].from else routes[i - 1].to;
        while (visited.count() != 7) {
            try visited.put(next, {});
            var shortest: struct { city: Str, cost: CostType } = .{ .city = undefined, .cost = std.math.maxInt(CostType) };
            for (routes) |route| {
                const dest = if (std.mem.eql(u8, next, route.from)) route.to else if (std.mem.eql(u8, next, route.to))
                    route.from
                else
                    continue;
                if (visited.contains(dest)) continue;
                if (route.cost < shortest.cost) {
                    shortest.cost = route.cost;
                    shortest.city = try std.fmt.allocPrint(arena.allocator(), "{s}", .{dest});
                }
            }
            sum += shortest.cost;
            next = shortest.city;
        }
        if (sum < min) min = sum;
    }
    return min;
}
pub fn second(allocator: std.mem.Allocator) !usize {
    var arena = std.heap.ArenaAllocator.init(allocator);
    defer arena.deinit();
    var routes = try parseRoutes(allocator, @embedFile(PATH));
    defer allocator.free(routes);
    var max: usize = 0;
    var i: usize = 0;
    while (i < 8) : (i += 1) {
        var visited = Visited.init(arena.allocator());
        defer visited.deinit();
        var sum: usize = 0;
        var next: Str = if (i == 0) routes[i].from else routes[i - 1].to;
        while (visited.count() != 7) {
            try visited.put(next, {});
            var longest: struct { city: Str, cost: CostType } = .{ .city = undefined, .cost = 0 };
            for (routes) |route| {
                const dest = if (std.mem.eql(u8, next, route.from)) route.to else if (std.mem.eql(u8, next, route.to))
                    route.from
                else
                    continue;
                if (visited.contains(dest)) continue;
                if (route.cost > longest.cost) {
                    longest.cost = route.cost;
                    longest.city = try std.fmt.allocPrint(arena.allocator(), "{s}", .{dest});
                }
            }
            sum += longest.cost;
            next = longest.city;
        }
        if (sum > max) max = sum;
    }
    return max;
}
fn parseRoutes(allocator: std.mem.Allocator, input: Str) !Routes {
    var routes = std.ArrayList(RouteItem).init(allocator);
    defer routes.deinit();
    var lines = std.mem.tokenize(u8, input, "\n");
    while (lines.next()) |line| {
        var words = std.mem.tokenize(u8, line, " ");
        const from = words.next().?;
        _ = words.next(); // drop 'to'
        const to = words.next().?;
        _ = words.next(); // drop '='
        const cost = try std.fmt.parseUnsigned(CostType, words.next().?, 10);
        try routes.append(RouteItem{ .from = from, .to = to, .cost = cost });
    }
    return routes.toOwnedSlice();
}
test "day09a" {
    try std.testing.expectEqual(@as(usize, 251), try first(std.testing.allocator));
}
test "day09b" {
    try std.testing.expectEqual(@as(usize, 898), try second(std.testing.allocator));
}