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));
}