qqwref

Sokoban Polyomino checker

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