#import "File";
#import "Basic";
#import "String";

ZERO :: #run to_u128(cast(u8)0);
ONE :: #run to_u128(cast(u8)1);
MEMO_SIZE_1 :: 50;
MEMO_SIZE_2 :: 128;
solve_day12 :: (test: bool) {

    contents := read_entire_file(ifx test then "inputs/day12_test.txt" else "inputs/day12.txt");
    lines := split(contents, "\n");

    part1 := 0;
    part2 := 0;

    t: U128;

    memo := NewArray(MEMO_SIZE_1 * MEMO_SIZE_2, s64);

    numbers_part1: [..]u8;
    numbers_part2: [..]u8;

    for line: lines {
        memset(memo.data, 255, memo.count * size_of(s64));

        array_reset_keeping_memory(*numbers_part1);
        array_reset_keeping_memory(*numbers_part2);
        possible_slots: U128 = ZERO;
        must_slots: U128 = ZERO;

        space_index := find_index_from_left(line, #char " ");

        number_split := split(slice(line, space_index + 1, line.count), ",");

        //print("'%'\n", slice(line, 0, space_index));
        for 0..space_index - 1 {
            c := line[it];

            if c == #char "?" {
                possible_slots = possible_slots | (ONE << cast(u8) it);
            } else if c == #char "#" {
                must_slots = must_slots | (ONE << cast(u8) it);
            }
        }

        possible_slots = possible_slots | must_slots;

        accum: u32 = 0;

        for number_split {
            num := string_to_int(it, 10, u8);
            accum += num;
            array_add(*numbers_part1, num);
        }

        accum += cast(u32)(numbers_part1.count - 1);

        current_slots: U128;

        part1 += count_possiblities(xx space_index, 0, accum - numbers_part1[0], numbers_part1, current_slots, possible_slots, must_slots, memo);

        possible_slots2 := possible_slots;
        must_slots2 := must_slots;
        array_add(*numbers_part2, ..numbers_part1);

        for 0..3 {
            array_add(*numbers_part2, ..numbers_part1);
            possible_slots2 = possible_slots2 | (possible_slots2 << cast(u8)(space_index + 1));
            possible_slots2 = possible_slots2 | (ONE << cast(u8)space_index);
            must_slots2 = must_slots2 | (must_slots2 << cast(u8)(space_index + 1));
        }

        accum = 0;

        for numbers_part2 {
            accum += it;
        }

        accum += xx (numbers_part2.count - 1);

        memset(memo.data, 255, memo.count * size_of(s64));

        //print("Numbers count: %\n", numbers_part2.count);

        part2 += count_possiblities(xx (4 + 5 * space_index), 0, accum - numbers_part2[0], numbers_part2, current_slots, possible_slots2, must_slots2, memo);

    }

    print("Part 1: %\n", part1);
    print("Part 2: %\n", part2);
}

count_possiblities :: (bitfield_length: u32, offset: u32, bits_left: u32, numbers: []u8, current_slots: U128, possible_slots: U128, must_slots: U128, memo: []s64) -> s64 {
    if numbers.count == 0  return 0;

    number := numbers[0];
    result: s64 = 0;

    if bits_left + offset > bitfield_length  return 0;

    must_slots_capped2 := ((ONE << cast(u8)offset) - ONE) & must_slots;
    must_slots_capped := ((ONE << xx (number + offset + 1)) - ONE) & must_slots;


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

    memo_num := memo[offset * MEMO_SIZE_1 + numbers.count];
    if memo_num != -1 {
        return memo_num;
    }

    for offset..bitfield_length - bits_left - 1 {
        n1 := (ONE << number);
        n2 := n1 - ONE;
        numbers_bits := (n2 << cast(u8)it);

        np := numbers_bits & possible_slots;
        if np == numbers_bits {
            cnm := (current_slots | numbers_bits) & must_slots_capped;
            if cnm == must_slots_capped {
                cnm3 := (current_slots | numbers_bits) & must_slots;
                if numbers.count == 1 && cnm3 == must_slots {
                    result += 1;
                } else if numbers.count > 1 && bits_left >= (numbers[1] + 1) {
                    result += count_possiblities(bitfield_length, it + number + 1, bits_left - numbers[1] - 1, array_view(numbers, 1, numbers.count - 1), current_slots | numbers_bits, possible_slots, must_slots, memo);
                }
            }
        }
    }

    memo[offset * MEMO_SIZE_1 + numbers.count] = result;

    return result;
}

operator | :: (a: U128, b: U128) -> U128 {
    return .{
        low = a.low | b.low,
        high = a.high | b.high,
    };
}

operator & :: (a: U128, b: U128) -> U128 {
    return .{
        low = a.low & b.low,
        high = a.high & b.high,
    };
}