fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <bitset>
  4.  
  5. template <typename TCont>
  6. bool valid_index(uint8_t v1, uint8_t v2, TCont& slots) {
  7.     uint8_t index = static_cast<uint8_t>(v1 + v2) >> 4;
  8.     if (index == 0) { // Index 0 is invalid
  9.         return false;
  10.     }
  11.     if (slots[index] == 0) { // An empty slot is valid
  12.         slots[index] = v1;
  13.         return true;
  14.     }
  15.     // A collision is valid only if they share the lowest index
  16.     return (slots[index] == v1);    
  17. }
  18.  
  19. int main()
  20. {
  21.     unsigned long long count = 0;
  22.     unsigned long long valid_count = 0;
  23.  
  24.     // For every sorted combination of 5 indexes
  25.     const uint8_t step = 0b0000'0010;
  26.     for (uint8_t i1 = 0b0001'0000; i1; i1 += step)
  27.     for (uint8_t i2 = 0b0001'0000 + (i1 & 0xF0); i2; i2 += step)
  28.     for (uint8_t i3 = 0b0001'0000 + (i2 & 0xF0); i3; i3 += step)
  29.     for (uint8_t i4 = 0b0001'0000 + (i3 & 0xF0); i4; i4 += step)
  30.     for (uint8_t i5 = 0b0001'0000 + (i4 & 0xF0); i5; i5 += step) {
  31.         ++count;
  32.  
  33.         uint8_t slots[16] = {};
  34.         if (valid_index(i1, 0, slots) &&
  35.             valid_index(i2, 0, slots) &&
  36.             valid_index(i3, 0, slots) &&
  37.             valid_index(i4, 0, slots) &&
  38.             valid_index(i5, 0, slots) &&
  39.             valid_index(i1, i2, slots) &&
  40.             valid_index(i1, i3, slots) &&
  41.             valid_index(i1, i4, slots) &&
  42.             valid_index(i1, i5, slots) &&
  43.             valid_index(i2, i3, slots) &&
  44.             valid_index(i2, i4, slots) &&
  45.             valid_index(i2, i5, slots) &&
  46.             valid_index(i3, i4, slots) &&
  47.             valid_index(i3, i5, slots) &&
  48.             valid_index(i4, i5, slots) &&
  49.             valid_index(i1, i2 + i3, slots) &&
  50.             valid_index(i1, i2 + i4, slots) &&
  51.             valid_index(i1, i2 + i5, slots) &&
  52.             valid_index(i1, i3 + i4, slots) &&
  53.             valid_index(i3, i3 + i5, slots) &&
  54.             valid_index(i1, i4 + i5, slots) &&
  55.             valid_index(i2, i3 + i4, slots) &&
  56.             valid_index(i2, i3 + i5, slots) &&
  57.             valid_index(i2, i4 + i5, slots) &&
  58.             valid_index(i3, i4 + 15, slots) &&
  59.             valid_index(i1, i2 + i3 + i4, slots) &&
  60.             valid_index(i1, i2 + i3 + i5, slots) &&
  61.             valid_index(i1, i2 + i4 + i5, slots) &&
  62.             valid_index(i1, i3 + i4 + i5, slots) &&
  63.             valid_index(i2, i3 + i4 + i5, slots) &&
  64.             valid_index(i1, i2 + i3 + i4 + i5, slots))
  65.         {
  66.             ++valid_count;
  67.             std::cout << "Valid combination: ";
  68.             std::cout << std::setw(10) << (i1 / 16.0);
  69.             std::cout << std::setw(10) << (i2 / 16.0);
  70.             std::cout << std::setw(10) << (i3 / 16.0);
  71.             std::cout << std::setw(10) << (i4 / 16.0);
  72.             std::cout << std::setw(10) << (i5 / 16.0) << "\n";
  73.  
  74.             auto magic = 60ull << 56;
  75.             magic |= static_cast<uint64_t>(i1) << (60 - 53 - 4); // F7
  76.             magic |= static_cast<uint64_t>(i2) << (60 - 44 - 4); // E6
  77.             magic |= static_cast<uint64_t>(i3) << (60 - 35 - 4); // D5
  78.             magic |= static_cast<uint64_t>(i4) << (60 - 26 - 4); // C4
  79.             magic |= static_cast<uint64_t>(i5) << (60 - 17 - 4); // B3
  80.             std::cout << "Magic: " << std::hex << magic << std::dec;
  81.             std::cout << "  " << std::bitset<64>(magic) << "\n\n";
  82.         }
  83.     }
  84.  
  85.     std::cout << valid_count << "/" << count << std::endl;
  86. }
  87.  
  88.  
Success #stdin #stdout 0.55s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Valid combination:      1.125      2.25     4.875     5.125    15.875
Magic: 3c007f1489c24090  0011110000000000011111110001010010001001110000100100000010010000

Valid combination:      1.125      2.25    10.875    11.125    15.875
Magic: 3c007f2c95c24090  0011110000000000011111110010110010010101110000100100000010010000

Valid combination:      1.125     2.375     4.875     5.125    15.875
Magic: 3c007f1489c26090  0011110000000000011111110001010010001001110000100110000010010000

Valid combination:      1.125     2.375    10.875    11.125    15.875
Magic: 3c007f2c95c26090  0011110000000000011111110010110010010101110000100110000010010000

Valid combination:      1.125       2.5     4.875     5.125    15.875
Magic: 3c007f1489c28090  0011110000000000011111110001010010001001110000101000000010010000

Valid combination:      1.125       2.5    10.875    11.125    15.875
Magic: 3c007f2c95c28090  0011110000000000011111110010110010010101110000101000000010010000

Valid combination:      1.125     2.625     4.875     5.125    15.875
Magic: 3c007f1489c2a090  0011110000000000011111110001010010001001110000101010000010010000

Valid combination:      1.125     2.625    10.875    11.125    15.875
Magic: 3c007f2c95c2a090  0011110000000000011111110010110010010101110000101010000010010000

Valid combination:       1.25      2.25     4.875     5.125    15.875
Magic: 3c007f1489c240a0  0011110000000000011111110001010010001001110000100100000010100000

Valid combination:       1.25      2.25    10.875    11.125    15.875
Magic: 3c007f2c95c240a0  0011110000000000011111110010110010010101110000100100000010100000

Valid combination:       1.25     2.375      4.75     5.125    15.875
Magic: 3c007f14898260a0  0011110000000000011111110001010010001001100000100110000010100000

Valid combination:       1.25     2.375      4.75      5.25    15.875
Magic: 3c007f15098260a0  0011110000000000011111110001010100001001100000100110000010100000

Valid combination:       1.25     2.375     4.875     5.125    15.875
Magic: 3c007f1489c260a0  0011110000000000011111110001010010001001110000100110000010100000

Valid combination:       1.25     2.375     10.75    11.125    15.875
Magic: 3c007f2c958260a0  0011110000000000011111110010110010010101100000100110000010100000

Valid combination:       1.25     2.375     10.75     11.25    15.875
Magic: 3c007f2d158260a0  0011110000000000011111110010110100010101100000100110000010100000

Valid combination:       1.25     2.375    10.875    11.125    15.875
Magic: 3c007f2c95c260a0  0011110000000000011111110010110010010101110000100110000010100000

Valid combination:       1.25       2.5      4.75     5.125    15.875
Magic: 3c007f14898280a0  0011110000000000011111110001010010001001100000101000000010100000

Valid combination:       1.25       2.5     4.875     5.125    15.875
Magic: 3c007f1489c280a0  0011110000000000011111110001010010001001110000101000000010100000

Valid combination:       1.25       2.5     10.75    11.125    15.875
Magic: 3c007f2c958280a0  0011110000000000011111110010110010010101100000101000000010100000

Valid combination:       1.25       2.5    10.875    11.125    15.875
Magic: 3c007f2c95c280a0  0011110000000000011111110010110010010101110000101000000010100000

Valid combination:      1.375      2.25     4.875     5.125    15.875
Magic: 3c007f1489c240b0  0011110000000000011111110001010010001001110000100100000010110000

Valid combination:      1.375      2.25    10.875    11.125    15.875
Magic: 3c007f2c95c240b0  0011110000000000011111110010110010010101110000100100000010110000

Valid combination:      1.375     2.375      4.75     5.125    15.875
Magic: 3c007f14898260b0  0011110000000000011111110001010010001001100000100110000010110000

Valid combination:      1.375     2.375     4.875     5.125    15.875
Magic: 3c007f1489c260b0  0011110000000000011111110001010010001001110000100110000010110000

Valid combination:      1.375     2.375     10.75    11.125    15.875
Magic: 3c007f2c958260b0  0011110000000000011111110010110010010101100000100110000010110000

Valid combination:      1.375     2.375    10.875    11.125    15.875
Magic: 3c007f2c95c260b0  0011110000000000011111110010110010010101110000100110000010110000

Valid combination:        1.5      2.25     4.875     5.125    15.875
Magic: 3c007f1489c240c0  0011110000000000011111110001010010001001110000100100000011000000

Valid combination:        1.5      2.25    10.875    11.125    15.875
Magic: 3c007f2c95c240c0  0011110000000000011111110010110010010101110000100100000011000000

Valid combination:        4.5      5.75     6.875     7.125    15.875
Magic: 3c007f1c8dc5c240  0011110000000000011111110001110010001101110001011100001001000000

Valid combination:        4.5      5.75     8.875     9.125    15.875
Magic: 3c007f2491c5c240  0011110000000000011111110010010010010001110001011100001001000000

Valid combination:      4.625     5.625     6.875     7.125    15.875
Magic: 3c007f1c8dc5a250  0011110000000000011111110001110010001101110001011010001001010000

Valid combination:      4.625     5.625     8.875     9.125    15.875
Magic: 3c007f2491c5a250  0011110000000000011111110010010010010001110001011010001001010000

Valid combination:      4.625      5.75      6.75     7.125    15.875
Magic: 3c007f1c8d85c250  0011110000000000011111110001110010001101100001011100001001010000

Valid combination:      4.625      5.75     6.875     7.125    15.875
Magic: 3c007f1c8dc5c250  0011110000000000011111110001110010001101110001011100001001010000

Valid combination:      4.625      5.75      8.75     9.125    15.875
Magic: 3c007f249185c250  0011110000000000011111110010010010010001100001011100001001010000

Valid combination:      4.625      5.75     8.875     9.125    15.875
Magic: 3c007f2491c5c250  0011110000000000011111110010010010010001110001011100001001010000

Valid combination:       4.75       5.5     6.875     7.125    15.875
Magic: 3c007f1c8dc58260  0011110000000000011111110001110010001101110001011000001001100000

Valid combination:       4.75       5.5     8.875     9.125    15.875
Magic: 3c007f2491c58260  0011110000000000011111110010010010010001110001011000001001100000

Valid combination:       4.75     5.625      6.75     7.125    15.875
Magic: 3c007f1c8d85a260  0011110000000000011111110001110010001101100001011010001001100000

Valid combination:       4.75     5.625     6.875     7.125    15.875
Magic: 3c007f1c8dc5a260  0011110000000000011111110001110010001101110001011010001001100000

Valid combination:       4.75     5.625      8.75     9.125    15.875
Magic: 3c007f249185a260  0011110000000000011111110010010010010001100001011010001001100000

Valid combination:       4.75     5.625     8.875     9.125    15.875
Magic: 3c007f2491c5a260  0011110000000000011111110010010010010001110001011010001001100000

Valid combination:       4.75      5.75     6.625     7.125    15.875
Magic: 3c007f1c8d45c260  0011110000000000011111110001110010001101010001011100001001100000

Valid combination:       4.75      5.75      6.75     7.125    15.875
Magic: 3c007f1c8d85c260  0011110000000000011111110001110010001101100001011100001001100000

Valid combination:       4.75      5.75     6.875     7.125    15.875
Magic: 3c007f1c8dc5c260  0011110000000000011111110001110010001101110001011100001001100000

Valid combination:       4.75      5.75     8.625     9.125    15.875
Magic: 3c007f249145c260  0011110000000000011111110010010010010001010001011100001001100000

Valid combination:       4.75      5.75      8.75     9.125    15.875
Magic: 3c007f249185c260  0011110000000000011111110010010010010001100001011100001001100000

Valid combination:       4.75      5.75     8.875     9.125    15.875
Magic: 3c007f2491c5c260  0011110000000000011111110010010010010001110001011100001001100000

48/98402304
https://ideone.com/B9S40Q
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!