const DAYS = 16;

const DAYS = 17;

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

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

50
44
11
49
42
46
18
32
26
40
21
7
18
43
10
47
36
24
22
40

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
;