tomdodd4598

Untitled

Sep 28th, 2021
699
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <atomic>
  3. #include <cstdint>
  4. #include <functional>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <set>
  8. #include <thread>
  9. #include <vector>
  10.  
  11. typedef int_fast8_t i8;
  12. typedef int64_t i64;
  13. typedef uint64_t u64;
  14.  
  15. typedef std::atomic<i64> a_i64;
  16. typedef std::atomic<size_t> a_size;
  17.  
  18. typedef std::set<size_t> hash_set;
  19. typedef std::vector<i8> tape_vec;
  20. typedef std::vector<std::thread> thread_vec;
  21.  
  22. void bb1();
  23. void bb2();
  24. void bb3();
  25. void bb4();
  26.  
  27. int main() {
  28.     int n;
  29.     std::cout << "Card count: ";
  30.     std::cin >> n;
  31.     std::cout << "\n";
  32.  
  33.     if (n < 1) std::cout << "Can not compute busy beaver function for less than 1 card!\n";
  34.     else if (n == 1) bb1();
  35.     else if (n == 2) bb2();
  36.     else if (n == 3) bb3();
  37.     else if (n == 4) bb4();
  38.     else std::cout << "Can not compute busy beaver function for more than 4 cards!\n";
  39.  
  40.     return 0;
  41. }
  42.  
  43. void set_bb_threads(thread_vec& vec, void (*bb_internal)(a_i64*, a_size*), a_i64* perm_count, a_size* score) {
  44.     const int bb_thread_count = std::thread::hardware_concurrency() - 1;
  45.     for (int i = 0; i < bb_thread_count; ++i) {
  46.         vec.push_back(std::thread(bb_internal, perm_count, score));
  47.     }
  48. }
  49.  
  50. void join_bb_threads(thread_vec& vec) {
  51.     std::for_each(vec.begin(), vec.end(), std::mem_fn(&std::thread::join));
  52. }
  53.  
  54. template<typename T>
  55. inline void update_max_atomic(std::atomic<T>* max_value, const T new_value) {
  56.     T prev_value = *max_value;
  57.     while (prev_value < new_value && !max_value->compare_exchange_weak(prev_value, new_value));
  58. }
  59.  
  60. inline i8 to_dir(i64 raw) {
  61.     return (raw > 0l) - (raw <= 0l);
  62. }
  63.  
  64. inline size_t tape_index(i64 pos) {
  65.     const i64 mask = pos >> 63;
  66.     const u64 mag = (pos + mask) ^ mask;
  67.     return static_cast<size_t>((mag << 1) - (pos < 0));
  68. }
  69.  
  70. inline void tape_check(tape_vec& vec, size_t idx) {
  71.     if (idx >= vec.size()) vec.resize(idx << 1, 0);
  72. }
  73.  
  74. inline size_t tape_count(const tape_vec& vec) {
  75.     size_t num = 0;
  76.     for (i8 c : vec) {
  77.         num += (c > 0);
  78.     }
  79.     return num;
  80. }
  81.  
  82. inline size_t bb_hash(const tape_vec& vec, i64 state, i8 in, size_t idx) {
  83.     size_t h = 5381 + vec.size();
  84.     for (i8 c : vec) {
  85.         h = ((h << 5) + h) + c;
  86.     }
  87.     h = ((h << 5) + h) + state;
  88.     h = ((h << 5) + h) + in;
  89.     return ((h << 5) + h) + idx;
  90. }
  91.  
  92. template <typename T>
  93. inline bool contains(const std::set<T> set, T& elem) {
  94.     return set.find(elem) != set.end();
  95. }
  96.  
  97. void bb1() {
  98.     constexpr size_t VECLIMIT = 4;
  99.     constexpr size_t SETLIMIT = 16;
  100.  
  101.     size_t score = 0;
  102.  
  103.     i64 perm = -1;
  104.     i64 card[1][2][3];
  105.  
  106.     while (++perm < 64) {
  107.         i64 valid = 0;
  108.         i64 state;
  109.         i64 c0 = perm / 8;
  110.         i64 c1 = perm % 8;
  111.  
  112.         card[0][0][0] = c0 & 1;
  113.         card[0][0][1] = to_dir(c0 & 2);
  114.         card[0][0][2] = state = c0 >> 2;
  115.         valid += (state < 1);
  116.  
  117.         card[0][1][0] = c1 & 1;
  118.         card[0][1][1] = to_dir(c1 & 2);
  119.         card[0][1][2] = state = c1 >> 2;
  120.         valid += (state < 1);
  121.  
  122.         if (!valid) continue;
  123.  
  124.         auto vec = tape_vec(1, 0);
  125.         auto hashes = hash_set();
  126.  
  127.         state = 0;
  128.         i8 in = 0;
  129.         i64 pos = 0;
  130.         size_t hash, idx = 0;
  131.  
  132.         do {
  133.             if (vec.size() > VECLIMIT || hashes.size() > SETLIMIT || contains(hashes, hash = bb_hash(vec, state, in, idx))) {
  134.                 state = -1;
  135.                 break;
  136.             }
  137.             else hashes.insert(hash);
  138.             idx = tape_index(pos);
  139.             tape_check(vec, idx);
  140.             in = vec[idx];
  141.             vec[idx] = static_cast<i8>(card[state][in][0]);
  142.             pos += card[state][in][1];
  143.             state = card[state][in][2];
  144.         }
  145.         while (state < 1);
  146.  
  147.         if (state > 0) score = std::max(score, tape_count(vec));
  148.     }
  149.  
  150.     std::cout << "Score: " << score << "\n";
  151. }
  152.  
  153. void bb2() {
  154.     constexpr size_t VECLIMIT = 8;
  155.     constexpr size_t SETLIMIT = 32;
  156.  
  157.     size_t score = 0;
  158.  
  159.     i64 perm = -1;
  160.     i64 card[2][2][3];
  161.  
  162.     while (++perm < 20736) {
  163.         i64 valid = 0;
  164.         i64 state;
  165.         i64 c0 = perm / 1728;
  166.         i64 c1 = (perm / 144) % 12;
  167.         i64 c2 = (perm / 12) % 12;
  168.         i64 c3 = perm % 12;
  169.  
  170.         card[0][0][0] = c0 & 1;
  171.         card[0][0][1] = to_dir(c0 & 2);
  172.         card[0][0][2] = state = c0 >> 2;
  173.         valid += (state < 2);
  174.  
  175.         card[0][1][0] = c1 & 1;
  176.         card[0][1][1] = to_dir(c1 & 2);
  177.         card[0][1][2] = state = c1 >> 2;
  178.         valid += (state < 2);
  179.  
  180.         card[1][0][0] = c2 & 1;
  181.         card[1][0][1] = to_dir(c2 & 2);
  182.         card[1][0][2] = state = c2 >> 2;
  183.         valid += (state < 2);
  184.  
  185.         card[1][1][0] = c3 & 1;
  186.         card[1][1][1] = to_dir(c3 & 2);
  187.         card[1][1][2] = state = c3 >> 2;
  188.         valid += (state < 2);
  189.  
  190.         if (!valid) continue;
  191.  
  192.         auto vec = tape_vec(1, 0);
  193.         auto hashes = hash_set();
  194.  
  195.         state = 0;
  196.         i8 in = 0;
  197.         i64 pos = 0;
  198.         size_t hash, idx = 0;
  199.  
  200.         do {
  201.             if (vec.size() > VECLIMIT || hashes.size() > SETLIMIT || contains(hashes, hash = bb_hash(vec, state, in, idx))) {
  202.                 state = -1;
  203.                 break;
  204.             }
  205.             else hashes.insert(hash);
  206.             idx = tape_index(pos);
  207.             tape_check(vec, idx);
  208.             in = vec[idx];
  209.             vec[idx] = static_cast<i8>(card[state][in][0]);
  210.             pos += card[state][in][1];
  211.             state = card[state][in][2];
  212.         }
  213.         while (state < 2);
  214.  
  215.         if (state > 0) score = std::max(score, tape_count(vec));
  216.     }
  217.  
  218.     std::cout << "Score: " << score << "\n";
  219. }
  220.  
  221. constexpr i64 BB3_PERMCOUNT = 16777216;
  222.  
  223. void bb3_internal(a_i64* perm_count, a_size* score) {
  224.     constexpr size_t VECLIMIT = 12;
  225.     constexpr size_t SETLIMIT = 64;
  226.  
  227.     i64 perm;
  228.     i64 card[3][2][3];
  229.  
  230.     while ((perm = ++*perm_count) < BB3_PERMCOUNT) {
  231.         i64 valid = 0;
  232.         i64 state;
  233.         i64 c0 = perm / 1048576;
  234.         i64 c1 = (perm / 65536) % 16;
  235.         i64 c2 = (perm / 4096) % 16;
  236.         i64 c3 = (perm / 256) % 16;
  237.         i64 c4 = (perm / 16) % 16;
  238.         i64 c5 = perm % 16;
  239.  
  240.         card[0][0][0] = c0 & 1;
  241.         card[0][0][1] = to_dir(c0 & 2);
  242.         card[0][0][2] = state = c0 >> 2;
  243.         valid += (state < 3);
  244.  
  245.         card[0][1][0] = c1 & 1;
  246.         card[0][1][1] = to_dir(c1 & 2);
  247.         card[0][1][2] = state = c1 >> 2;
  248.         valid += (state < 3);
  249.  
  250.         card[1][0][0] = c2 & 1;
  251.         card[1][0][1] = to_dir(c2 & 2);
  252.         card[1][0][2] = state = c2 >> 2;
  253.         valid += (state < 3);
  254.  
  255.         card[1][1][0] = c3 & 1;
  256.         card[1][1][1] = to_dir(c3 & 2);
  257.         card[1][1][2] = state = c3 >> 2;
  258.         valid += (state < 3);
  259.  
  260.         card[2][0][0] = c4 & 1;
  261.         card[2][0][1] = to_dir(c4 & 2);
  262.         card[2][0][2] = state = c4 >> 2;
  263.         valid += (state < 3);
  264.  
  265.         card[2][1][0] = c5 & 1;
  266.         card[2][1][1] = to_dir(c5 & 2);
  267.         card[2][1][2] = state = c5 >> 2;
  268.         valid += (state < 3);
  269.  
  270.         if (!valid) continue;
  271.  
  272.         auto vec = tape_vec(1, 0);
  273.         auto hashes = hash_set();
  274.  
  275.         state = 0;
  276.         i8 in = 0;
  277.         i64 pos = 0;
  278.         size_t hash, idx = 0;
  279.  
  280.         do {
  281.             if (vec.size() > VECLIMIT || hashes.size() > SETLIMIT || contains(hashes, hash = bb_hash(vec, state, in, idx))) {
  282.                 state = -1;
  283.                 break;
  284.             }
  285.             else hashes.insert(hash);
  286.             idx = tape_index(pos);
  287.             tape_check(vec, idx);
  288.             in = vec[idx];
  289.             vec[idx] = static_cast<i8>(card[state][in][0]);
  290.             pos += card[state][in][1];
  291.             state = card[state][in][2];
  292.         }
  293.         while (state < 3);
  294.  
  295.         if (state > 0) {
  296.             update_max_atomic(score, tape_count(vec));
  297.         }
  298.     }
  299. }
  300.  
  301. void bb3() {
  302.     std::cout << "This may take some time...\n0%";
  303.  
  304.     a_i64 perm_count = 0;
  305.     a_size score = 0;
  306.     bool finished = false;
  307.  
  308.     std::thread progress_daemon([&perm_count, &finished] {
  309.         int progress = 0;
  310.         while (!finished) {
  311.             const int new_progress = static_cast<int>(100.0 * perm_count / BB3_PERMCOUNT);
  312.             if (new_progress > progress) std::cout << "\r" << new_progress << "%";
  313.             progress = new_progress;
  314.         }
  315.     });
  316.  
  317.     auto vec = thread_vec();
  318.     set_bb_threads(vec, &bb3_internal, &perm_count, &score);
  319.  
  320.     join_bb_threads(vec);
  321.     finished = true;
  322.     progress_daemon.join();
  323.  
  324.     std::cout << "\r100%\n\nScore: " << score << "\n";
  325. }
  326.  
  327. constexpr i64 BB4_PERMCOUNT = 25600000000;
  328.  
  329. void bb4_internal(a_i64* perm_count, a_size* score) {
  330.     constexpr size_t VECLIMIT = 24;
  331.     constexpr size_t SETLIMIT = 128;
  332.  
  333.     i64 perm;
  334.     i64 card[4][2][3];
  335.  
  336.     while ((perm = ++*perm_count) < BB4_PERMCOUNT) {
  337.         i64 valid = 0;
  338.         i64 state;
  339.         i64 c0 = perm / 1280000000;
  340.         i64 c1 = (perm / 64000000) % 20;
  341.         i64 c2 = (perm / 3200000) % 20;
  342.         i64 c3 = (perm / 160000) % 20;
  343.         i64 c4 = (perm / 8000) % 20;
  344.         i64 c5 = (perm / 400) % 20;
  345.         i64 c6 = (perm / 20) % 20;
  346.         i64 c7 = perm % 20;
  347.  
  348.         card[0][0][0] = c0 & 1;
  349.         card[0][0][1] = to_dir(c0 & 2);
  350.         card[0][0][2] = state = c0 >> 2;
  351.         valid += (state < 4);
  352.  
  353.         card[0][1][0] = c1 & 1;
  354.         card[0][1][1] = to_dir(c1 & 2);
  355.         card[0][1][2] = state = c1 >> 2;
  356.         valid += (state < 4);
  357.  
  358.         card[1][0][0] = c2 & 1;
  359.         card[1][0][1] = to_dir(c2 & 2);
  360.         card[1][0][2] = state = c2 >> 2;
  361.         valid += (state < 4);
  362.  
  363.         card[1][1][0] = c3 & 1;
  364.         card[1][1][1] = to_dir(c3 & 2);
  365.         card[1][1][2] = state = c3 >> 2;
  366.         valid += (state < 4);
  367.  
  368.         card[2][0][0] = c4 & 1;
  369.         card[2][0][1] = to_dir(c4 & 2);
  370.         card[2][0][2] = state = c4 >> 2;
  371.         valid += (state < 4);
  372.  
  373.         card[2][1][0] = c5 & 1;
  374.         card[2][1][1] = to_dir(c5 & 2);
  375.         card[2][1][2] = state = c5 >> 2;
  376.         valid += (state < 4);
  377.  
  378.         card[3][0][0] = c6 & 1;
  379.         card[3][0][1] = to_dir(c6 & 2);
  380.         card[3][0][2] = state = c6 >> 2;
  381.         valid += (state < 4);
  382.  
  383.         card[3][1][0] = c7 & 1;
  384.         card[3][1][1] = to_dir(c7 & 2);
  385.         card[3][1][2] = state = c7 >> 2;
  386.         valid += (state < 4);
  387.  
  388.         if (!valid) continue;
  389.  
  390.         auto vec = tape_vec(1, 0);
  391.         auto hashes = hash_set();
  392.  
  393.         state = 0;
  394.         i8 in = 0;
  395.         i64 pos = 0;
  396.         size_t hash, idx = 0;
  397.  
  398.         do {
  399.             if (vec.size() > VECLIMIT || hashes.size() > SETLIMIT || contains(hashes, hash = bb_hash(vec, state, in, idx))) {
  400.                 state = -1;
  401.                 break;
  402.             }
  403.             else hashes.insert(hash);
  404.             idx = tape_index(pos);
  405.             tape_check(vec, idx);
  406.             in = vec[idx];
  407.             vec[idx] = static_cast<i8>(card[state][in][0]);
  408.             pos += card[state][in][1];
  409.             state = card[state][in][2];
  410.         }       while (state < 4);
  411.  
  412.         if (state > 0) {
  413.             update_max_atomic(score, tape_count(vec));
  414.         }
  415.     }
  416. }
  417.  
  418. void bb4() {
  419.     std::cout << "This may take a very, very long time...\n0.00%";
  420.     std::cout << std::fixed << std::setprecision(2);
  421.  
  422.     a_i64 perm_count = 0;
  423.     a_size score = 0;
  424.     bool finished = false;
  425.  
  426.     std::thread progress_daemon([&perm_count, &finished] {
  427.         int progress = 0;
  428.         while (!finished) {
  429.             double percent = 100.0 * perm_count / BB4_PERMCOUNT;
  430.             int new_progress = static_cast<int>(100.0 * percent);
  431.             if (new_progress > progress) std::cout << "\r" << percent << "%";
  432.             progress = new_progress;
  433.         }
  434.     });
  435.  
  436.     auto vec = thread_vec();
  437.     set_bb_threads(vec, &bb4_internal, &perm_count, &score);
  438.  
  439.     join_bb_threads(vec);
  440.     finished = true;
  441.     progress_daemon.join();
  442.  
  443.     std::cout << "\r100.00%\n\nScore: " << score << "\n";
  444. }
  445.  
RAW Paste Data