API tools faq
paste
Advertisement
qqwref

Denki Blocks solver (updated)

qqwref
Sep 29th, 2015 (edited)
43
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 38.52 KB | None | 0 0
raw download clone embed print report diff
  1. /*
  2.  (Sub)Optimal Denki Blocks solver
  3.  Copyright (C) 2014-5 Michael Gottlieb
  4. */
  5.  
  6.  
  7. // do we care about pairs / 3-of-a-kinds?
  8. #define USING_PAIRS 1      // needs to be 1 if anything in this group is
  9. #define NO_PAIRS 0         // forbid any pairs
  10. #define NO_THREE_KIND 0    // pairs are OK, but forbid 3-of-a-kinds
  11. #define THREE_KIND_ONLY 1  // allow 3-of-a-kind only
  12.  
  13. // should we minimize matches?
  14. #define MINIMIZE_MATCHES 0  // needs to be 1 if anything in this group is
  15. #define ONE_MATCH 0         // forbid unsolved states with some but not all colors paired
  16. #define TWO_MATCHES_ONE 0   // forbid all states with exactly one color paired
  17. #define TWO_MATCHES_TWO 0   // forbid all states with exactly two colors paired
  18.  
  19. // use alternate heuristic for suboptimal solves?
  20. #define ALTERNATE_HEURISTIC 1
  21.  
  22. // make sure we can make a shape?
  23. #define USING_SHAPE 0           // needs to be 1 if anything in this group is
  24. #define COLOR_TEST < '5'        // test to see if we care about this color
  25.                                 // e.g. "== '2'" for bonus shape, "< '5'" for 3 of a kind
  26. #define GOAL_SHAPE {0,1,2,5,6,7,16,18,19,20,21,23,24,25,32,33,34,36,37,38,39,41,50,51,52,55,56,57}
  27.                                 // goal shape
  28.                                
  29. // for use when looking for a partial solution (set to 0 when not in use)
  30. #define GOAL_GROUP_NUM 0
  31.  
  32. // Main struct and control flow of program, with all includes used in it
  33.  
  34. #include <algorithm>
  35. #include <fstream>
  36. #include <iostream>
  37. #include <list>
  38. #include <map>
  39. #include <queue>
  40. #include <string>
  41. #include <time.h>
  42. #include <vector>
  43. #include <windows.h>
  44.  
  45. typedef unsigned char byte;
  46.  
  47. struct Groups {
  48.     std::vector<std::vector<int> > pieceGroups;
  49.     std::map<int, int> inversePieceGroups;
  50. };
  51.  
  52. struct Moves {
  53.     int nMoves;
  54.     std::vector<byte> moves;
  55. };
  56.  
  57. struct Queued {
  58.     int minDist;
  59.     std::vector<byte> key;
  60.    
  61.     bool operator< (const Queued other) const {
  62.         return (minDist < other.minDist);
  63.     }
  64. };
  65.  
  66. // http://timday.bitbucket.org/lru.html
  67. class LruCache
  68. {
  69. public:
  70.   typedef std::map<std::string, std::list<std::string>::iterator> key_lookup;
  71.  
  72.   LruCache(size_t c): _capacity(c) {
  73.   }
  74.  
  75.   // is k in cache?
  76.   bool contains(const std::string& k) {
  77.     return (lookup.find(k) != lookup.end());
  78.   }
  79.  
  80.   // Obtain value of the cached function for k
  81.   bool operator()(const std::string& k) {
  82.     const typename key_lookup::iterator it = lookup.find(k);
  83.     if (it==lookup.end()) {
  84.       insert(k);
  85.       return false;
  86.     } else {  
  87.       keys.splice(keys.end(), keys, (*it).second);
  88.       return true;
  89.     }
  90.   }
  91.  
  92.   // Record a fresh key in the cache
  93.   void insert(const std::string& k) {
  94.     if (lookup.size()==_capacity)
  95.       evict();
  96.     std::list<std::string>::iterator it = keys.insert(keys.end(),k);
  97.     lookup.insert(std::make_pair(k, it));
  98.   }
  99.  
  100. private:  
  101.   // Purge the least-recently-used element in the cache
  102.   void evict() {
  103.     const typename key_lookup::iterator it = lookup.find(keys.front());
  104.     lookup.erase(it);
  105.     keys.pop_front();
  106.   }  
  107.  
  108.   const size_t _capacity; // Maximum number of key-value pairs to be retained
  109.   std::list<std::string> keys; // Key access history
  110.   key_lookup lookup; // Key lookup
  111. };
  112.  
  113. struct DenkiSolver {
  114.     static void printGrid(std::string state) {
  115.         std::cout << "+----------------+\n";
  116.         for (int i=0; i<16; i++) {
  117.             std::cout << "|";
  118.             for (int j=0; j<16; j++) {
  119.                 if (state[i*16+j] == '0') {
  120.                     std::cout << ' ';
  121.                 } else {
  122.                     std::cout << state[i*16+j];
  123.                 }
  124.             }
  125.             std::cout << "|\n";
  126.         }
  127.         std::cout << "+----------------+\n";
  128.     }
  129.    
  130.     // moves: 0=U 1=D 2=L 3=R
  131.     // print compressed moves
  132.     static std::string printMoves(std::vector<byte> moves, int moveCount) {
  133.         std::string moveList;
  134.         std::string moveName = "UDLR";
  135.         int i;
  136.         for (i=0; i<(moveCount/4); i++) {
  137.             int x = (int) moves[i];
  138.             moveList += moveName[(x & 192) >> 6];
  139.             moveList += moveName[(x & 48) >> 4];
  140.             moveList += moveName[(x & 12) >> 2];
  141.             moveList += moveName[(x & 3)];
  142.         }
  143.         int x = moves[i];
  144.         if (moveCount % 4 > 2) moveList += moveName[(x & 48) >> 4];
  145.         if (moveCount % 4 > 1) moveList += moveName[(x & 12) >> 2];
  146.         if (moveCount % 4 > 0) moveList += moveName[x & 3];
  147.         return moveList;
  148.     }
  149.    
  150.     // add a move to an existing series of moves
  151.     static std::vector<byte> addMove(std::vector<byte> moves, int mov, int moveCount) {
  152.         std::vector<byte> newMoves = moves;
  153.         if (moveCount % 4 == 0) { // add a new move byte
  154.             newMoves.push_back(mov);
  155.             newMoves.shrink_to_fit();
  156.         } else { // add moves to the last byte
  157.             newMoves[newMoves.size() - 1] = 4*newMoves[newMoves.size() - 1] + mov;
  158.         }
  159.         return newMoves;
  160.     }
  161.    
  162.     // can we apply this move to this piece?
  163.     static bool isValid(int move, int n) {
  164.         if (move == 0) {
  165.             return (n >= 16);
  166.         } else if (move == 1) {
  167.             return (n <= 239);
  168.         } else if (move == 2) {
  169.             return (n%16 != 0);
  170.         } else {
  171.             return (n%16 != 15);
  172.         }
  173.     }
  174.    
  175.     // encode a string (to take up less space)
  176.     static std::vector<byte> encode(std::string input) {
  177.         std::vector<byte> output;
  178.         int nEmpty = 0;
  179.         for (int i=0; i<256; i++) {
  180.             if (input[i] == '0' || input[i] == '1') {
  181.                 nEmpty++;
  182.             } else {
  183.                 while (nEmpty >= 64) {
  184.                     output.push_back('9' + 64);
  185.                     nEmpty -= 64;
  186.                 }
  187.                 if (nEmpty > 0) {
  188.                     output.push_back('9' + nEmpty);
  189.                 }
  190.                 nEmpty = 0;
  191.                 output.push_back(input[i]);
  192.             }
  193.         }
  194.         output.shrink_to_fit();
  195.         return output;
  196.     }
  197.    
  198.     // decode a string
  199.     static std::string decode(std::vector<byte> input, std::string walls) {
  200.         std::string output = "";
  201.         int cnt = 0;
  202.         for (int i=0; i<(int)input.size(); i++) {
  203.             if (input[i] <= '9') {
  204.                 output += input[i];
  205.                 cnt++;
  206.             } else {
  207.                 for (int j=0; j<(int) (input[i] - '9'); j++) {
  208.                     output += walls[cnt];
  209.                     cnt++;
  210.                 }
  211.             }
  212.         }
  213.         while (cnt < 256) {
  214.             output += walls[cnt];
  215.             cnt++;
  216.         }
  217.         return output;
  218.     }
  219.    
  220.     // get pieceGroups and inversePieceGroups
  221.     static Groups getGroups(std::string position) {
  222.         Groups groups;
  223.        
  224.         // initialize visited array
  225.         std::vector<int> visited (256, 0);
  226.         for (int i=0; i<256; i++) {
  227.             if (position[i] <= '1') {
  228.                 visited[i] = 1;
  229.             }
  230.         }
  231.        
  232.         // look for piece groups
  233.         int groupCount = 0;
  234.         for (int i=0; i<256; i++) {
  235.             if (visited[i] == 1) continue;
  236.             std::vector<int> group;
  237.             int groupI = 0;
  238.             char correct = position[i];
  239.             group.push_back(i);
  240.             visited[i] = 1;
  241.             groups.inversePieceGroups[i] = groupCount;
  242.             while (groupI < (int) group.size()) {
  243.                 int x = group[groupI];
  244.                 for (int mov=0; mov<4; mov++) {
  245.                     if (isValid(mov, x)) {
  246.                         int add = moveAddition(mov);
  247.                         if (visited[x+add]==0 && position[x+add]==correct) {
  248.                             group.push_back(x+add);
  249.                             visited[x+add] = 1;
  250.                             groups.inversePieceGroups[x+add] = groupCount;
  251.                         }
  252.                     }
  253.                 }
  254.                 groupI++;
  255.             }
  256. #if USING_PAIRS == 1 || USING_SHAPE == 1
  257.             std::sort(group.begin(), group.end());
  258. #endif 
  259.             groups.pieceGroups.push_back(group);
  260.             groupCount++;
  261.         }
  262.        
  263.         return groups;
  264.     }
  265.    
  266.     // determine which piece groups can move
  267.     static std::vector<int> whatCanMove(int move, Groups groups, std::string position) {
  268.         // 0 = not processed
  269.         // 1 = can move
  270.         // 2 = can't move
  271.         // 3 = in use, not analyzed
  272.         // 4 = in use, analyzed
  273.    
  274.         int add = moveAddition(move);
  275.         std::vector<std::vector<int> > *pieceGroups = &groups.pieceGroups;
  276.         int groupCount = (int) pieceGroups->size();
  277.         std::map<int, int> *inversePieceGroups = &groups.inversePieceGroups;
  278.                                        
  279.         std::vector<int> canMove (groupCount, 0);
  280.         for (int i=0; i<groupCount; i++) {
  281.             if (canMove[i] > 0) continue;
  282.             canMove[i] = 3; // in use, not analyzed
  283.             int curGroup = i;
  284.             while (curGroup != -1) {
  285.                 // check the position above each piece in the group
  286.                 std::vector<int> *thisGroup = &((*pieceGroups)[curGroup]);
  287.                 for (int j=0; j<(int) thisGroup->size(); j++) {
  288.                     // if at the edge, no good
  289.                     if (!isValid(move, (*thisGroup)[j])) {
  290.                         canMove[i] = 2;
  291.                         break;
  292.                     }
  293.                     char pieceForward = position[(*thisGroup)[j] + add];
  294.                     // if there's a wall in the way, no good
  295.                     if (pieceForward == '1') {
  296.                         canMove[i] = 2;
  297.                         break;
  298.                     }
  299.                     // if there's another piece in the way...
  300.                     if (pieceForward > '1') {
  301.                         int groupForward = (*inversePieceGroups)[(*thisGroup)[j] + add];
  302.                         // if that other group can't move, neither can we
  303.                         if (canMove[groupForward] == 2) {
  304.                             canMove[i] = 2;
  305.                             break;
  306.                         }
  307.                         // if that other group isn't processed, work on it
  308.                         if (canMove[groupForward] == 0) {
  309.                             canMove[groupForward] = 3;
  310.                         }
  311.                     }
  312.                 }
  313.                
  314.                 if (canMove[i] == 2) break;
  315.                
  316.                 // done with this group
  317.                 canMove[curGroup] = 4;
  318.                    
  319.                 // get another working group
  320.                 curGroup = -1;
  321.                 for (int j=0; j<groupCount; j++) {
  322.                     if (canMove[j] == 3) {
  323.                         curGroup = j;
  324.                     }
  325.                 }
  326.             }
  327.            
  328.             // so could we move this group?
  329.             if (canMove[i] == 2) { // no
  330.                 for (int j=0; j<groupCount; j++) {
  331.                     if (canMove[j] > 2) {
  332.                         canMove[j] = 0;
  333.                     }
  334.                 }
  335.             } else { // yes - all intermediate groups can be moved too
  336.                 for (int j=0; j<groupCount; j++) {
  337.                     if (canMove[j] > 2) {
  338.                         canMove[j] = 1;
  339.                     }
  340.                 }
  341.             }
  342.         }
  343.    
  344.         return canMove;
  345.     }
  346.    
  347.     static std::string applyMove(int mov, Groups groups, std::string position) {
  348.         // determine what can move
  349.         std::vector<int> canMove = whatCanMove(mov, groups, position);
  350.            
  351.         // move 'em
  352.         std::string newPosition = position;
  353.         std::map<int, int> *inversePieceGroups = &groups.inversePieceGroups;
  354.         if (mov == 0) { // up
  355.             for (int y=0; y<15; y++) {
  356.                 for (int x=0; x<16; x++) {
  357.                     if (position[y*16 + x + 16] > '1') {
  358.                         if (canMove[(*inversePieceGroups)[y*16 + x + 16]] == 1) {
  359.                             newPosition[y*16 + x] = newPosition[y*16 + x + 16];
  360.                             newPosition[y*16 + x + 16] = '0';
  361.                         }
  362.                     }
  363.                 }
  364.             }
  365.         } else if (mov == 1) { // down
  366.             for (int y=15; y>0; y--) {
  367.                 for (int x=0; x<16; x++) {
  368.                     if (position[y*16 + x - 16] > '1') {
  369.                         if (canMove[(*inversePieceGroups)[y*16 + x - 16]] == 1) {
  370.                             newPosition[y*16 + x] = newPosition[y*16 + x - 16];
  371.                             newPosition[y*16 + x - 16] = '0';
  372.                         }
  373.                     }
  374.                 }
  375.             }
  376.         } else if (mov == 2) { // left
  377.             for (int y=0; y<16; y++) {
  378.                 for (int x=0; x<15; x++) {
  379.                     if (position[y*16 + x + 1] > '1') {
  380.                         if (canMove[(*inversePieceGroups)[y*16 + x + 1]] == 1) {
  381.                             newPosition[y*16 + x] = newPosition[y*16 + x + 1];
  382.                             newPosition[y*16 + x + 1] = '0';
  383.                         }
  384.                     }
  385.                 }
  386.             }
  387.         } else { // right
  388.             for (int y=0; y<16; y++) {
  389.                 for (int x=15; x>0; x--) {
  390.                     if (position[y*16 + x - 1] > '1') {
  391.                         if (canMove[(*inversePieceGroups)[y*16 + x - 1]] == 1) {
  392.                             newPosition[y*16 + x] = newPosition[y*16 + x - 1];
  393.                             newPosition[y*16 + x - 1] = '0';
  394.                         }
  395.                     }
  396.                 }
  397.             }
  398.         }
  399.         return newPosition;
  400.     }
  401.    
  402.     // check if solved
  403.     static int isSolved(std::string position, std::vector<std::vector<int> > pieceGroups) {
  404. #if GOAL_GROUP_NUM > 0
  405.         // for partial solutions
  406.         if (pieceGroups.size() <= GOAL_GROUP_NUM) {
  407.             return 1;
  408.         } else {
  409.             return 0;
  410.         }
  411. #endif
  412.        
  413.         int group2=0, group3=0, group4=0; // how many of each of the 3 matching colors
  414.         for (int i=0; i<(int) pieceGroups.size(); i++) {
  415.             char correct = position[pieceGroups[i][0]];
  416.             if (correct == '2') {
  417.                 group2++;
  418.             } else if (correct == '3') {
  419.                 group3++;
  420.             } else if (correct == '4') {
  421.                 group4++;
  422.             }
  423.         }
  424.            
  425.         if (group2<2 && group3<2 && group4<2) {
  426. #if USING_PAIRS == 1
  427.             // OK, it's solved. but do we have a pair?
  428.             int only2=-1, only3=-1, only4=-1;
  429.             for (int i=0; i<(int) pieceGroups.size(); i++) {
  430.                 char correct = position[pieceGroups[i][0]];
  431.                 if (correct == '2') {
  432.                     only2 = i;
  433.                 } else if (correct == '3') {
  434.                     only3 = i;
  435.                 } else if (correct == '4') {
  436.                     only4 = i;
  437.                 }
  438.             }
  439. #if NO_PAIRS == 1
  440.             if (only2 > -1 && only3 > -1 && sameShape(pieceGroups[only2], pieceGroups[only3]) == 1)
  441.                 return -1;
  442.             if (only2 > -1 && only4 > -1 && sameShape(pieceGroups[only2], pieceGroups[only4]) == 1)
  443.                 return -1;
  444.             if (only3 > -1 && only4 > -1 && sameShape(pieceGroups[only3], pieceGroups[only4]) == 1)
  445.                 return -1;
  446.             return 1;
  447. #endif
  448. #if NO_THREE_KIND == 1
  449.             if (only2 > -1 && only3 > -1 && sameShape(pieceGroups[only2], pieceGroups[only3]) != 1)
  450.                 return 1;
  451.             if (only2 > -1 && only4 > -1 && sameShape(pieceGroups[only2], pieceGroups[only4]) != 1)
  452.                 return 1;
  453.             if (only3 > -1 && only4 > -1 && sameShape(pieceGroups[only3], pieceGroups[only4]) != 1)
  454.                 return 1;
  455.             return -1;
  456. #endif
  457. #if THREE_KIND_ONLY == 1
  458.             if (only2 > -1 && only3 > -1 && sameShape(pieceGroups[only2], pieceGroups[only3]) != 1)
  459.                 return -1;
  460.             if (only2 > -1 && only4 > -1 && sameShape(pieceGroups[only2], pieceGroups[only4]) != 1)
  461.                 return -1;
  462.             if (only3 > -1 && only4 > -1 && sameShape(pieceGroups[only3], pieceGroups[only4]) != 1)
  463.                 return -1;
  464.             return 1;
  465. #endif
  466. #endif
  467.             return 1;
  468. #if ONE_MATCH == 1
  469.         } else if ((group2>1 || group3>1 || group4>1) && (group2==1 || group3==1 || group4==1)) {
  470.             return -1;
  471. #endif
  472. #if TWO_MATCHES_ONE == 1
  473.         // don't allow exactly 1 thing matched
  474.         } else if ((group2==1 && group3!=1 && group4!=1) || (group2!=1 && group3==1 && group4!=1) || (group2!=1 && group3!=1 && group4==1)) {
  475.             return -1;
  476. #endif
  477. #if TWO_MATCHES_TWO == 1
  478.         // don't allow exactly 2 things matched
  479.         } else if ((group2==1 && group3==1 && group4!=1) || (group2==1 && group3!=1 && group4==1) || (group2!=1 && group3==1 && group4==1)) {
  480.             return -1;
  481. #endif
  482.         } else {
  483.             return 0;
  484.         }
  485.     }
  486.    
  487.     // do these two groups have the same shape?
  488.     // the two groups should be sorted
  489.     static int sameShape(std::vector<int> group1, std::vector<int> group2) {
  490.         if (group1.size() != group2.size()) {
  491.             return 0;
  492.         }
  493.         int dx = (group2[0]%16) - (group1[0]%16);
  494.         int dy = (group2[0]/16) - (group1[0]/16);
  495.         for (int i=1; i<(int) group1.size(); i++) {
  496.             if ((group2[i]%16) - (group1[i]%16) != dx)
  497.                 return 0;
  498.             if ((group2[i]/16) - (group1[i]/16) != dy)
  499.                 return 0;
  500.         }
  501.         return 1;
  502.     }
  503.    
  504.     static int moveAddition(int mov) {
  505.         // -16, 16, -1, 1
  506.         if (mov == 0) {
  507.             return -16;
  508.         } else if (mov == 1) {
  509.             return 16;
  510.         } else if (mov == 2) {
  511.             return -1;
  512.         } else if (mov == 3) {
  513.             return 1;
  514.         } else {
  515.             return 0;
  516.         }
  517.     }
  518.    
  519.     static int inTaboo(std::string position, std::vector<std::string> taboo) {
  520.         int inTaboo = 0;
  521.         for (int i=0; i<(int) taboo.size(); i++) {
  522.             if (taboo[i] == position) {
  523.                 inTaboo = 1;
  524.                 break;
  525.             }
  526.         }
  527.         return inTaboo;
  528.     }
  529.    
  530.     // get distances between every pair of positions
  531.     // allowed moves:
  532.     // - move one piece in a direction
  533.     // - move both pieces in same direction
  534.     static std::vector<int> getManhattanDistances(std::string walls) {
  535.         // walls are '0's and '1's
  536.         std::vector<int> distances (256*256, -1);
  537.        
  538.         for (int i=0; i<256; i++) {
  539.             if (walls[i] == '0')
  540.                 distances[i*257] = 0;
  541.         }
  542.        
  543.         int depth = 0;
  544.         int foundPositions = 1;
  545.         // loop by depth
  546.         while (foundPositions > 0) {
  547.             foundPositions = 0;
  548.             // find point pairs of this depth
  549.             for (int i=0; i<256; i++) {
  550.                 for (int j=0; j<256; j++) {
  551.                     int index = i*256+j;
  552.                     if (distances[index] == depth) {
  553.                         foundPositions++;
  554.                        
  555.                         // what pairs of points are at depth+1?
  556.                         for (int mov=0; mov<4; mov++) {
  557.                             if (isValid(mov,i) && walls[i+moveAddition(mov)] == '0' && distances[index + moveAddition(mov)*256] == -1) { // move i only
  558.                                 distances[index + moveAddition(mov)*256] = depth+1;
  559.                             }
  560.                             if (isValid(mov,j) && walls[j+moveAddition(mov)] == '0' && distances[index + moveAddition(mov)] == -1) { // move j only
  561.                                 distances[index + moveAddition(mov)] = depth+1;
  562.                             }
  563.                             if (isValid(mov,i) && isValid(mov,j) && walls[i+moveAddition(mov)] == '0' && walls[j+moveAddition(mov)] == '0' && distances[index + moveAddition(mov)*257] == -1) { // move both i and j
  564.                                 distances[index + moveAddition(mov)*257] = depth+1;
  565.                             }
  566.                         }
  567.                     }
  568.                 }
  569.             }
  570.             depth++;
  571.         }
  572.        
  573.         return distances;
  574.     }
  575.    
  576.     // heuristic for minimum possible moves to solve this position
  577.     // OK so
  578.     // right now we are just finding the group that is the furthest from the next group and getting its minimum distance
  579.     // what we really want is the furthest a set of groups can be from everything else
  580.    
  581.     // new idea: find max distance between two groups (using triangle inequality)
  582.     static int minDistance(std::string &position, Groups &groups, std::vector<int> &distances, int groupPenalty, int alternate) {
  583.         // get list of distances between groups
  584.         std::vector<std::vector<int> > *pieceGroups = &groups.pieceGroups;
  585.         int groupSize = (int) pieceGroups->size();
  586.         std::vector<int> groupDistances (groupSize*groupSize, -1);
  587.         for (int i=0; i<groupSize; i++) {
  588.             groupDistances[i*groupSize+i] = 0;
  589.             char iColor = position[(*pieceGroups)[i][0]];
  590.             if (iColor < '2' || iColor > '4') continue;
  591.             for (int j=0; j<groupSize; j++) {
  592.                 if (i==j) continue;
  593.                 if (iColor != position[(*pieceGroups)[j][0]]) continue;
  594.                
  595.                 // minimum distance between piece in group and piece in other group
  596.                 int groupDistance = -1;
  597.                 for (int pi = 0; pi<(int)(*pieceGroups)[i].size(); pi++) {
  598.                     for (int pj = 0; pj<(int)(*pieceGroups)[j].size(); pj++) {
  599.                         int pDistance = distances[256*(*pieceGroups)[i][pi]+(*pieceGroups)[j][pj]];
  600.                         if (pDistance < groupDistance || groupDistance == -1) {
  601.                             groupDistance = pDistance;
  602.                         }
  603.                     }
  604.                 }
  605.                 groupDistances[i*groupSize+j] = groupDistance - 1; // tiles only need to get to distance 1 to connect
  606.             }
  607.         }
  608.        
  609.         // Floyd-Warshall?
  610.         // combining edges of size X and Y is max(X,Y), not X+Y
  611.         for (int k=0; k<groupSize; k++) {
  612.             for (int i=0; i<groupSize; i++) {
  613.                 for (int j=0; j<groupSize; j++) {
  614.                     if (groupDistances[i*groupSize+j] > groupDistances[i*groupSize+k] &&
  615.                         groupDistances[i*groupSize+k] != -1 && groupDistances[k*groupSize+j] != -1 &&
  616.                         groupDistances[i*groupSize+j] > groupDistances[k*groupSize+j]) {
  617.                         groupDistances[i*groupSize+j] = groupDistances[i*groupSize+k];
  618.                         if (groupDistances[i*groupSize+j] < groupDistances[k*groupSize+j])
  619.                             groupDistances[i*groupSize+j] = groupDistances[k*groupSize+j];
  620.                     }
  621.                 }
  622.             }
  623.         }
  624.        
  625.         int distance = -1;
  626.         if (alternate == 0) {
  627.             // report maximum distance
  628.             for (int i=0; i<groupSize; i++) {
  629.                 for (int j=0; j<groupSize; j++) {
  630.                     if (groupDistances[i*groupSize+j] > distance) {
  631.                         distance = groupDistances[i*groupSize+j];
  632.                     }
  633.                 }
  634.             }
  635.         } else if (alternate == 1) {
  636.             // report maximum distance
  637.             int distance2 = 0;
  638.             int distance3 = 0;
  639.             int distance4 = 0;
  640.             for (int i=0; i<groupSize; i++) {
  641.                 if (position[(*pieceGroups)[i][0]] == '2') {
  642.                     for (int j=0; j<groupSize; j++) {
  643.                         if (groupDistances[i*groupSize+j] > distance2) {
  644.                             distance2 = groupDistances[i*groupSize+j];
  645.                         }
  646.                     }
  647.                 } else if (position[(*pieceGroups)[i][0]] == '3') {
  648.                     for (int j=0; j<groupSize; j++) {
  649.                         if (groupDistances[i*groupSize+j] > distance3) {
  650.                             distance3 = groupDistances[i*groupSize+j];
  651.                         }
  652.                     }
  653.                 } else if (position[(*pieceGroups)[i][0]] == '4') {
  654.                     for (int j=0; j<groupSize; j++) {
  655.                         if (groupDistances[i*groupSize+j] > distance4) {
  656.                             distance4 = groupDistances[i*groupSize+j];
  657.                         }
  658.                     }
  659.                 }
  660.             }
  661.             distance = distance2 + distance3 + distance4;
  662.         }
  663.    
  664.         return distance + groupSize * groupPenalty;
  665.     }
  666.    
  667.     static std::string getWalls(std::string puzzle) {
  668.         std::string walls = "";
  669.         for (int i=0; i<256; i++) {
  670.             if (puzzle[i] == '1') {
  671.                 walls += '1';
  672.             } else {
  673.                 walls += '0';
  674.             }
  675.         }
  676.         return walls;
  677.     }
  678.  
  679.     // A BUNCH OF WAYS TO SOLVE STUFF
  680.     // solve with iterative deepening
  681.     static void iterativeDeepeningSolve(std::string puzzle) {
  682.         std::string walls = getWalls(puzzle);
  683.            
  684.         // start search
  685.         std::vector<std::string> noTaboo;
  686.         std::vector<int> distances = getManhattanDistances(walls);
  687.         int depth = 0;
  688.         int foundSolutions = 0;
  689.         clock_t start = clock();
  690.         while (foundSolutions == 0) {
  691.             int solutions = iterativeDeepeningSearch(puzzle, walls, distances, depth, "", noTaboo);
  692.             clock_t t = clock() - start;
  693.             if (solutions > 0) {
  694.                 std::cout << "Solutions: " << solutions << " at depth " << depth << " (t = " << t << ")\n";
  695.                 foundSolutions = 1;
  696.             } else {
  697.                 std::cout << "Depth " << depth << " done (t = " << t << ")\n";
  698.                 depth++;
  699.             }
  700.         }
  701.     }
  702.    
  703.     // position = position, walls = precomputed walls of position,
  704.     // remaining_depth = moves left to search, moves = move string so far
  705.     static int iterativeDeepeningSearch(std::string position, std::string walls, std::vector<int> distances, int remaining_depth, std::string moves, std::vector<std::string> taboo) {
  706.         //std::cout << moves << "\n";
  707.         int solutions = 0;
  708.        
  709.         // figure out piece groups
  710.         Groups groups = getGroups(position);
  711.        
  712.         if (looksSolvable(position, groups) == 0) return 0;
  713.        
  714.         // check for solved if we are out of moves
  715.         if (remaining_depth <= 0) {
  716.             int solved = isSolved(position, groups.pieceGroups);
  717.             if (solved==1) {
  718.                 std::cout << "Found solution: " << moves << "\n";
  719.             }
  720.             return solved;
  721.         }
  722.        
  723.         if (minDistance(position, groups, distances, 0, 0) > remaining_depth) return 0;
  724.        
  725.         // loop through moves
  726.         std::vector<std::string> newTaboo;
  727.         newTaboo.push_back(position);
  728.        
  729.         // try U move
  730.         std::string uPosition = applyMove(0, groups, position);
  731.         if (uPosition != position && inTaboo(uPosition, taboo) == 0) solutions += iterativeDeepeningSearch(uPosition, walls, distances, remaining_depth-1, moves+"U", newTaboo);
  732.        
  733.         // try D move
  734.         std::string dPosition = applyMove(1, groups, position);
  735.         if (dPosition != position && inTaboo(dPosition, taboo) == 0) solutions += iterativeDeepeningSearch(dPosition, walls, distances, remaining_depth-1, moves+"D", newTaboo);
  736.        
  737.         Groups uGroups = getGroups(uPosition);
  738.         Groups dGroups = getGroups(dPosition);
  739.        
  740.         // try L move (but no LU/LD if equal to UL/DL)
  741.         std::string lPosition = applyMove(2, groups, position);
  742.         if (lPosition != position && inTaboo(lPosition, taboo) == 0) {
  743.             std::vector<std::string> lTaboo = newTaboo;
  744.             lTaboo.push_back(applyMove(2, uGroups, uPosition));
  745.             lTaboo.push_back(applyMove(2, dGroups, dPosition));
  746.             solutions += iterativeDeepeningSearch(lPosition, walls, distances, remaining_depth-1, moves+"L", lTaboo);
  747.         }
  748.        
  749.         // try R move (but no RU/RD if equal to UR/DR)
  750.         std::string rPosition = applyMove(3, groups, position);
  751.         if (rPosition != position && inTaboo(rPosition, taboo) == 0) {
  752.             std::vector<std::string> rTaboo = newTaboo;
  753.             rTaboo.push_back(applyMove(3, uGroups, uPosition));
  754.             rTaboo.push_back(applyMove(3, dGroups, dPosition));
  755.             solutions += iterativeDeepeningSearch(rPosition, walls, distances, remaining_depth-1, moves+"R", rTaboo);
  756.         }
  757.    
  758.         return solutions;
  759.     }
  760.    
  761.     // solve by enumerating every position in one map
  762.     static void singleMapSolve(std::string puzzle, int goalMoves, int maxStates) {
  763.         std::string walls = getWalls(puzzle);
  764.            
  765.         // start with empty map (state -> <depth, movestring>)
  766.         std::map<std::vector<byte>, Moves> positions;
  767.         // insert starting state at depth 0, set main_depth = 0
  768.         std::vector<byte> noMoves;
  769.         positions[encode(puzzle)] = (Moves) {0, noMoves};
  770.         int foundSolution = 0;
  771.         int main_depth = 0;
  772.         std::vector<int> distances = getManhattanDistances(walls);
  773.        
  774.         Groups groups = getGroups(puzzle);
  775.    
  776.         while (foundSolution == 0) {
  777.             // iterate over map to look for depth == main_depth. for each
  778.             int foundPosition = 0;
  779.             for (std::map<std::vector<byte>, Moves>::iterator it=positions.begin(); it!=positions.end(); ++it) {
  780.                 if (it->second.nMoves == main_depth) {
  781.                     foundPosition = 1;
  782.                    
  783.                     std::string position = decode(it->first, walls);
  784.                     Groups groups = getGroups(position);
  785.                    
  786.                     if (looksSolvable(position, groups) == 0) continue;
  787.                    
  788.                     int solved = isSolved(position, groups.pieceGroups);
  789.                     if (solved == 1) {
  790.                         foundSolution = 1;
  791.                         std::cout << "Found solution: " << printMoves(it->second.moves, main_depth) << "\n";
  792.                         break;
  793. #if MINIMIZE_MATCHES == 1
  794.                     } else if (solved == -1) {
  795.                         continue;
  796. #endif
  797.                     }
  798.                    
  799.                     if ((int) positions.size() > maxStates) {
  800.                         continue;
  801.                     }
  802.                    
  803.                     if (minDistance(position, groups, distances, 0, 0) + main_depth >= goalMoves) {
  804.                         continue;
  805.                     }
  806.                    
  807.                     for (int mov = 0; mov < 4; mov++) {
  808.                         std::string newPosition = applyMove(mov, groups, position);
  809.                         // add this position into the map if it isn't already there
  810.                         if (positions.count(encode(newPosition)) == 0) {
  811.                             positions[encode(newPosition)] = (Moves) {it->second.nMoves + 1, addMove(it->second.moves, mov, it->second.nMoves)};
  812.                         }
  813.                     }
  814.                 }
  815.             }
  816.                
  817.             if (foundPosition == 0) {
  818.                 std::cout << "Could not find solution.\n";
  819.                 foundSolution = 1;
  820.             }
  821.                
  822.             main_depth++;
  823.             if (foundSolution == 0) {
  824.                 std::cout << "Depth " << main_depth << ", positions " << positions.size() << "\n";
  825.             }
  826.         }
  827.     }
  828.    
  829.     // solve by enumerating every position with one map per depth
  830.     static void moduloMapSolve(std::string puzzle, int goalMoves, int nMaps, int maxStates) {
  831.         std::string walls = getWalls(puzzle);
  832.            
  833.         // start with empty maps (state -> <depth, movestring>)
  834.         std::vector<std::map<std::vector<byte>, std::vector<byte> > > positions;
  835.         for (int i=0; i<nMaps; i++) {
  836.             std::map<std::vector<byte>, std::vector<byte> > subPositions;
  837.             positions.push_back(subPositions);
  838.         }
  839.        
  840.         // insert starting state at depth 0, set main_depth = 0
  841.         std::vector<byte> noMoves;
  842.         positions[0][encode(puzzle)] = noMoves;
  843.         int foundSolution = 0;
  844.         int main_depth = 0;
  845.         std::vector<int> distances = getManhattanDistances(walls);
  846.        
  847.         Groups groups = getGroups(puzzle);
  848.    
  849.         while (foundSolution == 0) {
  850.             // get current and next position maps
  851.             std::map<std::vector<byte>, std::vector<byte> > *curPositions = &positions[main_depth % nMaps];
  852.             std::map<std::vector<byte>, std::vector<byte> > *nextPositions = &positions[(main_depth + 1) % nMaps];
  853.             nextPositions->clear();
  854.            
  855.             int maxPositions = maxStates;
  856.             for (int i=0; i<nMaps; i++) {
  857.                 maxPositions -= positions[i].size();
  858.             }
  859.        
  860.             // iterate over map
  861.             int foundPosition = 0;
  862.             for (std::map<std::vector<byte>, std::vector<byte> >::iterator it=curPositions->begin(); it!=curPositions->end(); ++it) {
  863.                 foundPosition = 1;
  864.                    
  865.                 std::string position = decode(it->first, walls);
  866.                 Groups groups = getGroups(position);
  867.                    
  868.                 if (looksSolvable(position, groups) == 0) continue;
  869.                
  870.                 int solved = isSolved(position, groups.pieceGroups);
  871.                 if (solved == 1) {
  872.                     foundSolution = 1;
  873.                     std::cout << "Found solution: " << printMoves(it->second, main_depth) << "\n";
  874.                     break;
  875. #if MINIMIZE_MATCHES == 1
  876.                 } else if (solved == -1) {
  877.                     continue;
  878. #endif
  879.                 }
  880.                    
  881.                 if ((int) nextPositions->size() > maxPositions) {
  882.                     continue;
  883.                 }
  884.                    
  885.                 if (minDistance(position, groups, distances, 0, 0) + main_depth >= goalMoves) {
  886.                     continue;
  887.                 }
  888.                
  889.                 // loop through moves
  890.                 for (int mov = 0; mov < 4; mov++) {
  891.                     std::string newPosition = applyMove(mov, groups, position);
  892.                     int positionExists = 0;
  893.                     std::vector<byte> encoded = encode(newPosition);
  894.                     for (int i=0; i<nMaps; i++) {
  895.                         if (positions[i].count(encoded) != 0) {
  896.                             positionExists = 1;
  897.                             break;
  898.                         }
  899.                     }
  900.                     if (positionExists == 0) {
  901.                         (*nextPositions)[encoded] = addMove(it->second, mov, main_depth);
  902.                     }
  903.                 }
  904.             }
  905.                
  906.             if (foundPosition == 0) {
  907.                 std::cout << "Could not find solution.\n";
  908.                 foundSolution = 1;
  909.             }
  910.                
  911.             main_depth++;
  912.             if (foundSolution == 0) {
  913.                 std::cout << "Depth " << main_depth << ", positions " << nextPositions->size() << "\n";
  914.             }
  915.            
  916.             if ((int) nextPositions->size() > maxPositions) {
  917.                 break;
  918.             }
  919.         }
  920.     }
  921.    
  922. #if USING_SHAPE == 1
  923.     static int allInShape(std::string &position, Groups &groups) {
  924.         std::vector<int> goalShape;
  925.         goalShape = GOAL_SHAPE;
  926.        
  927.         // want to make sure each group of large-enough size is part of the goal shape
  928.         int groupCount = groups.pieceGroups.size();
  929.         for (int i=0; i<groupCount; i++) {
  930.             std::vector<int> subShape = groups.pieceGroups[i];
  931.             if (position[subShape[0]] COLOR_TEST && subShape.size() >= 2) {
  932.                 // is this group part of the goal shape?
  933.                 int found = 0;
  934.                 for (int ctr = 0; ctr < (int) goalShape.size(); ctr++) {
  935.                     int subPtr = 0;
  936.                     int goalPtr = ctr;
  937.                     while (subPtr < (int)subShape.size() && goalPtr < (int)goalShape.size()) {
  938.                         if (subShape[subPtr]-subShape[0] == goalShape[goalPtr]-goalShape[ctr]) {
  939.                             subPtr++;
  940.                         }
  941.                         goalPtr++;
  942.                     }
  943.                     if (subPtr == (int)subShape.size()) {
  944.                         found = 1;
  945.                         break;
  946.                     }
  947.                 }
  948.                 if (found == 0) {
  949.                     return 0;
  950.                 }
  951.             }
  952.         }
  953.         return 1;
  954.     }
  955. #endif
  956.  
  957.     static int looksSolvable(std::string &position, Groups &groups) {
  958. #if USING_SHAPE == 1
  959.         if (allInShape(position, groups) == 0) return 0;
  960. #endif
  961.  
  962.         // put any puzzle-specific code here!
  963.        
  964.         return 1;
  965.     }
  966.    
  967.    
  968.    
  969.     // solve by enumerating almost every position with one map per depth
  970.     // drop states if we need to so we don't have more than maxStatesPer per depth
  971.     static int moduloMapSuboptimalSolve(std::string puzzle, int goalMoves, int nMaps, int maxStatesPer, int penalty) {
  972.         std::string walls = getWalls(puzzle);
  973.            
  974.         // start with empty maps (state -> <depth, movestring>)
  975.         std::vector<std::map<std::vector<byte>, std::vector<byte> > > positions;
  976.         for (int i=0; i<nMaps; i++) {
  977.             std::map<std::vector<byte>, std::vector<byte> > subPositions;
  978.             positions.push_back(subPositions);
  979.         }
  980.        
  981.         // insert starting state at depth 0, set main_depth = 0
  982.         std::vector<byte> noMoves;
  983.         positions[0][encode(puzzle)] = noMoves;
  984.         int foundSolution = 0;
  985.         int main_depth = 0;
  986.         std::vector<int> distances = getManhattanDistances(walls);
  987.        
  988.         Groups groups = getGroups(puzzle);
  989.    
  990.         while (foundSolution == 0) {
  991.             // get current and next position maps
  992.             std::map<std::vector<byte>, std::vector<byte> > *curPositions = &positions[main_depth % nMaps];
  993.             std::map<std::vector<byte>, std::vector<byte> > *nextPositions = &positions[(main_depth + 1) % nMaps];
  994.             nextPositions->clear();
  995.             std::priority_queue<Queued> queued;
  996.            
  997.             //int printed = 0;
  998.        
  999.             // iterate over map
  1000.             int foundPosition = 0;
  1001.             for (std::map<std::vector<byte>, std::vector<byte> >::iterator it=curPositions->begin(); it!=curPositions->end(); ++it) {
  1002.                 foundPosition = 1;
  1003.                    
  1004.                 std::string position = decode(it->first, walls);
  1005.                 Groups groups = getGroups(position);
  1006.                    
  1007.                 if (looksSolvable(position, groups) == 0) continue;
  1008.                
  1009.                 //if (printed == 0) {
  1010.                 //  printGrid(position);
  1011.                 //  printed = 1;
  1012.                 //}
  1013.                
  1014.                 int solved = isSolved(position, groups.pieceGroups);
  1015.                 if (solved == 1) {
  1016.                     foundSolution = 1;
  1017.                     std::cout << "Found suboptimal solution: " << printMoves(it->second, main_depth) << "\n";
  1018.                     return main_depth;
  1019. #if MINIMIZE_MATCHES == 1
  1020.                 } else if (solved == -1) {
  1021.                     continue;
  1022. #endif
  1023.                 }
  1024.                    
  1025.                 if (minDistance(position, groups, distances, 0, 0) + main_depth >= goalMoves) {
  1026.                     continue;
  1027.                 }
  1028.                
  1029.                 // loop through moves
  1030.                 for (int mov = 0; mov < 4; mov++) {
  1031.                     std::string newPosition = applyMove(mov, groups, position);
  1032.                     int positionExists = 0;
  1033.                     std::vector<byte> encoded = encode(newPosition);
  1034.                     for (int i=0; i<nMaps; i++) {
  1035.                         if (positions[i].count(encoded) != 0) {
  1036.                             positionExists = 1;
  1037.                             break;
  1038.                         }
  1039.                     }
  1040.                     if (positionExists == 0) {
  1041.                         // add to both nextPositions and priority queue
  1042.                         Groups newGroups = getGroups(newPosition);
  1043.                         int minDist = minDistance(newPosition, newGroups, distances, penalty, ALTERNATE_HEURISTIC);
  1044.                         (*nextPositions)[encoded] = addMove(it->second, mov, main_depth);
  1045.                         queued.push((Queued) {minDist, encoded});
  1046.                        
  1047.                         // but if priority queue is too big, delete one
  1048.                         if ((int) nextPositions->size() > maxStatesPer) {
  1049.                             nextPositions->erase(queued.top().key);
  1050.                             queued.pop();
  1051.                         }
  1052.                     }
  1053.                 }
  1054.             }
  1055.                
  1056.             if (foundPosition == 0) {
  1057.                 std::cout << "Could not find solution.\n";
  1058.                 foundSolution = 1;
  1059.                 return -1;
  1060.             }
  1061.                
  1062.             main_depth++;
  1063.             if (foundSolution == 0) {
  1064.                 std::cout << "Depth " << main_depth << ", positions " << nextPositions->size() << "\n";
  1065.             }
  1066.            
  1067.             //if ((int) nextPositions->size() > maxStatesPer) {
  1068.             //  break;
  1069.             //}
  1070.         }
  1071.         return -1;
  1072.     }
  1073.    
  1074.     // solve with iterative deepening
  1075.     static void iterativeDeepeningSolve2(std::string puzzle, int goalMoves, int cacheSize) {
  1076.         std::string walls = getWalls(puzzle);
  1077.            
  1078.         // start search
  1079.         std::vector<int> distances = getManhattanDistances(walls);
  1080.         int depth = 0;
  1081.         int foundSolutions = 0;
  1082.         clock_t start = clock();
  1083.         while (foundSolutions == 0 && depth <= goalMoves) {
  1084.             std::vector<LruCache*> caches;
  1085.             for (int i=0; i<=depth; i++) {
  1086.                 LruCache* l = new LruCache(cacheSize);
  1087.                 caches.push_back(l);
  1088.             }
  1089.  
  1090.             int solutions = iterativeDeepeningSearch2(puzzle, walls, distances, depth, "", caches);
  1091.             clock_t t = clock() - start;
  1092.             if (solutions > 0) {
  1093.                 std::cout << "Solutions: " << solutions << " at depth " << depth << " (t = " << t << ")\n";
  1094.                 foundSolutions = 1;
  1095.             } else {
  1096.                 std::cout << "Depth " << depth << " done (t = " << t << ")\n";
  1097.                 depth++;
  1098.             }
  1099.            
  1100.             for (std::vector<LruCache*>::iterator it = caches.begin() ; it != caches.end(); ++it)
  1101.             {
  1102.                 delete (*it);
  1103.             }
  1104.             caches.clear();
  1105.         }
  1106.     }
  1107.     /*
  1108.     // single DFS run
  1109.     static void iterativeDeepeningSolve2(std::string puzzle, int goalMoves, int cacheSize) {
  1110.         std::string walls = getWalls(puzzle);
  1111.            
  1112.         // start search
  1113.         std::vector<int> distances = getManhattanDistances(walls);
  1114.         int depth = goalMoves - 1;
  1115.         int foundSolutions = 0;
  1116.         clock_t start = clock();
  1117.        
  1118.         std::vector<LruCache*> caches;
  1119.         for (int i=0; i<=depth; i++) {
  1120.             LruCache* l = new LruCache(cacheSize);
  1121.             caches.push_back(l);
  1122.         }
  1123.  
  1124.         int solutions = iterativeDeepeningSearch2(puzzle, walls, distances, depth, "", caches);
  1125.         clock_t t = clock() - start;
  1126.         if (solutions > 0) {
  1127.             std::cout << "Solutions: " << solutions << " at depth " << depth << " (t = " << t << ")\n";
  1128.             foundSolutions = 1;
  1129.         } else {
  1130.             std::cout << "No solutions (t = " << t << ")\n";
  1131.         }
  1132.            
  1133.         for (std::vector<LruCache*>::iterator it = caches.begin() ; it != caches.end(); ++it)
  1134.         {
  1135.             delete (*it);
  1136.         }
  1137.         caches.clear();
  1138.     }*/
  1139.    
  1140.     // position = position, walls = precomputed walls of position,
  1141.     // remaining_depth = moves left to search, moves = move string so far
  1142.     static int iterativeDeepeningSearch2(std::string position, std::string walls, std::vector<int> distances, int remaining_depth, std::string moves, std::vector<LruCache*> caches) {
  1143.         //std::cout << moves << "\n";
  1144.         int solutions = 0;
  1145.        
  1146.         // figure out piece groups
  1147.         Groups groups = getGroups(position);
  1148.        
  1149.         if (looksSolvable(position, groups) == 0) return 0;
  1150.        
  1151.         // check for solved if we are out of moves
  1152.         if (remaining_depth <= 0) {
  1153.             int solved = isSolved(position, groups.pieceGroups);
  1154.             if (solved==1) {
  1155.                 std::cout << "Found solution: " << moves << "\n";
  1156.             }
  1157.             return solved;
  1158.         }
  1159.        
  1160.         if (minDistance(position, groups, distances, 0, 0) > remaining_depth) return 0;
  1161.        
  1162.         // check if this position is in the cache(s)
  1163.         bool cached = false;
  1164.         for (int i=remaining_depth; (i<=(remaining_depth + 3) && i<(int)caches.size()); i++) {
  1165.             if (caches[i]->contains(position)) {
  1166.                 cached = true;
  1167.                 break;
  1168.             }
  1169.         }
  1170.         if (cached) {
  1171.             return 0;
  1172.         } else {
  1173.             caches[remaining_depth]->insert(position);
  1174.         }
  1175.        
  1176.         // loop through moves UDLR
  1177.         std::string newPosition = applyMove(0, groups, position);
  1178.         solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+"U", caches);
  1179.         newPosition = applyMove(1, groups, position);
  1180.         solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+"D", caches);
  1181.         newPosition = applyMove(2, groups, position);
  1182.         solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+"L", caches);
  1183.         newPosition = applyMove(3, groups, position);
  1184.         solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+"R", caches);
  1185.         /*for (int mov = 0; mov < 4; mov++) {
  1186.             std::string newPosition = applyMove(mov, groups, position);
  1187.                    
  1188.             solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+moveName[mov], caches);
  1189.         }*/
  1190.    
  1191.         return solutions;
  1192.     }
  1193.    
  1194.    
  1195.     // todo:
  1196.     // - build a shape
  1197.    
  1198.    
  1199.  
  1200.     static int solve() {
  1201.         while (true) {
  1202.             // get puzzle
  1203.             int goalMoves = 100;
  1204.             std::string puzzle;
  1205.             std::string totalInput = "";
  1206.            
  1207.             while (totalInput.length() < 256) {
  1208.                 std::string input = "";
  1209.                 getline(std::cin, input);
  1210.                 if (input == "") {
  1211.                     return EXIT_SUCCESS;
  1212.                 }
  1213.                 totalInput += input;
  1214.             }
  1215.                
  1216.             // process puzzle (and possibly a |number)
  1217.             puzzle = totalInput.substr(0, 256);
  1218.             if (totalInput.length() > 256) {
  1219.                 goalMoves = 0;
  1220.                 for (int i=256; i<(int)totalInput.length(); i++) {
  1221.                     if (totalInput[i] >= '0' && totalInput[i] <= '9') {
  1222.                         goalMoves = goalMoves*10 + (totalInput[i] - '0');
  1223.                     }
  1224.                 }
  1225.             }
  1226.            
  1227.             // print puzzle
  1228.             printGrid(puzzle);
  1229.            
  1230.             //iterativeDeepeningSolve(puzzle);
  1231.             //iterativeDeepeningSolve2(puzzle, goalMoves, 10000);
  1232.            
  1233.             //terminate called after throwing an instance of 'std::bad_alloc'
  1234.             //  what():  std::bad_alloc
  1235.            
  1236.             //moduloMapSolve(puzzle, goalMoves, 4, 10000000);
  1237.            
  1238.             std::cout << "(Penalty 5)" << std::endl;
  1239.             while (true) {
  1240.                 int newGoal = moduloMapSuboptimalSolve(puzzle, goalMoves, 100, 10000, 5);
  1241.                 if (newGoal == -1 || newGoal >= goalMoves) break;
  1242.                 goalMoves = newGoal;
  1243.                 std::cout << "Goal changed to " << goalMoves << " moves" << std::endl;
  1244.             }
  1245.             std::cout << "(Penalty 1)" << std::endl;
  1246.             while (true) {
  1247.                 int newGoal = moduloMapSuboptimalSolve(puzzle, goalMoves, 100, 10000, 1);
  1248.                 if (newGoal == -1 || newGoal >= goalMoves) break;
  1249.                 goalMoves = newGoal;
  1250.                 std::cout << "Goal changed to " << goalMoves << " moves" << std::endl;
  1251.             }
  1252.             std::cout << "(Penalty 0)" << std::endl;
  1253.             while (true) {
  1254.                 int newGoal = moduloMapSuboptimalSolve(puzzle, goalMoves, 100, 10000, 0);
  1255.                 if (newGoal == -1 || newGoal >= goalMoves) break;
  1256.                 goalMoves = newGoal;
  1257.                 std::cout << "Goal changed to " << goalMoves << " moves" << std::endl;
  1258.             }
  1259.         }
  1260.        
  1261.         return EXIT_SUCCESS;
  1262.     }
  1263. };
  1264.  
  1265. int main(int argc, char *argv[]) {
  1266.     DenkiSolver::solve();
  1267. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!