const std = @import("std");

const PATH = "input/day17.txt";
const Str = []const u8;

const BUCKETS = std.mem.count(u8, @embedFile(PATH), "\n");
const BucketType = u6;
const MaskSize = std.meta.Int(.unsigned, 20);

pub fn first(allocator: std.mem.Allocator) !usize {
    const buckets = try parseInput(allocator, @embedFile(PATH));
    defer allocator.free(buckets);

    var used = std.StaticBitSet(BUCKETS).initEmpty();

    var sets = std.ArrayList(MaskSize).init(allocator);
    defer sets.deinit();

    try recurse(buckets, 0, 150, &used, &sets);

    return sets.items.len;
}

pub fn second(allocator: std.mem.Allocator) !usize {
    const buckets = try parseInput(allocator, @embedFile(PATH));
    defer allocator.free(buckets);

    var used = std.StaticBitSet(BUCKETS).initEmpty();

    var sets = std.ArrayList(MaskSize).init(allocator);
    defer sets.deinit();

    try recurse(buckets, 0, 150, &used, &sets);

    var min = std.AutoHashMap(usize, usize).init(allocator);
    defer min.deinit();

    var min_cont: usize = std.math.maxInt(usize);

    for (sets.items) |item| {
        const count = @popCount(item);
        if (count < min_cont) min_cont = count;

        const res = try min.getOrPut(count);
        if (res.found_existing) res.value_ptr.* += 1 else res.value_ptr.* = 1;
    }

    return min.get(min_cont).?;
}

test "day17a" {
    try std.testing.expectEqual(@as(usize, 654), try first(std.testing.allocator));
}

test "day17b" {
    try std.testing.expectEqual(@as(usize, 57), try second(std.testing.allocator));
}

fn recurse(
    buckets: []BucketType,
    start: usize,
    liters: usize,
    used: *std.StaticBitSet(BUCKETS),
    sets: *std.ArrayList(MaskSize),
) !void {
    if (liters == 0) {
        try sets.append(used.mask);
        return;
    }

    var idx: usize = start;
    while (idx < buckets.len) : (idx += 1) {
        if (!used.isSet(idx)) {
            if (buckets[idx] <= liters) {
                used.set(idx);
                try recurse(buckets, idx, liters - buckets[idx], used, sets);
                used.unset(idx);
            }
        }
    }
}

fn parseInput(allocator: std.mem.Allocator, in: Str) ![]BucketType {
    var ret = std.ArrayList(BucketType).init(allocator);
    defer ret.deinit();

    var lines = std.mem.tokenize(u8, in, "\n");
    while (lines.next()) |line| {
        try ret.append(try std.fmt.parseUnsigned(BucketType, line, 10));
    }

    return try ret.toOwnedSlice();
}

const test_input =
    \\20
    \\15
    \\10
    \\5
    \\5
;