Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- (Sub)Optimal Denki Blocks solver
- Copyright (C) 2014-5 Michael Gottlieb
- */
- // do we care about pairs / 3-of-a-kinds?
- #define USING_PAIRS 1 // needs to be 1 if anything in this group is
- #define NO_PAIRS 0 // forbid any pairs
- #define NO_THREE_KIND 0 // pairs are OK, but forbid 3-of-a-kinds
- #define THREE_KIND_ONLY 1 // allow 3-of-a-kind only
- // should we minimize matches?
- #define MINIMIZE_MATCHES 0 // needs to be 1 if anything in this group is
- #define ONE_MATCH 0 // forbid unsolved states with some but not all colors paired
- #define TWO_MATCHES_ONE 0 // forbid all states with exactly one color paired
- #define TWO_MATCHES_TWO 0 // forbid all states with exactly two colors paired
- // use alternate heuristic for suboptimal solves?
- #define ALTERNATE_HEURISTIC 1
- // make sure we can make a shape?
- #define USING_SHAPE 0 // needs to be 1 if anything in this group is
- #define COLOR_TEST < '5' // test to see if we care about this color
- // e.g. "== '2'" for bonus shape, "< '5'" for 3 of a kind
- #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}
- // goal shape
- // for use when looking for a partial solution (set to 0 when not in use)
- #define GOAL_GROUP_NUM 0
- // Main struct and control flow of program, with all includes used in it
- #include <algorithm>
- #include <fstream>
- #include <iostream>
- #include <list>
- #include <map>
- #include <queue>
- #include <string>
- #include <time.h>
- #include <vector>
- #include <windows.h>
- typedef unsigned char byte;
- struct Groups {
- std::vector<std::vector<int> > pieceGroups;
- std::map<int, int> inversePieceGroups;
- };
- struct Moves {
- int nMoves;
- std::vector<byte> moves;
- };
- struct Queued {
- int minDist;
- std::vector<byte> key;
- bool operator< (const Queued other) const {
- return (minDist < other.minDist);
- }
- };
- // http://timday.bitbucket.org/lru.html
- class LruCache
- {
- public:
- typedef std::map<std::string, std::list<std::string>::iterator> key_lookup;
- LruCache(size_t c): _capacity(c) {
- }
- // is k in cache?
- bool contains(const std::string& k) {
- return (lookup.find(k) != lookup.end());
- }
- // Obtain value of the cached function for k
- bool operator()(const std::string& k) {
- const typename key_lookup::iterator it = lookup.find(k);
- if (it==lookup.end()) {
- insert(k);
- return false;
- } else {
- keys.splice(keys.end(), keys, (*it).second);
- return true;
- }
- }
- // Record a fresh key in the cache
- void insert(const std::string& k) {
- if (lookup.size()==_capacity)
- evict();
- std::list<std::string>::iterator it = keys.insert(keys.end(),k);
- lookup.insert(std::make_pair(k, it));
- }
- private:
- // Purge the least-recently-used element in the cache
- void evict() {
- const typename key_lookup::iterator it = lookup.find(keys.front());
- lookup.erase(it);
- keys.pop_front();
- }
- const size_t _capacity; // Maximum number of key-value pairs to be retained
- std::list<std::string> keys; // Key access history
- key_lookup lookup; // Key lookup
- };
- struct DenkiSolver {
- static void printGrid(std::string state) {
- std::cout << "+----------------+\n";
- for (int i=0; i<16; i++) {
- std::cout << "|";
- for (int j=0; j<16; j++) {
- if (state[i*16+j] == '0') {
- std::cout << ' ';
- } else {
- std::cout << state[i*16+j];
- }
- }
- std::cout << "|\n";
- }
- std::cout << "+----------------+\n";
- }
- // moves: 0=U 1=D 2=L 3=R
- // print compressed moves
- static std::string printMoves(std::vector<byte> moves, int moveCount) {
- std::string moveList;
- std::string moveName = "UDLR";
- int i;
- for (i=0; i<(moveCount/4); i++) {
- int x = (int) moves[i];
- moveList += moveName[(x & 192) >> 6];
- moveList += moveName[(x & 48) >> 4];
- moveList += moveName[(x & 12) >> 2];
- moveList += moveName[(x & 3)];
- }
- int x = moves[i];
- if (moveCount % 4 > 2) moveList += moveName[(x & 48) >> 4];
- if (moveCount % 4 > 1) moveList += moveName[(x & 12) >> 2];
- if (moveCount % 4 > 0) moveList += moveName[x & 3];
- return moveList;
- }
- // add a move to an existing series of moves
- static std::vector<byte> addMove(std::vector<byte> moves, int mov, int moveCount) {
- std::vector<byte> newMoves = moves;
- if (moveCount % 4 == 0) { // add a new move byte
- newMoves.push_back(mov);
- newMoves.shrink_to_fit();
- } else { // add moves to the last byte
- newMoves[newMoves.size() - 1] = 4*newMoves[newMoves.size() - 1] + mov;
- }
- return newMoves;
- }
- // can we apply this move to this piece?
- static bool isValid(int move, int n) {
- if (move == 0) {
- return (n >= 16);
- } else if (move == 1) {
- return (n <= 239);
- } else if (move == 2) {
- return (n%16 != 0);
- } else {
- return (n%16 != 15);
- }
- }
- // encode a string (to take up less space)
- static std::vector<byte> encode(std::string input) {
- std::vector<byte> output;
- int nEmpty = 0;
- for (int i=0; i<256; i++) {
- if (input[i] == '0' || input[i] == '1') {
- nEmpty++;
- } else {
- while (nEmpty >= 64) {
- output.push_back('9' + 64);
- nEmpty -= 64;
- }
- if (nEmpty > 0) {
- output.push_back('9' + nEmpty);
- }
- nEmpty = 0;
- output.push_back(input[i]);
- }
- }
- output.shrink_to_fit();
- return output;
- }
- // decode a string
- static std::string decode(std::vector<byte> input, std::string walls) {
- std::string output = "";
- int cnt = 0;
- for (int i=0; i<(int)input.size(); i++) {
- if (input[i] <= '9') {
- output += input[i];
- cnt++;
- } else {
- for (int j=0; j<(int) (input[i] - '9'); j++) {
- output += walls[cnt];
- cnt++;
- }
- }
- }
- while (cnt < 256) {
- output += walls[cnt];
- cnt++;
- }
- return output;
- }
- // get pieceGroups and inversePieceGroups
- static Groups getGroups(std::string position) {
- Groups groups;
- // initialize visited array
- std::vector<int> visited (256, 0);
- for (int i=0; i<256; i++) {
- if (position[i] <= '1') {
- visited[i] = 1;
- }
- }
- // look for piece groups
- int groupCount = 0;
- for (int i=0; i<256; i++) {
- if (visited[i] == 1) continue;
- std::vector<int> group;
- int groupI = 0;
- char correct = position[i];
- group.push_back(i);
- visited[i] = 1;
- groups.inversePieceGroups[i] = groupCount;
- while (groupI < (int) group.size()) {
- int x = group[groupI];
- for (int mov=0; mov<4; mov++) {
- if (isValid(mov, x)) {
- int add = moveAddition(mov);
- if (visited[x+add]==0 && position[x+add]==correct) {
- group.push_back(x+add);
- visited[x+add] = 1;
- groups.inversePieceGroups[x+add] = groupCount;
- }
- }
- }
- groupI++;
- }
- #if USING_PAIRS == 1 || USING_SHAPE == 1
- std::sort(group.begin(), group.end());
- #endif
- groups.pieceGroups.push_back(group);
- groupCount++;
- }
- return groups;
- }
- // determine which piece groups can move
- static std::vector<int> whatCanMove(int move, Groups groups, std::string position) {
- // 0 = not processed
- // 1 = can move
- // 2 = can't move
- // 3 = in use, not analyzed
- // 4 = in use, analyzed
- int add = moveAddition(move);
- std::vector<std::vector<int> > *pieceGroups = &groups.pieceGroups;
- int groupCount = (int) pieceGroups->size();
- std::map<int, int> *inversePieceGroups = &groups.inversePieceGroups;
- std::vector<int> canMove (groupCount, 0);
- for (int i=0; i<groupCount; i++) {
- if (canMove[i] > 0) continue;
- canMove[i] = 3; // in use, not analyzed
- int curGroup = i;
- while (curGroup != -1) {
- // check the position above each piece in the group
- std::vector<int> *thisGroup = &((*pieceGroups)[curGroup]);
- for (int j=0; j<(int) thisGroup->size(); j++) {
- // if at the edge, no good
- if (!isValid(move, (*thisGroup)[j])) {
- canMove[i] = 2;
- break;
- }
- char pieceForward = position[(*thisGroup)[j] + add];
- // if there's a wall in the way, no good
- if (pieceForward == '1') {
- canMove[i] = 2;
- break;
- }
- // if there's another piece in the way...
- if (pieceForward > '1') {
- int groupForward = (*inversePieceGroups)[(*thisGroup)[j] + add];
- // if that other group can't move, neither can we
- if (canMove[groupForward] == 2) {
- canMove[i] = 2;
- break;
- }
- // if that other group isn't processed, work on it
- if (canMove[groupForward] == 0) {
- canMove[groupForward] = 3;
- }
- }
- }
- if (canMove[i] == 2) break;
- // done with this group
- canMove[curGroup] = 4;
- // get another working group
- curGroup = -1;
- for (int j=0; j<groupCount; j++) {
- if (canMove[j] == 3) {
- curGroup = j;
- }
- }
- }
- // so could we move this group?
- if (canMove[i] == 2) { // no
- for (int j=0; j<groupCount; j++) {
- if (canMove[j] > 2) {
- canMove[j] = 0;
- }
- }
- } else { // yes - all intermediate groups can be moved too
- for (int j=0; j<groupCount; j++) {
- if (canMove[j] > 2) {
- canMove[j] = 1;
- }
- }
- }
- }
- return canMove;
- }
- static std::string applyMove(int mov, Groups groups, std::string position) {
- // determine what can move
- std::vector<int> canMove = whatCanMove(mov, groups, position);
- // move 'em
- std::string newPosition = position;
- std::map<int, int> *inversePieceGroups = &groups.inversePieceGroups;
- if (mov == 0) { // up
- for (int y=0; y<15; y++) {
- for (int x=0; x<16; x++) {
- if (position[y*16 + x + 16] > '1') {
- if (canMove[(*inversePieceGroups)[y*16 + x + 16]] == 1) {
- newPosition[y*16 + x] = newPosition[y*16 + x + 16];
- newPosition[y*16 + x + 16] = '0';
- }
- }
- }
- }
- } else if (mov == 1) { // down
- for (int y=15; y>0; y--) {
- for (int x=0; x<16; x++) {
- if (position[y*16 + x - 16] > '1') {
- if (canMove[(*inversePieceGroups)[y*16 + x - 16]] == 1) {
- newPosition[y*16 + x] = newPosition[y*16 + x - 16];
- newPosition[y*16 + x - 16] = '0';
- }
- }
- }
- }
- } else if (mov == 2) { // left
- for (int y=0; y<16; y++) {
- for (int x=0; x<15; x++) {
- if (position[y*16 + x + 1] > '1') {
- if (canMove[(*inversePieceGroups)[y*16 + x + 1]] == 1) {
- newPosition[y*16 + x] = newPosition[y*16 + x + 1];
- newPosition[y*16 + x + 1] = '0';
- }
- }
- }
- }
- } else { // right
- for (int y=0; y<16; y++) {
- for (int x=15; x>0; x--) {
- if (position[y*16 + x - 1] > '1') {
- if (canMove[(*inversePieceGroups)[y*16 + x - 1]] == 1) {
- newPosition[y*16 + x] = newPosition[y*16 + x - 1];
- newPosition[y*16 + x - 1] = '0';
- }
- }
- }
- }
- }
- return newPosition;
- }
- // check if solved
- static int isSolved(std::string position, std::vector<std::vector<int> > pieceGroups) {
- #if GOAL_GROUP_NUM > 0
- // for partial solutions
- if (pieceGroups.size() <= GOAL_GROUP_NUM) {
- return 1;
- } else {
- return 0;
- }
- #endif
- int group2=0, group3=0, group4=0; // how many of each of the 3 matching colors
- for (int i=0; i<(int) pieceGroups.size(); i++) {
- char correct = position[pieceGroups[i][0]];
- if (correct == '2') {
- group2++;
- } else if (correct == '3') {
- group3++;
- } else if (correct == '4') {
- group4++;
- }
- }
- if (group2<2 && group3<2 && group4<2) {
- #if USING_PAIRS == 1
- // OK, it's solved. but do we have a pair?
- int only2=-1, only3=-1, only4=-1;
- for (int i=0; i<(int) pieceGroups.size(); i++) {
- char correct = position[pieceGroups[i][0]];
- if (correct == '2') {
- only2 = i;
- } else if (correct == '3') {
- only3 = i;
- } else if (correct == '4') {
- only4 = i;
- }
- }
- #if NO_PAIRS == 1
- if (only2 > -1 && only3 > -1 && sameShape(pieceGroups[only2], pieceGroups[only3]) == 1)
- return -1;
- if (only2 > -1 && only4 > -1 && sameShape(pieceGroups[only2], pieceGroups[only4]) == 1)
- return -1;
- if (only3 > -1 && only4 > -1 && sameShape(pieceGroups[only3], pieceGroups[only4]) == 1)
- return -1;
- return 1;
- #endif
- #if NO_THREE_KIND == 1
- if (only2 > -1 && only3 > -1 && sameShape(pieceGroups[only2], pieceGroups[only3]) != 1)
- return 1;
- if (only2 > -1 && only4 > -1 && sameShape(pieceGroups[only2], pieceGroups[only4]) != 1)
- return 1;
- if (only3 > -1 && only4 > -1 && sameShape(pieceGroups[only3], pieceGroups[only4]) != 1)
- return 1;
- return -1;
- #endif
- #if THREE_KIND_ONLY == 1
- if (only2 > -1 && only3 > -1 && sameShape(pieceGroups[only2], pieceGroups[only3]) != 1)
- return -1;
- if (only2 > -1 && only4 > -1 && sameShape(pieceGroups[only2], pieceGroups[only4]) != 1)
- return -1;
- if (only3 > -1 && only4 > -1 && sameShape(pieceGroups[only3], pieceGroups[only4]) != 1)
- return -1;
- return 1;
- #endif
- #endif
- return 1;
- #if ONE_MATCH == 1
- } else if ((group2>1 || group3>1 || group4>1) && (group2==1 || group3==1 || group4==1)) {
- return -1;
- #endif
- #if TWO_MATCHES_ONE == 1
- // don't allow exactly 1 thing matched
- } else if ((group2==1 && group3!=1 && group4!=1) || (group2!=1 && group3==1 && group4!=1) || (group2!=1 && group3!=1 && group4==1)) {
- return -1;
- #endif
- #if TWO_MATCHES_TWO == 1
- // don't allow exactly 2 things matched
- } else if ((group2==1 && group3==1 && group4!=1) || (group2==1 && group3!=1 && group4==1) || (group2!=1 && group3==1 && group4==1)) {
- return -1;
- #endif
- } else {
- return 0;
- }
- }
- // do these two groups have the same shape?
- // the two groups should be sorted
- static int sameShape(std::vector<int> group1, std::vector<int> group2) {
- if (group1.size() != group2.size()) {
- return 0;
- }
- int dx = (group2[0]%16) - (group1[0]%16);
- int dy = (group2[0]/16) - (group1[0]/16);
- for (int i=1; i<(int) group1.size(); i++) {
- if ((group2[i]%16) - (group1[i]%16) != dx)
- return 0;
- if ((group2[i]/16) - (group1[i]/16) != dy)
- return 0;
- }
- return 1;
- }
- static int moveAddition(int mov) {
- // -16, 16, -1, 1
- if (mov == 0) {
- return -16;
- } else if (mov == 1) {
- return 16;
- } else if (mov == 2) {
- return -1;
- } else if (mov == 3) {
- return 1;
- } else {
- return 0;
- }
- }
- static int inTaboo(std::string position, std::vector<std::string> taboo) {
- int inTaboo = 0;
- for (int i=0; i<(int) taboo.size(); i++) {
- if (taboo[i] == position) {
- inTaboo = 1;
- break;
- }
- }
- return inTaboo;
- }
- // get distances between every pair of positions
- // allowed moves:
- // - move one piece in a direction
- // - move both pieces in same direction
- static std::vector<int> getManhattanDistances(std::string walls) {
- // walls are '0's and '1's
- std::vector<int> distances (256*256, -1);
- for (int i=0; i<256; i++) {
- if (walls[i] == '0')
- distances[i*257] = 0;
- }
- int depth = 0;
- int foundPositions = 1;
- // loop by depth
- while (foundPositions > 0) {
- foundPositions = 0;
- // find point pairs of this depth
- for (int i=0; i<256; i++) {
- for (int j=0; j<256; j++) {
- int index = i*256+j;
- if (distances[index] == depth) {
- foundPositions++;
- // what pairs of points are at depth+1?
- for (int mov=0; mov<4; mov++) {
- if (isValid(mov,i) && walls[i+moveAddition(mov)] == '0' && distances[index + moveAddition(mov)*256] == -1) { // move i only
- distances[index + moveAddition(mov)*256] = depth+1;
- }
- if (isValid(mov,j) && walls[j+moveAddition(mov)] == '0' && distances[index + moveAddition(mov)] == -1) { // move j only
- distances[index + moveAddition(mov)] = depth+1;
- }
- 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
- distances[index + moveAddition(mov)*257] = depth+1;
- }
- }
- }
- }
- }
- depth++;
- }
- return distances;
- }
- // heuristic for minimum possible moves to solve this position
- // OK so
- // right now we are just finding the group that is the furthest from the next group and getting its minimum distance
- // what we really want is the furthest a set of groups can be from everything else
- // new idea: find max distance between two groups (using triangle inequality)
- static int minDistance(std::string &position, Groups &groups, std::vector<int> &distances, int groupPenalty, int alternate) {
- // get list of distances between groups
- std::vector<std::vector<int> > *pieceGroups = &groups.pieceGroups;
- int groupSize = (int) pieceGroups->size();
- std::vector<int> groupDistances (groupSize*groupSize, -1);
- for (int i=0; i<groupSize; i++) {
- groupDistances[i*groupSize+i] = 0;
- char iColor = position[(*pieceGroups)[i][0]];
- if (iColor < '2' || iColor > '4') continue;
- for (int j=0; j<groupSize; j++) {
- if (i==j) continue;
- if (iColor != position[(*pieceGroups)[j][0]]) continue;
- // minimum distance between piece in group and piece in other group
- int groupDistance = -1;
- for (int pi = 0; pi<(int)(*pieceGroups)[i].size(); pi++) {
- for (int pj = 0; pj<(int)(*pieceGroups)[j].size(); pj++) {
- int pDistance = distances[256*(*pieceGroups)[i][pi]+(*pieceGroups)[j][pj]];
- if (pDistance < groupDistance || groupDistance == -1) {
- groupDistance = pDistance;
- }
- }
- }
- groupDistances[i*groupSize+j] = groupDistance - 1; // tiles only need to get to distance 1 to connect
- }
- }
- // Floyd-Warshall?
- // combining edges of size X and Y is max(X,Y), not X+Y
- for (int k=0; k<groupSize; k++) {
- for (int i=0; i<groupSize; i++) {
- for (int j=0; j<groupSize; j++) {
- if (groupDistances[i*groupSize+j] > groupDistances[i*groupSize+k] &&
- groupDistances[i*groupSize+k] != -1 && groupDistances[k*groupSize+j] != -1 &&
- groupDistances[i*groupSize+j] > groupDistances[k*groupSize+j]) {
- groupDistances[i*groupSize+j] = groupDistances[i*groupSize+k];
- if (groupDistances[i*groupSize+j] < groupDistances[k*groupSize+j])
- groupDistances[i*groupSize+j] = groupDistances[k*groupSize+j];
- }
- }
- }
- }
- int distance = -1;
- if (alternate == 0) {
- // report maximum distance
- for (int i=0; i<groupSize; i++) {
- for (int j=0; j<groupSize; j++) {
- if (groupDistances[i*groupSize+j] > distance) {
- distance = groupDistances[i*groupSize+j];
- }
- }
- }
- } else if (alternate == 1) {
- // report maximum distance
- int distance2 = 0;
- int distance3 = 0;
- int distance4 = 0;
- for (int i=0; i<groupSize; i++) {
- if (position[(*pieceGroups)[i][0]] == '2') {
- for (int j=0; j<groupSize; j++) {
- if (groupDistances[i*groupSize+j] > distance2) {
- distance2 = groupDistances[i*groupSize+j];
- }
- }
- } else if (position[(*pieceGroups)[i][0]] == '3') {
- for (int j=0; j<groupSize; j++) {
- if (groupDistances[i*groupSize+j] > distance3) {
- distance3 = groupDistances[i*groupSize+j];
- }
- }
- } else if (position[(*pieceGroups)[i][0]] == '4') {
- for (int j=0; j<groupSize; j++) {
- if (groupDistances[i*groupSize+j] > distance4) {
- distance4 = groupDistances[i*groupSize+j];
- }
- }
- }
- }
- distance = distance2 + distance3 + distance4;
- }
- return distance + groupSize * groupPenalty;
- }
- static std::string getWalls(std::string puzzle) {
- std::string walls = "";
- for (int i=0; i<256; i++) {
- if (puzzle[i] == '1') {
- walls += '1';
- } else {
- walls += '0';
- }
- }
- return walls;
- }
- // A BUNCH OF WAYS TO SOLVE STUFF
- // solve with iterative deepening
- static void iterativeDeepeningSolve(std::string puzzle) {
- std::string walls = getWalls(puzzle);
- // start search
- std::vector<std::string> noTaboo;
- std::vector<int> distances = getManhattanDistances(walls);
- int depth = 0;
- int foundSolutions = 0;
- clock_t start = clock();
- while (foundSolutions == 0) {
- int solutions = iterativeDeepeningSearch(puzzle, walls, distances, depth, "", noTaboo);
- clock_t t = clock() - start;
- if (solutions > 0) {
- std::cout << "Solutions: " << solutions << " at depth " << depth << " (t = " << t << ")\n";
- foundSolutions = 1;
- } else {
- std::cout << "Depth " << depth << " done (t = " << t << ")\n";
- depth++;
- }
- }
- }
- // position = position, walls = precomputed walls of position,
- // remaining_depth = moves left to search, moves = move string so far
- static int iterativeDeepeningSearch(std::string position, std::string walls, std::vector<int> distances, int remaining_depth, std::string moves, std::vector<std::string> taboo) {
- //std::cout << moves << "\n";
- int solutions = 0;
- // figure out piece groups
- Groups groups = getGroups(position);
- if (looksSolvable(position, groups) == 0) return 0;
- // check for solved if we are out of moves
- if (remaining_depth <= 0) {
- int solved = isSolved(position, groups.pieceGroups);
- if (solved==1) {
- std::cout << "Found solution: " << moves << "\n";
- }
- return solved;
- }
- if (minDistance(position, groups, distances, 0, 0) > remaining_depth) return 0;
- // loop through moves
- std::vector<std::string> newTaboo;
- newTaboo.push_back(position);
- // try U move
- std::string uPosition = applyMove(0, groups, position);
- if (uPosition != position && inTaboo(uPosition, taboo) == 0) solutions += iterativeDeepeningSearch(uPosition, walls, distances, remaining_depth-1, moves+"U", newTaboo);
- // try D move
- std::string dPosition = applyMove(1, groups, position);
- if (dPosition != position && inTaboo(dPosition, taboo) == 0) solutions += iterativeDeepeningSearch(dPosition, walls, distances, remaining_depth-1, moves+"D", newTaboo);
- Groups uGroups = getGroups(uPosition);
- Groups dGroups = getGroups(dPosition);
- // try L move (but no LU/LD if equal to UL/DL)
- std::string lPosition = applyMove(2, groups, position);
- if (lPosition != position && inTaboo(lPosition, taboo) == 0) {
- std::vector<std::string> lTaboo = newTaboo;
- lTaboo.push_back(applyMove(2, uGroups, uPosition));
- lTaboo.push_back(applyMove(2, dGroups, dPosition));
- solutions += iterativeDeepeningSearch(lPosition, walls, distances, remaining_depth-1, moves+"L", lTaboo);
- }
- // try R move (but no RU/RD if equal to UR/DR)
- std::string rPosition = applyMove(3, groups, position);
- if (rPosition != position && inTaboo(rPosition, taboo) == 0) {
- std::vector<std::string> rTaboo = newTaboo;
- rTaboo.push_back(applyMove(3, uGroups, uPosition));
- rTaboo.push_back(applyMove(3, dGroups, dPosition));
- solutions += iterativeDeepeningSearch(rPosition, walls, distances, remaining_depth-1, moves+"R", rTaboo);
- }
- return solutions;
- }
- // solve by enumerating every position in one map
- static void singleMapSolve(std::string puzzle, int goalMoves, int maxStates) {
- std::string walls = getWalls(puzzle);
- // start with empty map (state -> <depth, movestring>)
- std::map<std::vector<byte>, Moves> positions;
- // insert starting state at depth 0, set main_depth = 0
- std::vector<byte> noMoves;
- positions[encode(puzzle)] = (Moves) {0, noMoves};
- int foundSolution = 0;
- int main_depth = 0;
- std::vector<int> distances = getManhattanDistances(walls);
- Groups groups = getGroups(puzzle);
- while (foundSolution == 0) {
- // iterate over map to look for depth == main_depth. for each
- int foundPosition = 0;
- for (std::map<std::vector<byte>, Moves>::iterator it=positions.begin(); it!=positions.end(); ++it) {
- if (it->second.nMoves == main_depth) {
- foundPosition = 1;
- std::string position = decode(it->first, walls);
- Groups groups = getGroups(position);
- if (looksSolvable(position, groups) == 0) continue;
- int solved = isSolved(position, groups.pieceGroups);
- if (solved == 1) {
- foundSolution = 1;
- std::cout << "Found solution: " << printMoves(it->second.moves, main_depth) << "\n";
- break;
- #if MINIMIZE_MATCHES == 1
- } else if (solved == -1) {
- continue;
- #endif
- }
- if ((int) positions.size() > maxStates) {
- continue;
- }
- if (minDistance(position, groups, distances, 0, 0) + main_depth >= goalMoves) {
- continue;
- }
- for (int mov = 0; mov < 4; mov++) {
- std::string newPosition = applyMove(mov, groups, position);
- // add this position into the map if it isn't already there
- if (positions.count(encode(newPosition)) == 0) {
- positions[encode(newPosition)] = (Moves) {it->second.nMoves + 1, addMove(it->second.moves, mov, it->second.nMoves)};
- }
- }
- }
- }
- if (foundPosition == 0) {
- std::cout << "Could not find solution.\n";
- foundSolution = 1;
- }
- main_depth++;
- if (foundSolution == 0) {
- std::cout << "Depth " << main_depth << ", positions " << positions.size() << "\n";
- }
- }
- }
- // solve by enumerating every position with one map per depth
- static void moduloMapSolve(std::string puzzle, int goalMoves, int nMaps, int maxStates) {
- std::string walls = getWalls(puzzle);
- // start with empty maps (state -> <depth, movestring>)
- std::vector<std::map<std::vector<byte>, std::vector<byte> > > positions;
- for (int i=0; i<nMaps; i++) {
- std::map<std::vector<byte>, std::vector<byte> > subPositions;
- positions.push_back(subPositions);
- }
- // insert starting state at depth 0, set main_depth = 0
- std::vector<byte> noMoves;
- positions[0][encode(puzzle)] = noMoves;
- int foundSolution = 0;
- int main_depth = 0;
- std::vector<int> distances = getManhattanDistances(walls);
- Groups groups = getGroups(puzzle);
- while (foundSolution == 0) {
- // get current and next position maps
- std::map<std::vector<byte>, std::vector<byte> > *curPositions = &positions[main_depth % nMaps];
- std::map<std::vector<byte>, std::vector<byte> > *nextPositions = &positions[(main_depth + 1) % nMaps];
- nextPositions->clear();
- int maxPositions = maxStates;
- for (int i=0; i<nMaps; i++) {
- maxPositions -= positions[i].size();
- }
- // iterate over map
- int foundPosition = 0;
- for (std::map<std::vector<byte>, std::vector<byte> >::iterator it=curPositions->begin(); it!=curPositions->end(); ++it) {
- foundPosition = 1;
- std::string position = decode(it->first, walls);
- Groups groups = getGroups(position);
- if (looksSolvable(position, groups) == 0) continue;
- int solved = isSolved(position, groups.pieceGroups);
- if (solved == 1) {
- foundSolution = 1;
- std::cout << "Found solution: " << printMoves(it->second, main_depth) << "\n";
- break;
- #if MINIMIZE_MATCHES == 1
- } else if (solved == -1) {
- continue;
- #endif
- }
- if ((int) nextPositions->size() > maxPositions) {
- continue;
- }
- if (minDistance(position, groups, distances, 0, 0) + main_depth >= goalMoves) {
- continue;
- }
- // loop through moves
- for (int mov = 0; mov < 4; mov++) {
- std::string newPosition = applyMove(mov, groups, position);
- int positionExists = 0;
- std::vector<byte> encoded = encode(newPosition);
- for (int i=0; i<nMaps; i++) {
- if (positions[i].count(encoded) != 0) {
- positionExists = 1;
- break;
- }
- }
- if (positionExists == 0) {
- (*nextPositions)[encoded] = addMove(it->second, mov, main_depth);
- }
- }
- }
- if (foundPosition == 0) {
- std::cout << "Could not find solution.\n";
- foundSolution = 1;
- }
- main_depth++;
- if (foundSolution == 0) {
- std::cout << "Depth " << main_depth << ", positions " << nextPositions->size() << "\n";
- }
- if ((int) nextPositions->size() > maxPositions) {
- break;
- }
- }
- }
- #if USING_SHAPE == 1
- static int allInShape(std::string &position, Groups &groups) {
- std::vector<int> goalShape;
- goalShape = GOAL_SHAPE;
- // want to make sure each group of large-enough size is part of the goal shape
- int groupCount = groups.pieceGroups.size();
- for (int i=0; i<groupCount; i++) {
- std::vector<int> subShape = groups.pieceGroups[i];
- if (position[subShape[0]] COLOR_TEST && subShape.size() >= 2) {
- // is this group part of the goal shape?
- int found = 0;
- for (int ctr = 0; ctr < (int) goalShape.size(); ctr++) {
- int subPtr = 0;
- int goalPtr = ctr;
- while (subPtr < (int)subShape.size() && goalPtr < (int)goalShape.size()) {
- if (subShape[subPtr]-subShape[0] == goalShape[goalPtr]-goalShape[ctr]) {
- subPtr++;
- }
- goalPtr++;
- }
- if (subPtr == (int)subShape.size()) {
- found = 1;
- break;
- }
- }
- if (found == 0) {
- return 0;
- }
- }
- }
- return 1;
- }
- #endif
- static int looksSolvable(std::string &position, Groups &groups) {
- #if USING_SHAPE == 1
- if (allInShape(position, groups) == 0) return 0;
- #endif
- // put any puzzle-specific code here!
- return 1;
- }
- // solve by enumerating almost every position with one map per depth
- // drop states if we need to so we don't have more than maxStatesPer per depth
- static int moduloMapSuboptimalSolve(std::string puzzle, int goalMoves, int nMaps, int maxStatesPer, int penalty) {
- std::string walls = getWalls(puzzle);
- // start with empty maps (state -> <depth, movestring>)
- std::vector<std::map<std::vector<byte>, std::vector<byte> > > positions;
- for (int i=0; i<nMaps; i++) {
- std::map<std::vector<byte>, std::vector<byte> > subPositions;
- positions.push_back(subPositions);
- }
- // insert starting state at depth 0, set main_depth = 0
- std::vector<byte> noMoves;
- positions[0][encode(puzzle)] = noMoves;
- int foundSolution = 0;
- int main_depth = 0;
- std::vector<int> distances = getManhattanDistances(walls);
- Groups groups = getGroups(puzzle);
- while (foundSolution == 0) {
- // get current and next position maps
- std::map<std::vector<byte>, std::vector<byte> > *curPositions = &positions[main_depth % nMaps];
- std::map<std::vector<byte>, std::vector<byte> > *nextPositions = &positions[(main_depth + 1) % nMaps];
- nextPositions->clear();
- std::priority_queue<Queued> queued;
- //int printed = 0;
- // iterate over map
- int foundPosition = 0;
- for (std::map<std::vector<byte>, std::vector<byte> >::iterator it=curPositions->begin(); it!=curPositions->end(); ++it) {
- foundPosition = 1;
- std::string position = decode(it->first, walls);
- Groups groups = getGroups(position);
- if (looksSolvable(position, groups) == 0) continue;
- //if (printed == 0) {
- // printGrid(position);
- // printed = 1;
- //}
- int solved = isSolved(position, groups.pieceGroups);
- if (solved == 1) {
- foundSolution = 1;
- std::cout << "Found suboptimal solution: " << printMoves(it->second, main_depth) << "\n";
- return main_depth;
- #if MINIMIZE_MATCHES == 1
- } else if (solved == -1) {
- continue;
- #endif
- }
- if (minDistance(position, groups, distances, 0, 0) + main_depth >= goalMoves) {
- continue;
- }
- // loop through moves
- for (int mov = 0; mov < 4; mov++) {
- std::string newPosition = applyMove(mov, groups, position);
- int positionExists = 0;
- std::vector<byte> encoded = encode(newPosition);
- for (int i=0; i<nMaps; i++) {
- if (positions[i].count(encoded) != 0) {
- positionExists = 1;
- break;
- }
- }
- if (positionExists == 0) {
- // add to both nextPositions and priority queue
- Groups newGroups = getGroups(newPosition);
- int minDist = minDistance(newPosition, newGroups, distances, penalty, ALTERNATE_HEURISTIC);
- (*nextPositions)[encoded] = addMove(it->second, mov, main_depth);
- queued.push((Queued) {minDist, encoded});
- // but if priority queue is too big, delete one
- if ((int) nextPositions->size() > maxStatesPer) {
- nextPositions->erase(queued.top().key);
- queued.pop();
- }
- }
- }
- }
- if (foundPosition == 0) {
- std::cout << "Could not find solution.\n";
- foundSolution = 1;
- return -1;
- }
- main_depth++;
- if (foundSolution == 0) {
- std::cout << "Depth " << main_depth << ", positions " << nextPositions->size() << "\n";
- }
- //if ((int) nextPositions->size() > maxStatesPer) {
- // break;
- //}
- }
- return -1;
- }
- // solve with iterative deepening
- static void iterativeDeepeningSolve2(std::string puzzle, int goalMoves, int cacheSize) {
- std::string walls = getWalls(puzzle);
- // start search
- std::vector<int> distances = getManhattanDistances(walls);
- int depth = 0;
- int foundSolutions = 0;
- clock_t start = clock();
- while (foundSolutions == 0 && depth <= goalMoves) {
- std::vector<LruCache*> caches;
- for (int i=0; i<=depth; i++) {
- LruCache* l = new LruCache(cacheSize);
- caches.push_back(l);
- }
- int solutions = iterativeDeepeningSearch2(puzzle, walls, distances, depth, "", caches);
- clock_t t = clock() - start;
- if (solutions > 0) {
- std::cout << "Solutions: " << solutions << " at depth " << depth << " (t = " << t << ")\n";
- foundSolutions = 1;
- } else {
- std::cout << "Depth " << depth << " done (t = " << t << ")\n";
- depth++;
- }
- for (std::vector<LruCache*>::iterator it = caches.begin() ; it != caches.end(); ++it)
- {
- delete (*it);
- }
- caches.clear();
- }
- }
- /*
- // single DFS run
- static void iterativeDeepeningSolve2(std::string puzzle, int goalMoves, int cacheSize) {
- std::string walls = getWalls(puzzle);
- // start search
- std::vector<int> distances = getManhattanDistances(walls);
- int depth = goalMoves - 1;
- int foundSolutions = 0;
- clock_t start = clock();
- std::vector<LruCache*> caches;
- for (int i=0; i<=depth; i++) {
- LruCache* l = new LruCache(cacheSize);
- caches.push_back(l);
- }
- int solutions = iterativeDeepeningSearch2(puzzle, walls, distances, depth, "", caches);
- clock_t t = clock() - start;
- if (solutions > 0) {
- std::cout << "Solutions: " << solutions << " at depth " << depth << " (t = " << t << ")\n";
- foundSolutions = 1;
- } else {
- std::cout << "No solutions (t = " << t << ")\n";
- }
- for (std::vector<LruCache*>::iterator it = caches.begin() ; it != caches.end(); ++it)
- {
- delete (*it);
- }
- caches.clear();
- }*/
- // position = position, walls = precomputed walls of position,
- // remaining_depth = moves left to search, moves = move string so far
- static int iterativeDeepeningSearch2(std::string position, std::string walls, std::vector<int> distances, int remaining_depth, std::string moves, std::vector<LruCache*> caches) {
- //std::cout << moves << "\n";
- int solutions = 0;
- // figure out piece groups
- Groups groups = getGroups(position);
- if (looksSolvable(position, groups) == 0) return 0;
- // check for solved if we are out of moves
- if (remaining_depth <= 0) {
- int solved = isSolved(position, groups.pieceGroups);
- if (solved==1) {
- std::cout << "Found solution: " << moves << "\n";
- }
- return solved;
- }
- if (minDistance(position, groups, distances, 0, 0) > remaining_depth) return 0;
- // check if this position is in the cache(s)
- bool cached = false;
- for (int i=remaining_depth; (i<=(remaining_depth + 3) && i<(int)caches.size()); i++) {
- if (caches[i]->contains(position)) {
- cached = true;
- break;
- }
- }
- if (cached) {
- return 0;
- } else {
- caches[remaining_depth]->insert(position);
- }
- // loop through moves UDLR
- std::string newPosition = applyMove(0, groups, position);
- solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+"U", caches);
- newPosition = applyMove(1, groups, position);
- solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+"D", caches);
- newPosition = applyMove(2, groups, position);
- solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+"L", caches);
- newPosition = applyMove(3, groups, position);
- solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+"R", caches);
- /*for (int mov = 0; mov < 4; mov++) {
- std::string newPosition = applyMove(mov, groups, position);
- solutions += iterativeDeepeningSearch2(newPosition, walls, distances, remaining_depth-1, moves+moveName[mov], caches);
- }*/
- return solutions;
- }
- // todo:
- // - build a shape
- static int solve() {
- while (true) {
- // get puzzle
- int goalMoves = 100;
- std::string puzzle;
- std::string totalInput = "";
- while (totalInput.length() < 256) {
- std::string input = "";
- getline(std::cin, input);
- if (input == "") {
- return EXIT_SUCCESS;
- }
- totalInput += input;
- }
- // process puzzle (and possibly a |number)
- puzzle = totalInput.substr(0, 256);
- if (totalInput.length() > 256) {
- goalMoves = 0;
- for (int i=256; i<(int)totalInput.length(); i++) {
- if (totalInput[i] >= '0' && totalInput[i] <= '9') {
- goalMoves = goalMoves*10 + (totalInput[i] - '0');
- }
- }
- }
- // print puzzle
- printGrid(puzzle);
- //iterativeDeepeningSolve(puzzle);
- //iterativeDeepeningSolve2(puzzle, goalMoves, 10000);
- //terminate called after throwing an instance of 'std::bad_alloc'
- // what(): std::bad_alloc
- //moduloMapSolve(puzzle, goalMoves, 4, 10000000);
- std::cout << "(Penalty 5)" << std::endl;
- while (true) {
- int newGoal = moduloMapSuboptimalSolve(puzzle, goalMoves, 100, 10000, 5);
- if (newGoal == -1 || newGoal >= goalMoves) break;
- goalMoves = newGoal;
- std::cout << "Goal changed to " << goalMoves << " moves" << std::endl;
- }
- std::cout << "(Penalty 1)" << std::endl;
- while (true) {
- int newGoal = moduloMapSuboptimalSolve(puzzle, goalMoves, 100, 10000, 1);
- if (newGoal == -1 || newGoal >= goalMoves) break;
- goalMoves = newGoal;
- std::cout << "Goal changed to " << goalMoves << " moves" << std::endl;
- }
- std::cout << "(Penalty 0)" << std::endl;
- while (true) {
- int newGoal = moduloMapSuboptimalSolve(puzzle, goalMoves, 100, 10000, 0);
- if (newGoal == -1 || newGoal >= goalMoves) break;
- goalMoves = newGoal;
- std::cout << "Goal changed to " << goalMoves << " moves" << std::endl;
- }
- }
- return EXIT_SUCCESS;
- }
- };
- int main(int argc, char *argv[]) {
- DenkiSolver::solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement