Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <ctype.h>
- #include <assert.h>
- #define DEBUG 1
- #define MAX_DIM 30 //the biggest possible dimension for a game
- #define MAX_ISLANDS 250 //the most possible islands in a game
- //=========================================================
- #define DB if (DEBUG) printf
- #define VERT_SINGLE '|'
- #define VERT_DOUBLE '\"'
- #define HOR_SINGLE '-'
- #define HOR_DOUBLE '='
- #define NO_DIRECTION 0
- #define UP 1
- #define RIGHT 2
- #define DOWN 3
- #define LEFT 4
- #define CONNECTED 1
- #define NOT_CONNECTED 0
- #define BRIDGE 1
- #define NO_BRIDGE 0
- #define NO_LINK -1
- #define STUPID_BRUTE 1
- #define SMART_BRUTE 2
- #define LOOPY_BRUTE 3
- int max(int a, int b);
- long long int power(int base, int index);
- char* directionName(int direction);
- int oppositeDirection(int direction);
- int findIsland(int x, int y, int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int islands);
- void inputGame(char map[MAX_DIM][MAX_DIM], int *xDim, int *yDim);
- int countIslands(char map[MAX_DIM][MAX_DIM], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int bridgeVal[MAX_ISLANDS], int xDim, int yDim);
- void findLinks(int linkDirections[MAX_ISLANDS][MAX_ISLANDS], char map[MAX_DIM][MAX_DIM], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, int islands, int *links);
- void checkConnections(int connected[MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int island);
- int validSolution(int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS]);
- int addMoreBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]);
- int fillOutBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]);
- void addBridgesToMap(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], char map[MAX_DIM][MAX_DIM], int islands, int linkDirections[MAX_ISLANDS][MAX_ISLANDS]);
- void solvePuzzleLoopyBrute(int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, char map[MAX_DIM][MAX_DIM]);
- void buildOutput(char output[MAX_DIM][MAX_DIM], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, int islands, int bridgeVal[MAX_ISLANDS]);
- void displayOutput(char output[MAX_DIM][MAX_DIM], int xDim, int yDim);
- int main(int argc, char** argv){
- int i=0, j=0;
- int xDim = 0, yDim = 0; //the size of the map
- char map[MAX_DIM][MAX_DIM];
- //The layout of the game, as input
- //
- // 2..2
- // .... xDim = 4, yDim = 3
- // 2..2
- int islands = 0;
- int bridgeVal[MAX_ISLANDS];
- int islandX[MAX_ISLANDS];
- int islandY[MAX_ISLANDS];
- //The grid co-ordinates and numeric value of each island
- //
- // X Y bridgeVal
- // -----
- // 0 |0 0 2
- // 1 |3 0 2 islands = 4
- // 2 |0 2 2
- // 3 |3 2 2
- int links = 0;
- int linkDirections[MAX_ISLANDS][MAX_ISLANDS];
- //The direction of adjacency between two islands. Opposites about the diagonal have opposite directions.
- //
- // 0123
- // ---- 0 = No link
- // 0 |0230 1 = Up
- // 1 |4003 2 = Right
- // 2 |1002 3 = Down
- // 3 |0140 4 = Left
- int bridges[MAX_ISLANDS][MAX_ISLANDS];
- //The answer to the puzzle. 0, 1, 2 indicates the number of bridges between two islands. Symmetrical about the diagonal.
- //
- // 0123
- // ----
- // 0 |0110
- // 1 |1001
- // 2 |1001
- // 3 |0110
- char output[MAX_DIM][MAX_DIM];
- //The program's output.
- //
- // 2--2
- // | |
- // 2--2
- //init
- for (i=0; i<MAX_DIM; i++){
- for (j=0; j<MAX_DIM; j++){
- map[i][j] = 0;
- }
- }
- for (i=0; i<MAX_ISLANDS; i++){
- bridgeVal[i] = 0;
- islandX[i] = 0;
- islandY[i] = 0;
- for (j=0; j<MAX_ISLANDS; j++){
- linkDirections[i][j] = NO_DIRECTION;
- bridges[i][i] = NO_LINK;
- }
- }
- //Read and map out the game
- DB("Inputting game...\n");
- inputGame(map, &xDim, &yDim);
- DB("Counting islands...\n");
- islands = countIslands(map, islandX, islandY, bridgeVal, xDim, yDim);
- DB("Determining adjacencies...\n");
- findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);
- DB("Solving puzzle...\n");
- solvePuzzleLoopyBrute(bridges, islands, bridgeVal, linkDirections, islandX, islandY, xDim, yDim, map);
- DB("Building output...\n");
- buildOutput(output, linkDirections, bridges, islandX, islandY, xDim, yDim, islands, bridgeVal);
- DB("Displaying output...\n");
- displayOutput(output, xDim, yDim);
- return 0;
- }
- int max(int a, int b){
- return (a>b ? a : b);
- }
- long long int power(int base, int index){
- int i = 0;
- long long int answer = 1;
- for (i=0; i<index; i++)
- answer *= base;
- return answer;
- }
- //Should be substantially faster than the above power()
- long long int power3(int index){
- int i = 0;
- long long int answer = 1;
- switch(index){
- case 0: return 1;
- case 1: return 3;
- case 2: return 9;
- case 3: return 27;
- case 4: return 81;
- case 5: return 243;
- case 6: return 729;
- case 7: return 2187;
- case 8: return 6561;
- case 9: return 19683;
- case 10: return 59049;
- case 11: return 177147;
- case 12: return 531441;
- case 13: return 1594323;
- case 14: return 4782969;
- case 15: return 14348907;
- case 16: return 43046721;
- case 17: return 129140163;
- case 18: return 387420489;
- case 19: return 1162261467;
- default:
- for (i=0; i<index; i++)
- answer *= 3;
- return answer;
- }
- }
- char* directionName(int direction){
- switch (direction){
- case UP: return "up";
- case DOWN: return "down";
- case LEFT: return "left";
- case RIGHT: return "right";
- case NO_DIRECTION: return "no direction";
- default: return "invalid direction";
- }
- }
- int oppositeDirection(int direction){
- switch (direction){
- case UP: return DOWN;
- case DOWN: return UP;
- case LEFT: return RIGHT;
- case RIGHT: return LEFT;
- default: return NO_DIRECTION;
- }
- }
- int findIsland(int x, int y, int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int islands){
- int i;
- for (i=0; i<islands; i++)
- if (x == islandX[i] && y == islandY[i])
- return i;
- return -1; //if no island found
- }
- void inputGame(char map[MAX_DIM][MAX_DIM], int *xDim, int *yDim){
- int x = 0, y = 0;
- char c;
- c = getchar();
- while (c != '\n' && c != EOF){
- map[x][y] = c;
- x ++;
- c = getchar();
- if (c == '\n'){
- y ++;
- *yDim = y;
- if (x != 0)
- *xDim = x;
- x = 0;
- c = getchar();
- }
- }
- }
- int countIslands(char map[MAX_DIM][MAX_DIM], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int bridgeVal[MAX_ISLANDS], int xDim, int yDim){
- int i, j;
- int islands = 0;
- DB("Dimensions: %dx%d\n", xDim, yDim);
- for (j=0; j<=yDim; j++){
- for (i=0; i<=xDim; i++){
- if (isdigit(map[i][j])){
- islandX[islands] = i;
- islandY[islands] = j;
- bridgeVal[islands] = (int) (map[i][j] - '0');
- DB("Island %d: x=%d, y=%d. Value = %d.\n", islands, i, j, bridgeVal[islands]);
- islands ++;
- }
- }
- }
- DB("%d islands\n", islands);
- return islands;
- }
- void findLinks(int linkDirections[MAX_ISLANDS][MAX_ISLANDS], char map[MAX_DIM][MAX_DIM], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, int islands, int *links){
- int from = 0, to = 0;
- int x = 0, y = 0;
- int n = 0;
- for (from = 0; from<islands; from ++){
- for (to=0; to<islands; to++){
- linkDirections[from][to] = NO_DIRECTION;
- }
- x = islandX[from];
- y = islandY[from];
- // up
- for (n = y-1; n>=0; n--){
- if (map[x][n] == '~'){ // trying to cross another bridge here. Bad idea.
- n=-1;
- }else if (isdigit(map[x][n])){
- to = findIsland(x, n, islandX, islandY, islands);
- assert (to >= 0); //we know about this island
- //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
- assert (
- linkDirections[from][to] == NO_DIRECTION ||
- linkDirections[from][to] == UP
- );
- linkDirections[from][to] = UP;
- linkDirections[to][from] = DOWN;
- bridges[from][to] = 0; //bridges are allowed here
- bridges[to][from] = 0;
- n = 0;
- //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
- (*links) ++;
- }
- }
- // down
- for (n = y+1; n<=yDim; n++){
- if (map[x][n] == '~'){ // trying to cross another bridge here. Bad idea.
- n=yDim+1;
- }else if (isdigit(map[x][n])){
- to = findIsland(x, n, islandX, islandY, islands);
- assert (to >= 0); //we know about this island
- //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
- assert (
- linkDirections[from][to] == NO_DIRECTION ||
- linkDirections[from][to] == DOWN
- );
- linkDirections[from][to] = DOWN;
- linkDirections[to][from] = UP;
- bridges[from][to] = 0; //bridges are allowed here
- bridges[to][from] = 0;
- n = yDim;
- //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
- (*links) ++;
- }
- }
- // left
- for (n = x-1; n>=0; n--){
- if (map[n][y] == 's'){ // trying to cross another bridge here. Bad idea.
- n=-1;
- }else if (isdigit(map[n][y])){
- to = findIsland(n, y, islandX, islandY, islands);
- assert (to >= 0); //we know about this island
- //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
- assert (
- linkDirections[from][to] == NO_DIRECTION ||
- linkDirections[from][to] == LEFT
- );
- linkDirections[from][to] = LEFT;
- linkDirections[to][from] = RIGHT;
- bridges[from][to] = 0; //bridges are allowed here
- bridges[to][from] = 0;
- n = 0;
- //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
- (*links) ++;
- }
- }
- // RIGHT
- for (n = x+1; n<=xDim; n++){
- if (map[n][y] == 's'){ // trying to cross another bridge here. Bad idea.
- n=xDim+1;
- }else if (isdigit(map[n][y])){
- to = findIsland(n, y, islandX, islandY, islands);
- assert (to >= 0); //we know about this island
- //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
- assert (
- linkDirections[from][to] == NO_DIRECTION ||
- linkDirections[from][to] == RIGHT
- );
- linkDirections[from][to] = RIGHT;
- linkDirections[to][from] = LEFT;
- bridges[from][to] = 0; //bridges are allowed here
- bridges[to][from] = 0;
- n = xDim;
- //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
- (*links) ++;
- }
- }
- }
- (*links) /= 2;
- DB("%d possible links.\n", *links);
- }
- void checkConnections(int connected[MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int island){
- DB("Checking connections from island %d\n", island);
- int i = 0;
- connected[island] = CONNECTED;
- for (i=0; i<islands; i++){
- if (bridges[island][i] > 0){
- if (connected[i] == NOT_CONNECTED){
- checkConnections(connected, bridges, islands, i);
- }
- }
- }
- }
- int validSolution(int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS]){
- int i=0, j=0;
- int n=0;
- int islandBridge[islands]; //the number of bridges connected to each island
- int connected[MAX_ISLANDS]; //whether each island is connected to island 0
- int bridgeMap[MAX_DIM][MAX_DIM];
- for (i=0; i<MAX_DIM; i++){
- for (j=0; j<MAX_DIM; j++){
- bridgeMap[i][j] = NO_BRIDGE;
- }
- }
- //the total number of bridges connected to each island must be equal to the number on the island
- for (i=0; i<islands; i++){
- islandBridge[i] = 0; //init
- connected[i] = NOT_CONNECTED;
- for (j=0; j<islands; j++){
- if (bridges[i][j] != NO_LINK){
- islandBridge[i] += bridges[i][j];
- //DB("{%d->%d = %d} ", i, j, bridges[i][j]);
- }
- }
- if (islandBridge[i] != bridgeVal[i]){
- return 0;
- }
- }
- //all the islands must be connected to each other
- checkConnections(connected, bridges, islands, 0);
- for (i=0; i<islands; i++){
- if (connected[i] == NOT_CONNECTED){
- DB("All nodes are not connected. This is not a solution.\n");
- return 0;
- }
- }
- //bridges are not allowed to cross each other
- for (i=0; i<islands; i++){
- for (j=0; j<islands; j++){
- switch (linkDirections[i][j]){
- case UP:
- assert (islandX[i] == islandX[j]);
- for (n=islandY[i]-1; n > islandY[j]; n--)
- if (bridgeMap[i][j] == BRIDGE)
- return 0;
- bridgeMap[i][j] = BRIDGE;
- break;
- case DOWN:
- assert (islandX[i] == islandX[j]);
- for (n=islandY[i]+1; n < islandY[j]; n++)
- if (bridgeMap[i][j] == BRIDGE)
- return 0;
- bridgeMap[i][j] = BRIDGE;
- break;
- case LEFT:
- assert (islandY[i] == islandY[j]);
- for (n=islandX[i]-1; n > islandX[j]; n--)
- if (bridgeMap[i][j] == BRIDGE)
- return 0;
- bridgeMap[i][j] = BRIDGE;
- break;
- case RIGHT:
- assert (islandY[i] == islandY[j]);
- for (n=islandX[i]+1; n < islandX[j]; n++)
- if (bridgeMap[i][j] == BRIDGE)
- return 0;
- bridgeMap[i][j] = BRIDGE;
- break;
- default:;
- }
- }
- }
- DB("Solution\n");
- return 1;
- }
- int addMoreBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]){
- int bridgesAdded = 0;
- int i=0, j=0;
- int linkCounter = 0;
- int newBridgeVal[islands];
- int newPreparedBridges[islands][islands];
- for (i=0; i<islands; i++){
- newBridgeVal[i] = bridgeVal[i];
- for (j=0; j<islands; j++){
- newPreparedBridges[i][j] = 0;
- }
- }
- //newBridgeVal = bridgeVal - bridges in the original preparedBridges
- for (i=0; i<islands; i++){
- newBridgeVal[i] = bridgeVal[i];
- for (j=0; j<islands; j++){
- assert(preparedBridges[i][j] == preparedBridges[j][i]);
- newBridgeVal[i] -= preparedBridges[i][j];
- assert(newBridgeVal[i] >= 0);
- }
- //DB("BridgeVal: %d --> %d\n", bridgeVal[i], newBridgeVal[i]);
- }
- for (i=0; i<islands; i++){
- if (newBridgeVal[i] > 0){
- //assemble linkCounter, skipping full islands
- linkCounter = 0;
- for (j=0; j<islands; j++){
- if ((linkDirections[i][j] != NO_DIRECTION) && (newBridgeVal[j] > 0)){
- linkCounter++;
- }
- }
- }
- //addMandatoryBridges algorithm, but using newBridgeVal, and adding bridges only to islands that aren't full.
- DB("Island %d: linkCounter = %d, newBridgeVal = %d", i, linkCounter, newBridgeVal[i]);
- if (linkCounter > 0 && linkCounter == (newBridgeVal[i] + 1) / 2){
- DB(" - more mandatory bridges here");
- for (j=0; j<islands; j++){
- if (newBridgeVal[j] > 0){
- if (linkDirections[i][j] != NO_DIRECTION){
- newPreparedBridges[i][j] = (newBridgeVal[i] / linkCounter);
- bridgesAdded ++;
- }
- }
- }
- }
- DB("\n");
- }
- DB("\n");
- for (i=0; i<islands; i++){
- for (j=0; j<islands; j++){
- newPreparedBridges[i][j] = newPreparedBridges[j][i] = max(newPreparedBridges[i][j], newPreparedBridges[j][i]);
- assert(newPreparedBridges[i][j] == newPreparedBridges[j][i]);
- if (newPreparedBridges[i][j] > 0){
- DB("Prepared bridge: %d%c%d\n", i,newPreparedBridges[i][j] == 1 ? HOR_SINGLE : HOR_DOUBLE, j);
- assert(linkDirections[i][j] != NO_DIRECTION);
- }
- preparedBridges[i][j] += newPreparedBridges[i][j];
- }
- }
- DB("%d extra bridges added this time\n", bridgesAdded);
- return bridgesAdded;
- }
- int fillOutBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]){
- int bridgesAdded = 0;
- int i=0, j=0;
- int n=0;
- int newBridgeVal[islands];
- int linkCounter[islands];
- int bridgeRoom[islands]; //room for more bridges
- int newPreparedBridges[islands][islands];
- for (i=0; i<islands; i++){
- newBridgeVal[i] = 0;
- bridgeRoom[i] = 0;
- for (j=0; j<islands; j++){
- linkCounter[i] = 0;
- newPreparedBridges[i][j] = 0;
- }
- }
- //newBridgeVal = bridgeVal - bridges in the original preparedBridges
- DB("%d islands\n", islands);
- for (i=0; i<islands; i++){
- newBridgeVal[i] = bridgeVal[i];
- if (newBridgeVal[i] > 0){
- DB("Island %d, bridgeVal = %d", i, bridgeVal[i]);
- for (j=0; j<islands; j++){
- assert(preparedBridges[i][j] == preparedBridges[j][i]);
- if (preparedBridges[i][j] > 0) DB(" -%d", preparedBridges[i][j]);
- assert(preparedBridges[i][j] <= newBridgeVal[i]);
- //DB("BridgeVal[%d} change: %d - %d = ", i, newBridgeVal[i], preparedBridges[i][j]);
- newBridgeVal[i] -= preparedBridges[i][j];
- //DB("%d\n", newBridgeVal[i]);
- assert(newBridgeVal[i] >= 0);
- }
- DB("\n");
- }
- assert(newBridgeVal[i] >= 0);
- DB("BridgeVal[%d]: %d --> %d\n", i, bridgeVal[i], newBridgeVal[i]);
- }
- for (i=0; i<islands; i++){
- if (newBridgeVal[i] > 0){
- //assemble linkCounter, skipping full islands
- linkCounter[i] = 0;
- for (j=0; j<islands; j++){
- if ((linkDirections[i][j] != NO_DIRECTION) && (newBridgeVal[j] > 0)){
- linkCounter[i] ++;
- bridgeRoom[i] += newBridgeVal[j];
- }
- }
- }
- }
- //fill out bridges
- for (i=0; i<islands; i++){
- if (newBridgeVal[i] > 0 && newBridgeVal[i] == bridgeRoom[i]){ //all possible bridges can be filled
- DB("Added %d bridges\n", bridgeRoom[i]);
- for (j=0; j<islands; j++){
- if (linkDirections[i][j] != NO_LINK){
- n = newBridgeVal[j];
- newPreparedBridges[i][j] += n;
- newPreparedBridges[j][i] += n;
- newBridgeVal[i] -= n;
- newBridgeVal[j] -= n;
- bridgesAdded ++;
- }
- }
- //assert(newBridgeVal[i] == 0);
- }
- }
- for (i=0; i<islands; i++){
- for (j=0; j<islands; j++){
- newPreparedBridges[i][j] = newPreparedBridges[j][i] = max(newPreparedBridges[i][j], newPreparedBridges[j][i]);
- assert(newPreparedBridges[i][j] == newPreparedBridges[j][i]);
- if (newPreparedBridges[i][j] > 0) DB("Prepared bridge: %d%c%d\n", i,newPreparedBridges[i][j] == 1 ? HOR_SINGLE : HOR_DOUBLE, j);
- if (newPreparedBridges[i][j]>0) DB("Prepared bridges[%d][%d]: %d-->%d\n", i, j, preparedBridges[i][j], preparedBridges[i][j] + newPreparedBridges[i][j]);
- preparedBridges[i][j] += newPreparedBridges[i][j];
- }
- }
- return bridgesAdded;
- }
- void addBridgesToMap(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], char map[MAX_DIM][MAX_DIM], int islands, int linkDirections[MAX_ISLANDS][MAX_ISLANDS]){
- int i=0, j=0;
- int bridgeVal[islands];
- int x=0, y=0;
- int reached = 0;
- for (i=0; i<islands; i++){
- bridgeVal[i] = 0;
- for (j=0; j<islands; j++){
- if (preparedBridges[i][j] > 0 && linkDirections[i][j] != NO_DIRECTION){
- DB("%d,%d(island %d) --> %d,%d(island %d) %s (%d)\n", islandX[i], islandY[i], i, islandX[j], islandY[j], j, directionName(linkDirections[i][j]), linkDirections[i][j]);
- bridgeVal[i] += preparedBridges[i][j];
- reached = 0;
- x=islandX[i];
- y=islandY[i];
- while (!reached){
- switch (linkDirections[i][j]){
- case UP:
- y --;
- reached = (y == islandY[j]);
- break;
- case DOWN:
- y ++;
- reached = (y == islandY[j]);
- break;
- case LEFT:
- x --;
- reached = (x == islandX[j]);
- break;
- case RIGHT:
- x ++;
- reached = (x == islandX[j]);
- break;
- default:
- DB("attempting to blacklist bridge with no direction\n");
- ;
- }
- if (x != islandX[j] || y != islandY[j]){
- map[x][y] = ((linkDirections[i][j] == LEFT || linkDirections[i][j] == RIGHT) ? '~' : 's'); //bridge part here; no crossing
- }
- }
- }
- }
- map[islandX[i]][islandY[i]] = bridgeVal[i]+'0'; //for debugging purposes
- }
- }
- void solvePuzzleLoopyBrute(int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, char map[MAX_DIM][MAX_DIM]){
- //brief algorithm:
- //performs initial bridgework of Smart Brute, then repeats the process in a modular way to further cut down required permutations.
- int links = 0;
- int solutionFound = 0;
- int potential[3][islands*2];
- int i=0, j=0, k=0;
- int potentials = 0;
- int listed = 0;
- long long int bruteCap = 0;
- long long int bruteLoop = 0;
- int preparedBridges[MAX_ISLANDS][MAX_ISLANDS];
- int newBridgeVal[islands];
- int permutationNoGood = 0; //flags the current permutation as bad
- //init
- for (i=0; i<islands; i++){
- for (j=0; j<islands; j++){
- preparedBridges[i][j] = 0;
- }
- }
- for (i=0; i<=2; i++){
- for (j=0; j<islands*2; j++){
- potential[i][j] = 0;
- }
- }
- //Add bridges until no more can be added automatically
- while (addMoreBridges(preparedBridges, islands, bridgeVal, linkDirections) > 0){
- DB("Bridges added\n");
- addBridgesToMap(preparedBridges, islandX, islandY, map, islands, linkDirections);
- findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);
- for (i=0; i<=xDim; i++){
- for (j=0; j<=yDim; j++){
- DB("%c", map[j][i]);
- }
- DB("\n");
- }
- }
- while (fillOutBridges(preparedBridges, islands, bridgeVal, linkDirections) > 0){
- DB("Bridges filled out\n");
- addBridgesToMap(preparedBridges, islandX, islandY, map, islands, linkDirections);
- findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);
- }
- for (i=0; i<xDim; i++){
- for (j=0; j<yDim; j++){
- DB("%c", map[j][i]);
- }
- DB("\n");
- }
- //newBridgeVal = bridgeVal - bridges in the original preparedBridges
- for (i=0; i<islands; i++){
- newBridgeVal[i] = bridgeVal[i];
- for (j=0; j<islands; j++){
- assert(preparedBridges[i][j] == preparedBridges[j][i]);
- newBridgeVal[i] -= preparedBridges[i][j];
- }
- assert(newBridgeVal[i] >= 0);
- DB("Bridge val[%d] after prepared bridges = %d\n", i, newBridgeVal[i]);
- }
- //assemble list of potential bridges
- for (i=0; i<islands; i++){
- if (newBridgeVal[i] > 0){
- for (j=0; j<islands; j++){
- if (newBridgeVal[j] > 0){
- if (preparedBridges[i][j] == 2){ //if a bridge of 2 already exists, there's no point in including this in the permutations
- //bridges[i][j] = bridges[j][i] = 2;
- DB("=== bridge already included\n");
- }else{
- if (linkDirections[i][j] != NO_DIRECTION){
- //make sure this isn't already on the list
- listed = 0;
- for (k=0; k<potentials; k++){
- if (potential[0][k] == j && potential[1][k] == i){
- listed = 1;
- k = potentials;
- }
- }
- if (!listed){
- potential[0][potentials] = i;
- potential[1][potentials] = j;
- potential[2][potentials] = preparedBridges[i][j];
- potentials ++;
- }
- }
- }
- }
- }
- }
- }
- for (i=0; i<islands; i++){
- for (j=0; j<islands; j++){
- bridges[i][j] = bridges[j][i] = preparedBridges[i][j]; //permutations will overwrite what they need to
- }
- }
- DB("%d potential bridge locations:\n", potentials);
- for (i=0; i<potentials; i++){
- DB("Island %d (%d bridges) to island %d (%d bridges)\n", potential[0][i], newBridgeVal[potential[0][i]], potential[1][i], newBridgeVal[potential[1][i]]);
- }
- //the variable "potentials" is the number of triplets we need to loop through.
- bruteCap = power3(potentials);
- DB("we're counting up to the number %Ld = 3^%d-1\n", bruteCap-1, potentials);
- //assert(0);
- for (bruteLoop=0; bruteLoop<bruteCap; bruteLoop++){
- DB("%20Ld %f%% |", bruteLoop, (100.0*bruteLoop/(bruteCap-1)));
- permutationNoGood = 0;
- for (i=0; i<potentials; i++){
- //DB ("(%Ld - %Ld) / %Ld\n", bruteLoop % power(3, i+1), bruteLoop % power(3, i), power(3, i));
- bridges[potential[0][i]][potential[1][i]] = ((bruteLoop % power3(i+1)) - (bruteLoop % power3(i))) / power3(i);
- DB("%c", bridges[potential[0][i]][potential[1][i]]+'0');
- if (bridges[potential[0][i]][potential[1][i]] < potential[2][i]){
- //printf("* - bad bridge at potential #%d", i);
- DB("\n");
- i=potentials; //exit loop
- permutationNoGood = 1;
- }else{
- bridges[potential[1][i]][potential[0][i]] = bridges[potential[0][i]][potential[1][i]];
- }
- }
- if (bruteLoop % 1000000 == 0) printf("\n%20LdM %f%%", bruteLoop/1000000, (100.0*bruteLoop/bruteCap));
- if (!permutationNoGood){
- DB("|\n");
- //check for solution
- if (validSolution(bridges, islands, bridgeVal, linkDirections, islandX, islandY)){
- bruteLoop = bruteCap;
- solutionFound = 1;
- }
- }
- }
- DB("\n");
- if (!solutionFound) printf("***No solution found***\n");
- printf("\n");
- }
- void buildOutput(char output[MAX_DIM][MAX_DIM], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int xDim, int yDim, int islands, int bridgeVal[MAX_ISLANDS]){
- int i = 0, j = 0;
- int from = 0, to = 0;
- int n = 0;
- int direction = NO_DIRECTION;
- char bridgeChar = 0;
- for (i=0; i<xDim; i++)
- for (j=0; j<=yDim; j++)
- output[i][j] = ' ';
- for (i=0; i<islands; i++)
- output[islandX[i]][islandY[i]] = bridgeVal[i] + '0'; //draw islands
- for (from=0; from<islands; from++){
- for (to=0; to<islands; to++){
- if (bridges[from][to] > 0){
- direction = linkDirections[from][to];
- if (direction == UP || direction == DOWN){
- bridgeChar = (bridges[from][to] == 1 ? VERT_SINGLE : VERT_DOUBLE);
- }else{
- assert(direction == LEFT || direction == RIGHT);
- bridgeChar = (bridges[from][to] == 1 ? HOR_SINGLE : HOR_DOUBLE);
- }
- switch (direction){
- case UP:
- assert (islandX[from] == islandX[to]);
- for (n=islandY[from]-1; n > islandY[to]; n--)
- output[islandX[from]][n] = bridgeChar;
- break;
- case DOWN:
- assert (islandX[from] == islandX[to]);
- for (n=islandY[from]+1; n < islandY[to]; n++)
- output[islandX[from]][n] = bridgeChar;
- break;
- case LEFT:
- assert (islandY[from] == islandY[to]);
- for (n=islandX[from]-1; n > islandX[to]; n--)
- output[n][islandY[from]] = bridgeChar;
- break;
- case RIGHT:
- assert (islandY[from] == islandY[to]);
- for (n=islandX[from]+1; n < islandX[to]; n++)
- output[n][islandY[from]] = bridgeChar;
- break;
- default:;
- }
- }
- }
- }
- }
- void displayOutput(char output[MAX_DIM][MAX_DIM], int xDim, int yDim){
- int i, j;
- for (j=0; j<=yDim; j++){
- for (i=0; i<xDim; i++){
- putchar(output[i][j]);
- }
- putchar('\n');
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement