API tools faq
paste
Advertisement
qqwref

Denki Blocks solver

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