const std = @import("std");

const ArrayList = std.ArrayList;

pub fn solve_part1() !void {
    var inputs = try std.fs.cwd().openFile("inputs/day12.txt", .{});
    var buffered_reader = std.io.bufferedReader(inputs.reader());
    var in_stream = buffered_reader.reader();

    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    var allocator = arena.allocator();

    var buffer: [1024]u8 = undefined;

    var result: u64 = 0;
    var result2: u64 = 0;
    var numbers = ArrayList(u8).init(allocator);
    var numbers_part2 = ArrayList(u8).init(allocator);
    defer numbers.deinit();
    defer numbers_part2.deinit();

    var memo: [][50]?u64 = try allocator.alloc([50]?u64, 128);
    var timer = try std.time.Timer.start();

    while (try in_stream.readUntilDelimiterOrEof(&buffer, '\n')) |line| {
        @memset(memo, [_]?u64{null} ** 50);
        defer numbers.clearRetainingCapacity();
        defer numbers_part2.clearRetainingCapacity();
        var possible_slots: u128 = 0;
        var must_slots: u128 = 0;

        var space_index = std.mem.indexOfScalar(u8, line, ' ').?;

        var number_split = std.mem.splitScalar(u8, line[space_index + 1 ..], ',');

        for (line[0..space_index], 0..) |c, i| {
            if (c == '?') {
                possible_slots |= @as(u128, 1) << @intCast(i);
            }

            if (c == '#') {
                must_slots |= @as(u128, 1) << @intCast(i);
            }
        }

        possible_slots |= must_slots;

        var accum: u32 = 0;
        while (number_split.next()) |number| {
            var num = try std.fmt.parseInt(u8, number, 10);
            accum += num;
            try numbers.append(num);
        }

        accum += @intCast(numbers.items.len - 1);

        var length: u32 = @intCast(space_index);
        var current_slots: u128 = 0;

        var n = count_possiblities(length, 0, accum - numbers.items[0], numbers.items, current_slots, possible_slots, must_slots, memo);

        var possible_slots2: u128 = possible_slots;
        var must_slots2: u128 = must_slots;
        try numbers_part2.appendSlice(numbers.items);

        for (0..4) |i| {
            _ = i;
            try numbers_part2.appendSlice(numbers.items);
            possible_slots2 |= possible_slots2 << @intCast(length + 1);
            possible_slots2 |= @as(u128, 1) << @intCast(length);
            must_slots2 |= must_slots2 << @intCast(length + 1);
        }

        accum = 0;

        for (numbers_part2.items) |nn| {
            accum += nn;
        }

        accum += @intCast(numbers_part2.items.len - 1);

        @memset(memo, [_]?u64{null} ** 50);
        var n2 = count_possiblities(length * 5 + 4, 0, accum - numbers_part2.items[0], numbers_part2.items, current_slots, possible_slots2, must_slots2, memo);

        result += n;
        result2 += n2;
    }
    var time = timer.read();
    std.log.info("Result: {d}", .{result});
    std.log.info("Result 2: {d}", .{result2});
    std.log.info("Time: {d}", .{time});
}

fn count_possiblities(bitfield_length: u32, offset: u32, bits_left: u32, numbers: []u8, current_slots: u128, possible_slots: u128, must_slots: u128, memo: [][50]?u64) u64 {
    if (numbers.len == 0) {
        return 0;
    }

    var number: u8 = numbers[0];
    var result: u64 = 0;

    if (bits_left + offset > bitfield_length) {
        return 0;
    }

    var must_slots_capped2 = ((@as(u128, 1) << @intCast(offset)) - 1) & must_slots;
    var must_slots_capped = ((@as(u128, 1) << @intCast(number + offset + 1)) - 1) & must_slots;

    if (current_slots & must_slots_capped2 != must_slots_capped2) {
        return 0;
    }

    if (memo[offset][numbers.len]) |i| {
        return i;
    }

    for (offset..bitfield_length - bits_left) |i| {
        var number_bits = (@as(u128, 1) << @intCast(number)) - 1 << @intCast(i);

        if (number_bits & possible_slots == number_bits) {
            if ((current_slots | number_bits) & must_slots_capped == must_slots_capped) {
                if (numbers.len == 1 and (current_slots | number_bits) & must_slots == must_slots) {
                    result += 1;
                } else if (numbers.len > 1 and bits_left >= numbers[1] + 1) {
                    result += count_possiblities(bitfield_length, @intCast(i + number + 1), bits_left - numbers[1] - 1, numbers[1..], current_slots | number_bits, possible_slots, must_slots, memo);
                }
            }
        }
    }

    memo[offset][numbers.len] = result;

    return result;
}