#include <iostream>
#include <iomanip>
#include <bitset>

template <typename TCont>
bool valid_index(uint8_t v1, uint8_t v2, TCont& slots) {
    uint8_t index = static_cast<uint8_t>(v1 + v2) >> 4;
    if (index == 0) { // Index 0 is invalid
        return false;
    }
    if (slots[index] == 0) { // An empty slot is valid
        slots[index] = v1;
        return true;
    }
    // A collision is valid only if they share the lowest index
    return (slots[index] == v1);    
}

int main()
{
    unsigned long long count = 0;
    unsigned long long valid_count = 0;

    // For every sorted combination of 5 indexes
    const uint8_t step = 0b0000'0010;
    for (uint8_t i1 = 0b0001'0000; i1; i1 += step)
    for (uint8_t i2 = 0b0001'0000 + (i1 & 0xF0); i2; i2 += step)
    for (uint8_t i3 = 0b0001'0000 + (i2 & 0xF0); i3; i3 += step)
    for (uint8_t i4 = 0b0001'0000 + (i3 & 0xF0); i4; i4 += step)
    for (uint8_t i5 = 0b0001'0000 + (i4 & 0xF0); i5; i5 += step) {
        ++count;
        
        uint8_t slots[16] = {};
        if (valid_index(i1, 0, slots) &&
            valid_index(i2, 0, slots) &&
            valid_index(i3, 0, slots) &&
            valid_index(i4, 0, slots) &&
            valid_index(i5, 0, slots) &&
            valid_index(i1, i2, slots) &&
            valid_index(i1, i3, slots) &&
            valid_index(i1, i4, slots) &&
            valid_index(i1, i5, slots) &&
            valid_index(i2, i3, slots) &&
            valid_index(i2, i4, slots) &&
            valid_index(i2, i5, slots) &&
            valid_index(i3, i4, slots) &&
            valid_index(i3, i5, slots) &&
            valid_index(i4, i5, slots) &&
            valid_index(i1, i2 + i3, slots) &&
            valid_index(i1, i2 + i4, slots) &&
            valid_index(i1, i2 + i5, slots) &&
            valid_index(i1, i3 + i4, slots) &&
            valid_index(i3, i3 + i5, slots) &&
            valid_index(i1, i4 + i5, slots) &&
            valid_index(i2, i3 + i4, slots) &&
            valid_index(i2, i3 + i5, slots) &&
            valid_index(i2, i4 + i5, slots) &&
            valid_index(i3, i4 + 15, slots) &&
            valid_index(i1, i2 + i3 + i4, slots) &&
            valid_index(i1, i2 + i3 + i5, slots) &&
            valid_index(i1, i2 + i4 + i5, slots) &&
            valid_index(i1, i3 + i4 + i5, slots) &&
            valid_index(i2, i3 + i4 + i5, slots) &&
            valid_index(i1, i2 + i3 + i4 + i5, slots))
        {
            ++valid_count;
            std::cout << "Valid combination: ";
            std::cout << std::setw(10) << (i1 / 16.0);
            std::cout << std::setw(10) << (i2 / 16.0);
            std::cout << std::setw(10) << (i3 / 16.0);
            std::cout << std::setw(10) << (i4 / 16.0);
            std::cout << std::setw(10) << (i5 / 16.0) << "\n";

            auto magic = 60ull << 56;
            magic |= static_cast<uint64_t>(i1) << (60 - 53 - 4); // F7
            magic |= static_cast<uint64_t>(i2) << (60 - 44 - 4); // E6
            magic |= static_cast<uint64_t>(i3) << (60 - 35 - 4); // D5
            magic |= static_cast<uint64_t>(i4) << (60 - 26 - 4); // C4
            magic |= static_cast<uint64_t>(i5) << (60 - 17 - 4); // B3
            std::cout << "Magic: " << std::hex << magic << std::dec;
            std::cout << "  " << std::bitset<64>(magic) << "\n\n";
        }
    }

    std::cout << valid_count << "/" << count << std::endl;
}