View difference between Paste ID: kXm3KLvB and HRHi4698

 /*
- Optimal Denki Blocks solver
+ (Sub)Optimal Denki Blocks solver
- Copyright (C) 2014 Michael Gottlieb
+ 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;
-	static int minDistance(std::string &position, Groups &groups, std::vector<int> &distances, int groupPenalty) {
+#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;
-		// report maximum distance
+
 			return 0;
 		}
 	}
-				if (groupDistances[i*groupSize+j] > distance) {
+
-					distance = groupDistances[i*groupSize+j];
+
 		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) {
-		if (minDistance(position, groups, distances, 0) > remaining_depth) return 0;
+
 		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') {
-					if (isSolved(position, groups.pieceGroups) == 1) {
+					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];
 						}
-					if (minDistance(position, groups, distances, 0) + main_depth >= goalMoves) {
+
 				}
 			}
 			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;
 
-				if (isSolved(position, groups.pieceGroups) == 1) {
+
 		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 (minDistance(position, groups, distances, 0) + main_depth >= goalMoves) {
+
 
 		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;
-	// TEMPORARY - FOR SOLVING GIVEN PUZZLE
+
 
 		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";
-				if (isSolved(position, groups.pieceGroups) == 1) {
+
 		}
 	}
 
 	// solve by enumerating every position with one map per depth
 	static void moduloMapSolve(std::string puzzle, int goalMoves, int nMaps, int maxStates) {
-				if (minDistance(position, groups, distances, 0) + main_depth >= goalMoves) {
+
 
 		// 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);
 
-						int minDist = minDistance(newPosition, newGroups, distances, penalty);
+
 			// 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;
 	}
-		if (minDistance(position, groups, distances, 0) > remaining_depth) return 0;
+
 
 
 	// 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});
-				int newGoal = moduloMapSuboptimalSolve(puzzle, goalMoves, 10, 10000, 5);
+
 						// but if priority queue is too big, delete one
 						if ((int) nextPositions->size() > maxStatesPer) {
 							nextPositions->erase(queued.top().key);
 							queued.pop();
 						}
 					}
-				int newGoal = moduloMapSuboptimalSolve(puzzle, goalMoves, 10, 10000, 1);
+
 			}
 
 			if (foundPosition == 0) {
 				std::cout << "Could not find solution.\n";
 				foundSolution = 1;
 				return -1;
-				int newGoal = moduloMapSuboptimalSolve(puzzle, goalMoves, 10, 10000, 0);
+
 
 			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();
 }