qqwref

Sokoban Polyomino checker (128 bit)

May 9th, 2021
654
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Sokoban n-squares search program, now 128 bit
  2.  
  3. // g++ sokoban_polyomino.cpp -o sokoban_polyomino.exe -Wall -O3 --std=c++0x
  4. // sokoban_polyonino.exe < poly_16.txt
  5.  
  6. #include <algorithm>
  7. #include <fstream>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <stdint.h>
  14. #include <string>
  15. #include <time.h>
  16. #include <vector>
  17. #include <windows.h>
  18.  
  19. typedef unsigned char byte;
  20. typedef unsigned __int128 uint128_t;
  21.  
  22. inline int moveAddition(int mov, int HH, int WW) {
  23.     // -16, 16, -1, 1
  24.     if (mov == 0) {
  25.         return -WW;
  26.     } else if (mov == 1) {
  27.         return WW;
  28.     } else if (mov == 2) {
  29.         return -1;
  30.     } else if (mov == 3) {
  31.         return 1;
  32.     } else {
  33.         return 0;
  34.     }
  35. }
  36.  
  37. inline uint128_t findPlayer(uint128_t state) {
  38.     return state & ((uint128_t)127);
  39. }
  40.  
  41. inline uint128_t getPosition(uint128_t state, int position) {
  42.     return state & (((uint128_t)128) << position);
  43. }
  44.  
  45. inline uint128_t setPlayer(uint128_t state, int position) {
  46.     return (state & ~((uint128_t)127)) | ((uint128_t)position);
  47. }
  48.  
  49. inline uint128_t togglePosition(uint128_t state, int position) {
  50.     return state ^ (((uint128_t)128) << position);
  51. }
  52.  
  53. // can we apply this move to this piece?
  54. inline bool isValid(int move, int n, uint128_t shape_position, int HH, int WW) {
  55.     int w = n + moveAddition(move, HH, WW);
  56.     if (w>=0 && w<126 && (shape_position & (((uint128_t)128)<<w))) {
  57.         return false;
  58.     }
  59.     if (move == 0) {
  60.         return (n >= WW);
  61.     } else if (move == 1) {
  62.         return (n < WW*(HH-1));
  63.     } else if (move == 2) {
  64.         return (n%WW != 0);
  65.     } else {
  66.         return (n%WW != WW-1);
  67.     }
  68. }
  69.  
  70. inline void printGrid(uint128_t state, uint128_t shape_position, int HH, int WW) {
  71.     int player = findPlayer(state);
  72.     std::cout << "+";
  73.     for (int j=0; j<WW; j++) std::cout << "-";
  74.     std::cout << "+\n";
  75.     for (int i=0; i<HH; i++) {
  76.         std::cout << "|";
  77.         for (int j=0; j<WW; j++) {
  78.             if (getPosition(shape_position, i*WW+j) > 0) {
  79.                 std::cout << "#";
  80.             } else if (i*WW+j == player) {
  81.                 std::cout << "@";
  82.             } else if (getPosition(state, i*WW+j) > 0) {
  83.                 std::cout << "*";
  84.             } else {
  85.                 std::cout << " ";
  86.             }
  87.         }
  88.         std::cout << "|\n";
  89.     }
  90.     std::cout << "+";
  91.     for (int j=0; j<WW; j++) std::cout << "-";
  92.     std::cout << "+\n";
  93. }
  94.  
  95. uint128_t applyMove(int mov, uint128_t position, uint128_t shape_position, int HH, int WW) {
  96.     int submov = mov&3;
  97.     int player = findPlayer(position);
  98.     int delta = moveAddition(submov, HH, WW);
  99.    
  100.     if (!isValid(submov, player, shape_position, HH, WW)) return 0;
  101.     if (getPosition(position, player+delta) > 0) return 0;
  102.  
  103.     if (mov>3 && (!isValid(submov^1, player, shape_position, HH, WW) || getPosition(position, player-delta) == 0)) return 0;
  104.     uint128_t newPosition = setPlayer(position, player+delta);
  105.     if (mov>3) {
  106.         newPosition = togglePosition(togglePosition(newPosition, player), player-delta);
  107.     }
  108.     return newPosition;
  109. }
  110.  
  111. // solve by enumerating every position with one map per depth
  112. int mapSolve(uint128_t puzzle, uint128_t shape_position, int HH, int WW) {
  113.     // start with empty maps (state -> <depth, movestring>)
  114.     std::set<uint128_t> positions;
  115.     std::set<uint128_t> nextPositions;
  116.     std::set<uint128_t> curPositions;
  117.    
  118.     // get starting positions
  119.     for (int i=0; i<HH*WW; i++) {
  120.         if (getPosition(puzzle, i) > 0) {
  121.             // try placing player around this
  122.             for (int j=0; j<4; j++) {
  123.                 int add = moveAddition(j, HH, WW);
  124.                 if (!isValid(j, i, shape_position, HH, WW)) continue;
  125.                 if (getPosition(puzzle, i+add) == 0) {
  126.                     positions.insert(setPlayer(puzzle, i+add));
  127.                     nextPositions.insert(setPlayer(puzzle, i+add));
  128.                 }
  129.             }
  130.         }
  131.     }
  132.    
  133.     int main_depth = 0;
  134.    
  135.     while (!nextPositions.empty()) {
  136.         // swap maps
  137.         std::swap(curPositions, nextPositions);
  138.         nextPositions.clear();
  139.        
  140.         // iterate over map
  141.         for (std::set<uint128_t>::iterator it=curPositions.begin(); it!=curPositions.end(); ++it) {
  142.             uint128_t position = *it;
  143.            
  144.             // loop through moves
  145.             for (int mov = 0; mov < 8; mov++) {
  146.                 uint128_t newPosition = applyMove(mov, position, shape_position, HH, WW);
  147.                 if (newPosition != 0) {
  148.                     if (positions.count(newPosition) == 0) {
  149.                         positions.insert(newPosition);
  150.                         nextPositions.insert(newPosition);
  151.                     }
  152.                 }
  153.             }
  154.         }
  155.            
  156.         if (nextPositions.empty()) {
  157.             return main_depth;
  158.         }
  159.            
  160.         main_depth++;
  161.     }
  162.     return -1;
  163. }
  164.  
  165. inline uint128_t parse_grid(std::string input) {
  166.     uint128_t shape_position = 0;
  167.     int idx = 0;
  168.     int len = (int) input.length();
  169.     for (int i=0; i<len; i++) {
  170.         if (input[i] == '|') continue;
  171.         if (input[i] == '#') {
  172.             shape_position += (((uint128_t)128) << idx);
  173.         }
  174.         idx++;
  175.     }
  176.     return shape_position;
  177. }
  178.  
  179. int solve() {
  180.     clock_t startTime = clock();
  181.    
  182.     uint128_t overallMaxPosition = 0;
  183.     uint128_t overallMaxShape = 0;
  184.     int overallHH = 0;
  185.     int overallWW = 0;
  186.     int overallMax = 0;
  187.     int HH = 0;
  188.     int WW = 0;
  189.    
  190.     // get and print puzzle
  191.     std::string input;
  192.     int position_number = 0;
  193.     while (getline(std::cin, input)) {
  194.         // get next polyomino
  195.         if (input == "") {
  196.             break;
  197.         }
  198.         int len = input.length();
  199.         HH = std::count(input.begin(), input.end(), '|') + 1;
  200.         if (HH == 1) {
  201.             WW = len;
  202.         } else {
  203.             WW = (int) input.find('|');
  204.         }
  205.         uint128_t shape_position = parse_grid(input);
  206.        
  207.         // find locations of the empty spaces
  208.         std::vector<int> space_locations;
  209.         for (int i=0; i<(HH*WW); i++) {
  210.             if (getPosition(shape_position, i) == 0) {
  211.                 space_locations.push_back(i);
  212.             }
  213.         }
  214.         int space_location_size = space_locations.size();
  215.  
  216.         // loop number of crates
  217.         for (int nCrates=1; nCrates<space_location_size; nCrates++) {
  218.             uint128_t position = (((uint128_t)1) << nCrates) - ((uint128_t)1);
  219.             // generate all possible moves for every position?
  220.             // for each position with this number of crates...
  221.             while (position < (((uint128_t)1) << space_location_size)) {
  222.                 // convert position (a permutation) into a block layout
  223.                 uint128_t curPosition = 0;
  224.                 for (int i=0; i<space_location_size; i++) {
  225.                     if (position & (((uint128_t)1) << i)) {
  226.                         curPosition += (((uint128_t)1) << space_locations[i]);
  227.                     }
  228.                 }
  229.                
  230.                 // get next permutation
  231.                 // https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
  232.                 uint128_t t = (position | (position - 1)) + 1;
  233.                 uint128_t w = t | ((((t & -t) / (position & -position)) >> 1) - 1);
  234.                 position = w;
  235.                
  236.                 // solve
  237.                 int z = mapSolve(curPosition*128, shape_position, HH, WW);
  238.                 // print maximum
  239.                 if (z > overallMax) {
  240.                     overallMax = z;
  241.                     double secs = double(clock() - startTime) / (double)CLOCKS_PER_SEC;
  242.                     std::cout << "Puzzle solved in " << z << " moves (" << secs << ")\n"  << std::flush;
  243.                     overallMaxPosition = curPosition*128+127;
  244.                     overallMaxShape = shape_position;
  245.                     overallHH = HH;
  246.                     overallWW = WW;
  247.                     printGrid(curPosition*128+127, shape_position, HH, WW);
  248.                 }
  249.             }
  250.         }
  251.         if ((position_number % 100) == 0) {
  252.             std::cout << "Done with position " << position_number << "\n";
  253.         }
  254.         position_number++;
  255.     }
  256.    
  257.     // finish
  258.     double secs = double(clock() - startTime) / (double)CLOCKS_PER_SEC;
  259.     std::cout << "Done (" << secs << ")\n" << std::flush;
  260.     std::cout << "Overall max moves was " << overallMax << "\n";
  261.     printGrid(overallMaxPosition, overallMaxShape, overallHH, overallWW);
  262.    
  263.     return EXIT_SUCCESS;
  264. }
  265.  
  266. // g++ sokoban_polyomino.cpp -o sokoban_polyomino.exe -Wall -O3 --std=c++0x
  267. int main(int argc, char *argv[]) {
  268.     solve();
  269. }
RAW Paste Data