daily pastebin goal
58%
SHARE
TWEET

Bridges

Archon Dec 7th, 2010 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <ctype.h>
  3. #include <assert.h>
  4.  
  5. #define DEBUG 1
  6.  
  7. #define MAX_DIM 30 //the biggest possible dimension for a game
  8. #define MAX_ISLANDS 250  //the most possible islands in a game
  9.  
  10. //=========================================================
  11.  
  12. #define DB if (DEBUG) printf
  13.  
  14. #define VERT_SINGLE '|'
  15. #define VERT_DOUBLE '\"'
  16. #define HOR_SINGLE '-'
  17. #define HOR_DOUBLE '='
  18.  
  19. #define NO_DIRECTION 0
  20. #define UP 1
  21. #define RIGHT 2
  22. #define DOWN 3
  23. #define LEFT 4
  24.  
  25. #define CONNECTED 1
  26. #define NOT_CONNECTED 0
  27.  
  28. #define BRIDGE 1
  29. #define NO_BRIDGE 0
  30.  
  31. #define NO_LINK -1
  32.  
  33. #define STUPID_BRUTE 1
  34. #define SMART_BRUTE 2
  35. #define LOOPY_BRUTE 3
  36.  
  37. int max(int a, int b);
  38. long long int power(int base, int index);
  39. char* directionName(int direction);
  40. int oppositeDirection(int direction);
  41. int findIsland(int x, int y, int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int islands);
  42. void inputGame(char map[MAX_DIM][MAX_DIM], int *xDim, int *yDim);
  43. int countIslands(char map[MAX_DIM][MAX_DIM], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int bridgeVal[MAX_ISLANDS], int xDim, int yDim);
  44. 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);
  45. void checkConnections(int connected[MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int island);
  46. 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]);
  47. int addMoreBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]);
  48. int fillOutBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]);
  49. 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]);
  50. 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]);
  51. 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]);
  52. void displayOutput(char output[MAX_DIM][MAX_DIM], int xDim, int yDim);
  53.  
  54. int main(int argc, char** argv){
  55.    
  56.    int i=0, j=0;
  57.    
  58.    int xDim = 0, yDim = 0; //the size of the map
  59.    char map[MAX_DIM][MAX_DIM];
  60.    //The layout of the game, as input
  61.    //
  62.    // 2..2
  63.    // ....  xDim = 4, yDim = 3
  64.    // 2..2
  65.  
  66.    int islands = 0;
  67.    int bridgeVal[MAX_ISLANDS];
  68.    int islandX[MAX_ISLANDS];
  69.    int islandY[MAX_ISLANDS];
  70.    //The grid co-ordinates and numeric value of each island
  71.    //
  72.    //    X Y bridgeVal
  73.    //    -----
  74.    // 0 |0 0 2
  75.    // 1 |3 0 2   islands = 4
  76.    // 2 |0 2 2
  77.    // 3 |3 2 2
  78.    
  79.    int links = 0;
  80.    int linkDirections[MAX_ISLANDS][MAX_ISLANDS];
  81.    //The direction of adjacency between two islands.  Opposites about the diagonal have opposite directions.
  82.    //
  83.    //    0123
  84.    //    ----  0 = No link
  85.    // 0 |0230  1 = Up
  86.    // 1 |4003  2 = Right
  87.    // 2 |1002  3 = Down
  88.    // 3 |0140  4 = Left
  89.    
  90.    int bridges[MAX_ISLANDS][MAX_ISLANDS];
  91.    //The answer to the puzzle.  0, 1, 2 indicates the number of bridges between two islands.  Symmetrical about the diagonal.
  92.    //
  93.    //    0123
  94.    //    ----
  95.    // 0 |0110
  96.    // 1 |1001
  97.    // 2 |1001
  98.    // 3 |0110
  99.    
  100.    char output[MAX_DIM][MAX_DIM];
  101.    //The program's output.
  102.    //
  103.    // 2--2
  104.    // |  |
  105.    // 2--2
  106.    
  107.    //init
  108.    for (i=0; i<MAX_DIM; i++){
  109.       for (j=0; j<MAX_DIM; j++){
  110.          map[i][j] = 0;
  111.       }
  112.    }
  113.    for (i=0; i<MAX_ISLANDS; i++){
  114.       bridgeVal[i] = 0;
  115.       islandX[i] = 0;
  116.       islandY[i] = 0;
  117.       for (j=0; j<MAX_ISLANDS; j++){
  118.          linkDirections[i][j] = NO_DIRECTION;
  119.          bridges[i][i] = NO_LINK;
  120.       }
  121.    }
  122.    
  123.    //Read and map out the game
  124.    DB("Inputting game...\n");
  125.    inputGame(map, &xDim, &yDim);
  126.    
  127.    DB("Counting islands...\n");
  128.    islands = countIslands(map, islandX, islandY, bridgeVal, xDim, yDim);
  129.    
  130.    DB("Determining adjacencies...\n");
  131.    findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);
  132.    
  133.    DB("Solving puzzle...\n");
  134.    solvePuzzleLoopyBrute(bridges, islands, bridgeVal, linkDirections, islandX, islandY, xDim, yDim, map);
  135.    
  136.    DB("Building output...\n");
  137.    buildOutput(output, linkDirections, bridges, islandX, islandY, xDim, yDim, islands, bridgeVal);
  138.    
  139.    DB("Displaying output...\n");
  140.    displayOutput(output, xDim, yDim);
  141.  
  142.    return 0;
  143. }
  144.  
  145. int max(int a, int b){
  146.    return (a>b ? a : b);
  147. }
  148.  
  149. long long int power(int base, int index){
  150.    int i = 0;
  151.    long long int answer = 1;
  152.    for (i=0; i<index; i++)
  153.       answer *= base;
  154.    return answer;
  155. }
  156.  
  157. //Should be substantially faster than the above power()
  158. long long int power3(int index){
  159.    int i = 0;
  160.    long long int answer = 1;
  161.    switch(index){
  162.    case  0: return 1;
  163.    case  1: return 3;
  164.    case  2: return 9;
  165.    case  3: return 27;
  166.    case  4: return 81;
  167.    case  5: return 243;
  168.    case  6: return 729;
  169.    case  7: return 2187;
  170.    case  8: return 6561;
  171.    case  9: return 19683;
  172.    case 10: return 59049;
  173.    case 11: return 177147;
  174.    case 12: return 531441;
  175.    case 13: return 1594323;
  176.    case 14: return 4782969;
  177.    case 15: return 14348907;
  178.    case 16: return 43046721;
  179.    case 17: return 129140163;
  180.    case 18: return 387420489;
  181.    case 19: return 1162261467;
  182.    default:
  183.       for (i=0; i<index; i++)
  184.          answer *= 3;
  185.       return answer;
  186.    }
  187. }
  188.  
  189. char* directionName(int direction){
  190.    switch (direction){
  191.    case UP: return "up";
  192.    case DOWN: return "down";
  193.    case LEFT: return "left";
  194.    case RIGHT: return "right";
  195.    case NO_DIRECTION: return "no direction";
  196.    default: return "invalid direction";
  197.    }
  198. }
  199.  
  200. int oppositeDirection(int direction){
  201.    switch (direction){
  202.    case UP: return DOWN;
  203.    case DOWN: return UP;
  204.    case LEFT: return RIGHT;
  205.    case RIGHT: return LEFT;
  206.    default: return NO_DIRECTION;
  207.    }
  208. }
  209.  
  210. int findIsland(int x, int y, int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int islands){
  211.    int i;
  212.    for (i=0; i<islands; i++)
  213.       if (x == islandX[i] && y == islandY[i])
  214.          return i;
  215.    return -1; //if no island found
  216. }
  217.  
  218. void inputGame(char map[MAX_DIM][MAX_DIM], int *xDim, int *yDim){
  219.    int x = 0, y = 0;
  220.    char c;
  221.    c = getchar();
  222.    while (c != '\n' && c != EOF){
  223.       map[x][y] = c;
  224.       x ++;
  225.       c = getchar();
  226.       if (c == '\n'){
  227.          y ++;
  228.          *yDim = y;
  229.          if (x != 0)
  230.             *xDim = x;
  231.          x = 0;
  232.          c = getchar();
  233.       }
  234.    }
  235. }
  236.  
  237. int countIslands(char map[MAX_DIM][MAX_DIM], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int bridgeVal[MAX_ISLANDS], int xDim, int yDim){
  238.    int i, j;
  239.    int islands = 0;
  240.    DB("Dimensions: %dx%d\n", xDim, yDim);
  241.    for (j=0; j<=yDim; j++){
  242.       for (i=0; i<=xDim; i++){
  243.          if (isdigit(map[i][j])){
  244.             islandX[islands] = i;
  245.             islandY[islands] = j;
  246.             bridgeVal[islands] = (int) (map[i][j] - '0');
  247.             DB("Island %d: x=%d, y=%d.  Value = %d.\n", islands, i, j, bridgeVal[islands]);
  248.             islands ++;
  249.          }
  250.       }
  251.    }
  252.    DB("%d islands\n", islands);
  253.    return islands;
  254. }
  255.  
  256. 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){
  257.    int from = 0, to = 0;
  258.    int x = 0, y = 0;
  259.    int n = 0;
  260.    
  261.    for (from = 0; from<islands; from ++){
  262.       for (to=0; to<islands; to++){
  263.          linkDirections[from][to] = NO_DIRECTION;
  264.       }
  265.       x = islandX[from];
  266.       y = islandY[from];
  267.      
  268.       // up
  269.       for (n = y-1; n>=0; n--){
  270.          if (map[x][n] == '~'){ // trying to cross another bridge here.  Bad idea.
  271.             n=-1;
  272.          }else if (isdigit(map[x][n])){
  273.             to = findIsland(x, n, islandX, islandY, islands);
  274.             assert (to >= 0); //we know about this island
  275.             //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  276.             assert (
  277.                linkDirections[from][to] == NO_DIRECTION ||
  278.                linkDirections[from][to] == UP
  279.             );
  280.             linkDirections[from][to] = UP;
  281.             linkDirections[to][from] = DOWN;
  282.             bridges[from][to] = 0; //bridges are allowed here
  283.             bridges[to][from] = 0;
  284.             n = 0;
  285.             //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  286.             (*links) ++;
  287.          }
  288.       }
  289.       // down
  290.       for (n = y+1; n<=yDim; n++){
  291.          if (map[x][n] == '~'){ // trying to cross another bridge here.  Bad idea.
  292.             n=yDim+1;
  293.          }else if (isdigit(map[x][n])){
  294.             to = findIsland(x, n, islandX, islandY, islands);
  295.             assert (to >= 0); //we know about this island
  296.             //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  297.             assert (
  298.                linkDirections[from][to] == NO_DIRECTION ||
  299.                linkDirections[from][to] == DOWN
  300.             );
  301.             linkDirections[from][to] = DOWN;
  302.             linkDirections[to][from] = UP;
  303.             bridges[from][to] = 0; //bridges are allowed here
  304.             bridges[to][from] = 0;
  305.             n = yDim;
  306.             //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  307.             (*links) ++;
  308.          }
  309.       }
  310.       // left
  311.       for (n = x-1; n>=0; n--){
  312.          if (map[n][y] == 's'){ // trying to cross another bridge here.  Bad idea.
  313.             n=-1;
  314.          }else if (isdigit(map[n][y])){
  315.             to = findIsland(n, y, islandX, islandY, islands);
  316.             assert (to >= 0); //we know about this island
  317.             //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  318.             assert (
  319.                linkDirections[from][to] == NO_DIRECTION ||
  320.                linkDirections[from][to] == LEFT
  321.             );
  322.             linkDirections[from][to] = LEFT;
  323.             linkDirections[to][from] = RIGHT;
  324.             bridges[from][to] = 0; //bridges are allowed here
  325.             bridges[to][from] = 0;
  326.             n = 0;
  327.             //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  328.             (*links) ++;
  329.          }
  330.       }
  331.       // RIGHT
  332.       for (n = x+1; n<=xDim; n++){
  333.          if (map[n][y] == 's'){ // trying to cross another bridge here.  Bad idea.
  334.             n=xDim+1;
  335.          }else if (isdigit(map[n][y])){
  336.             to = findIsland(n, y, islandX, islandY, islands);
  337.             assert (to >= 0); //we know about this island
  338.             //DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  339.             assert (
  340.                linkDirections[from][to] == NO_DIRECTION ||
  341.                linkDirections[from][to] == RIGHT
  342.             );
  343.             linkDirections[from][to] = RIGHT;
  344.             linkDirections[to][from] = LEFT;
  345.             bridges[from][to] = 0; //bridges are allowed here
  346.             bridges[to][from] = 0;
  347.             n = xDim;
  348.             //DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  349.             (*links) ++;
  350.          }
  351.       }
  352.    }
  353.    (*links) /= 2;
  354.    DB("%d possible links.\n", *links);
  355. }
  356.  
  357. void checkConnections(int connected[MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int island){
  358.    DB("Checking connections from island %d\n", island);
  359.    int i = 0;
  360.    connected[island] = CONNECTED;
  361.    for (i=0; i<islands; i++){
  362.       if (bridges[island][i] > 0){
  363.          if (connected[i] == NOT_CONNECTED){
  364.             checkConnections(connected, bridges, islands, i);
  365.          }
  366.       }
  367.    }
  368. }
  369.  
  370. 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]){
  371.    int i=0, j=0;
  372.    int n=0;
  373.    int islandBridge[islands]; //the number of bridges connected to each island
  374.    int connected[MAX_ISLANDS]; //whether each island is connected to island 0
  375.    int bridgeMap[MAX_DIM][MAX_DIM];
  376.    
  377.    for (i=0; i<MAX_DIM; i++){
  378.       for (j=0; j<MAX_DIM; j++){
  379.          bridgeMap[i][j] = NO_BRIDGE;
  380.       }
  381.    }
  382.    
  383.    //the total number of bridges connected to each island must be equal to the number on the island
  384.    for (i=0; i<islands; i++){
  385.       islandBridge[i] = 0; //init
  386.       connected[i] = NOT_CONNECTED;
  387.       for (j=0; j<islands; j++){
  388.          if (bridges[i][j] != NO_LINK){
  389.             islandBridge[i] += bridges[i][j];
  390.             //DB("{%d->%d = %d} ", i, j, bridges[i][j]);
  391.          }
  392.       }
  393.       if (islandBridge[i] != bridgeVal[i]){
  394.          return 0;
  395.       }
  396.    }
  397.  
  398.    //all the islands must be connected to each other
  399.    checkConnections(connected, bridges, islands, 0);
  400.    for (i=0; i<islands; i++){
  401.       if (connected[i] == NOT_CONNECTED){
  402.          DB("All nodes are not connected.  This is not a solution.\n");
  403.          return 0;
  404.       }
  405.    }
  406.    
  407.  
  408.    //bridges are not allowed to cross each other
  409.    for (i=0; i<islands; i++){
  410.       for (j=0; j<islands; j++){
  411.          switch (linkDirections[i][j]){
  412.          case UP:
  413.             assert (islandX[i] == islandX[j]);
  414.             for (n=islandY[i]-1; n > islandY[j]; n--)
  415.                if (bridgeMap[i][j] == BRIDGE)
  416.                   return 0;
  417.                bridgeMap[i][j] = BRIDGE;
  418.             break;
  419.          case DOWN:
  420.             assert (islandX[i] == islandX[j]);
  421.             for (n=islandY[i]+1; n < islandY[j]; n++)
  422.                if (bridgeMap[i][j] == BRIDGE)
  423.                   return 0;
  424.                bridgeMap[i][j] = BRIDGE;
  425.             break;
  426.          case LEFT:
  427.             assert (islandY[i] == islandY[j]);
  428.             for (n=islandX[i]-1; n > islandX[j]; n--)
  429.                if (bridgeMap[i][j] == BRIDGE)
  430.                   return 0;
  431.                bridgeMap[i][j] = BRIDGE;
  432.             break;
  433.          case RIGHT:
  434.             assert (islandY[i] == islandY[j]);
  435.             for (n=islandX[i]+1; n < islandX[j]; n++)
  436.                if (bridgeMap[i][j] == BRIDGE)
  437.                   return 0;
  438.                bridgeMap[i][j] = BRIDGE;
  439.             break;
  440.  
  441.             default:;
  442.          }
  443.       }
  444.    }
  445.    DB("Solution\n");
  446.    return 1;
  447. }
  448.  
  449. int addMoreBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]){
  450.    int bridgesAdded = 0;
  451.    int i=0, j=0;
  452.    int linkCounter = 0;
  453.    int newBridgeVal[islands];
  454.    int newPreparedBridges[islands][islands];
  455.    for (i=0; i<islands; i++){
  456.       newBridgeVal[i] = bridgeVal[i];
  457.       for (j=0; j<islands; j++){
  458.          newPreparedBridges[i][j] = 0;
  459.       }
  460.    }
  461.    
  462.    //newBridgeVal = bridgeVal - bridges in the original preparedBridges
  463.    for (i=0; i<islands; i++){
  464.       newBridgeVal[i] = bridgeVal[i];
  465.       for (j=0; j<islands; j++){
  466.          assert(preparedBridges[i][j] == preparedBridges[j][i]);
  467.          newBridgeVal[i] -= preparedBridges[i][j];
  468.          assert(newBridgeVal[i] >= 0);
  469.       }
  470.          //DB("BridgeVal: %d --> %d\n", bridgeVal[i], newBridgeVal[i]);
  471.    }
  472.    for (i=0; i<islands; i++){
  473.       if (newBridgeVal[i] > 0){
  474.          //assemble linkCounter, skipping full islands
  475.          linkCounter = 0;
  476.          for (j=0; j<islands; j++){
  477.             if ((linkDirections[i][j] != NO_DIRECTION) && (newBridgeVal[j] > 0)){
  478.                linkCounter++;
  479.             }
  480.          }
  481.       }
  482.       //addMandatoryBridges algorithm, but using newBridgeVal, and adding bridges only to islands that aren't full.
  483.       DB("Island %d: linkCounter = %d, newBridgeVal = %d", i, linkCounter, newBridgeVal[i]);
  484.       if (linkCounter > 0 && linkCounter == (newBridgeVal[i] + 1) / 2){
  485.          DB(" - more mandatory bridges here");
  486.          for (j=0; j<islands; j++){
  487.             if (newBridgeVal[j] > 0){
  488.                if (linkDirections[i][j] != NO_DIRECTION){
  489.                   newPreparedBridges[i][j] = (newBridgeVal[i] / linkCounter);
  490.                   bridgesAdded ++;
  491.                }
  492.             }
  493.          }
  494.       }
  495.       DB("\n");
  496.    }
  497.    DB("\n");
  498.    for (i=0; i<islands; i++){
  499.       for (j=0; j<islands; j++){
  500.          newPreparedBridges[i][j] = newPreparedBridges[j][i] = max(newPreparedBridges[i][j], newPreparedBridges[j][i]);
  501.          assert(newPreparedBridges[i][j] == newPreparedBridges[j][i]);
  502.          if (newPreparedBridges[i][j] > 0){
  503.             DB("Prepared bridge: %d%c%d\n", i,newPreparedBridges[i][j] == 1 ? HOR_SINGLE : HOR_DOUBLE, j);
  504.             assert(linkDirections[i][j] != NO_DIRECTION);
  505.          }
  506.          preparedBridges[i][j] += newPreparedBridges[i][j];
  507.       }
  508.    }
  509.    DB("%d extra bridges added this time\n", bridgesAdded);
  510.    return bridgesAdded;
  511. }
  512.  
  513. int fillOutBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]){
  514.    int bridgesAdded = 0;
  515.    int i=0, j=0;
  516.    int n=0;
  517.    int newBridgeVal[islands];
  518.    int linkCounter[islands];
  519.    int bridgeRoom[islands]; //room for more bridges
  520.    int newPreparedBridges[islands][islands];
  521.    for (i=0; i<islands; i++){
  522.       newBridgeVal[i] = 0;
  523.       bridgeRoom[i] = 0;
  524.       for (j=0; j<islands; j++){
  525.          linkCounter[i] = 0;
  526.          newPreparedBridges[i][j] = 0;
  527.       }
  528.    }
  529.    
  530.    
  531.    //newBridgeVal = bridgeVal - bridges in the original preparedBridges
  532.    DB("%d islands\n", islands);
  533.    for (i=0; i<islands; i++){
  534.       newBridgeVal[i] = bridgeVal[i];
  535.       if (newBridgeVal[i] > 0){
  536.          DB("Island %d, bridgeVal = %d", i, bridgeVal[i]);
  537.          for (j=0; j<islands; j++){
  538.             assert(preparedBridges[i][j] == preparedBridges[j][i]);
  539.             if (preparedBridges[i][j] > 0) DB(" -%d", preparedBridges[i][j]);
  540.             assert(preparedBridges[i][j] <= newBridgeVal[i]);
  541.             //DB("BridgeVal[%d} change: %d - %d = ", i, newBridgeVal[i], preparedBridges[i][j]);
  542.             newBridgeVal[i] -= preparedBridges[i][j];
  543.             //DB("%d\n", newBridgeVal[i]);
  544.             assert(newBridgeVal[i] >= 0);
  545.          }
  546.          DB("\n");
  547.       }
  548.       assert(newBridgeVal[i] >= 0);
  549.       DB("BridgeVal[%d]: %d --> %d\n", i, bridgeVal[i], newBridgeVal[i]);
  550.    }
  551.    for (i=0; i<islands; i++){
  552.       if (newBridgeVal[i] > 0){
  553.          //assemble linkCounter, skipping full islands
  554.          linkCounter[i] = 0;
  555.          for (j=0; j<islands; j++){
  556.             if ((linkDirections[i][j] != NO_DIRECTION) && (newBridgeVal[j] > 0)){
  557.                linkCounter[i] ++;
  558.                bridgeRoom[i] += newBridgeVal[j];
  559.             }
  560.          }
  561.       }
  562.    }
  563.    
  564.    //fill out bridges
  565.    for (i=0; i<islands; i++){
  566.       if (newBridgeVal[i] > 0 && newBridgeVal[i] == bridgeRoom[i]){ //all possible bridges can be filled
  567.          DB("Added %d bridges\n", bridgeRoom[i]);
  568.          for (j=0; j<islands; j++){
  569.             if (linkDirections[i][j] != NO_LINK){
  570.                n = newBridgeVal[j];
  571.                newPreparedBridges[i][j] += n;
  572.                newPreparedBridges[j][i] += n;
  573.                newBridgeVal[i] -= n;
  574.                newBridgeVal[j] -= n;
  575.                bridgesAdded ++;
  576.             }
  577.          }
  578.          //assert(newBridgeVal[i] == 0);
  579.       }
  580.    }
  581.  
  582.    for (i=0; i<islands; i++){
  583.       for (j=0; j<islands; j++){
  584.          newPreparedBridges[i][j] = newPreparedBridges[j][i] = max(newPreparedBridges[i][j], newPreparedBridges[j][i]);
  585.          assert(newPreparedBridges[i][j] == newPreparedBridges[j][i]);
  586.          if (newPreparedBridges[i][j] > 0) DB("Prepared bridge: %d%c%d\n", i,newPreparedBridges[i][j] == 1 ? HOR_SINGLE : HOR_DOUBLE, j);
  587.          
  588.          if (newPreparedBridges[i][j]>0) DB("Prepared bridges[%d][%d]: %d-->%d\n", i, j, preparedBridges[i][j], preparedBridges[i][j] + newPreparedBridges[i][j]);
  589.          preparedBridges[i][j] += newPreparedBridges[i][j];
  590.       }
  591.    }  
  592.  
  593.    return bridgesAdded;
  594. }
  595.  
  596. 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]){
  597.    int i=0, j=0;
  598.    int bridgeVal[islands];
  599.    int x=0, y=0;
  600.    int reached = 0;
  601.    for (i=0; i<islands; i++){
  602.       bridgeVal[i] = 0;
  603.       for (j=0; j<islands; j++){
  604.          if (preparedBridges[i][j] > 0 && linkDirections[i][j] != NO_DIRECTION){
  605.             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]);
  606.             bridgeVal[i] += preparedBridges[i][j];
  607.             reached = 0;
  608.             x=islandX[i];
  609.             y=islandY[i];
  610.             while (!reached){
  611.                switch (linkDirections[i][j]){
  612.                case UP:
  613.                   y --;
  614.                   reached = (y == islandY[j]);
  615.                   break;
  616.                case DOWN:
  617.                   y ++;
  618.                   reached = (y == islandY[j]);
  619.                   break;
  620.                case LEFT:
  621.                   x --;
  622.                   reached = (x == islandX[j]);
  623.                   break;
  624.                case RIGHT:
  625.                   x ++;
  626.                   reached = (x == islandX[j]);
  627.                   break;
  628.                default:
  629.                   DB("attempting to blacklist bridge with no direction\n");
  630.                   ;
  631.                }
  632.                if (x != islandX[j] || y != islandY[j]){
  633.                   map[x][y] = ((linkDirections[i][j] == LEFT || linkDirections[i][j] == RIGHT) ? '~' : 's'); //bridge part here; no crossing
  634.                }
  635.             }
  636.          }
  637.       }
  638.       map[islandX[i]][islandY[i]] = bridgeVal[i]+'0'; //for debugging purposes
  639.    }
  640. }
  641.  
  642. 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]){
  643.    //brief algorithm:
  644.    //performs initial bridgework of Smart Brute, then repeats the process in a modular way to further cut down required permutations.
  645.    int links = 0;
  646.    int solutionFound = 0;
  647.    int potential[3][islands*2];
  648.    int i=0, j=0, k=0;
  649.    int potentials = 0;
  650.    int listed = 0;
  651.    long long int bruteCap = 0;
  652.    long long int bruteLoop = 0;
  653.    int preparedBridges[MAX_ISLANDS][MAX_ISLANDS];
  654.    int newBridgeVal[islands];
  655.    int permutationNoGood = 0; //flags the current permutation as bad
  656.    
  657.    //init
  658.    for (i=0; i<islands; i++){
  659.       for (j=0; j<islands; j++){
  660.          preparedBridges[i][j] = 0;
  661.       }
  662.    }
  663.    for (i=0; i<=2; i++){
  664.       for (j=0; j<islands*2; j++){
  665.          potential[i][j] = 0;
  666.       }
  667.    }
  668.    
  669.    //Add bridges until no more can be added automatically
  670.    while (addMoreBridges(preparedBridges, islands, bridgeVal, linkDirections) > 0){
  671.       DB("Bridges added\n");
  672.       addBridgesToMap(preparedBridges, islandX, islandY, map, islands, linkDirections);
  673.       findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);
  674.       for (i=0; i<=xDim; i++){
  675.          for (j=0; j<=yDim; j++){
  676.             DB("%c", map[j][i]);
  677.          }
  678.          DB("\n");
  679.       }
  680.    }
  681.    while (fillOutBridges(preparedBridges, islands, bridgeVal, linkDirections) > 0){
  682.       DB("Bridges filled out\n");
  683.       addBridgesToMap(preparedBridges, islandX, islandY, map, islands, linkDirections);
  684.       findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);
  685.    }
  686.  
  687.    for (i=0; i<xDim; i++){
  688.       for (j=0; j<yDim; j++){
  689.          DB("%c", map[j][i]);
  690.       }
  691.       DB("\n");
  692.    }
  693.  
  694.    //newBridgeVal = bridgeVal - bridges in the original preparedBridges
  695.    for (i=0; i<islands; i++){
  696.       newBridgeVal[i] = bridgeVal[i];
  697.       for (j=0; j<islands; j++){
  698.          assert(preparedBridges[i][j] == preparedBridges[j][i]);
  699.          newBridgeVal[i] -= preparedBridges[i][j];
  700.       }
  701.       assert(newBridgeVal[i] >= 0);
  702.       DB("Bridge val[%d] after prepared bridges = %d\n", i, newBridgeVal[i]);
  703.    }
  704.    
  705.    //assemble list of potential bridges
  706.    for (i=0; i<islands; i++){
  707.       if (newBridgeVal[i] > 0){
  708.          for (j=0; j<islands; j++){
  709.             if (newBridgeVal[j] > 0){
  710.                if (preparedBridges[i][j] == 2){ //if a bridge of 2 already exists, there's no point in including this in the permutations
  711.                   //bridges[i][j] = bridges[j][i] = 2;
  712.                   DB("=== bridge already included\n");
  713.                }else{
  714.                   if (linkDirections[i][j] != NO_DIRECTION){
  715.                      //make sure this isn't already on the list
  716.                      listed = 0;
  717.                      for (k=0; k<potentials; k++){
  718.                         if (potential[0][k] == j && potential[1][k] == i){
  719.                            listed = 1;
  720.                            k = potentials;
  721.                         }
  722.                      }
  723.                      if (!listed){
  724.                         potential[0][potentials] = i;
  725.                         potential[1][potentials] = j;
  726.                         potential[2][potentials] = preparedBridges[i][j];
  727.                         potentials ++;
  728.                      }
  729.                   }
  730.                }
  731.             }
  732.          }
  733.       }
  734.    }
  735.    for (i=0; i<islands; i++){
  736.       for (j=0; j<islands; j++){
  737.          bridges[i][j] = bridges[j][i] = preparedBridges[i][j]; //permutations will overwrite what they need to
  738.       }
  739.    }
  740.    
  741.    DB("%d potential bridge locations:\n", potentials);
  742.    for (i=0; i<potentials; i++){
  743.       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]]);
  744.    }
  745.    //the variable "potentials" is the number of triplets we need to loop through.
  746.    bruteCap = power3(potentials);
  747.    DB("we're counting up to the number %Ld = 3^%d-1\n", bruteCap-1, potentials);
  748.                                                                                                                           //assert(0);
  749.    for (bruteLoop=0; bruteLoop<bruteCap; bruteLoop++){
  750.       DB("%20Ld %f%% |", bruteLoop, (100.0*bruteLoop/(bruteCap-1)));
  751.       permutationNoGood = 0;
  752.       for (i=0; i<potentials; i++){
  753.          //DB ("(%Ld - %Ld) / %Ld\n", bruteLoop % power(3, i+1), bruteLoop % power(3, i), power(3, i));
  754.          bridges[potential[0][i]][potential[1][i]] = ((bruteLoop % power3(i+1)) - (bruteLoop % power3(i))) / power3(i);
  755.          DB("%c", bridges[potential[0][i]][potential[1][i]]+'0');
  756.          if (bridges[potential[0][i]][potential[1][i]] < potential[2][i]){
  757.                                                                                     //printf("* - bad bridge at potential #%d", i);
  758.             DB("\n");
  759.             i=potentials; //exit loop
  760.             permutationNoGood = 1;
  761.          }else{
  762.             bridges[potential[1][i]][potential[0][i]] = bridges[potential[0][i]][potential[1][i]];
  763.          }
  764.       }
  765.                                                                                          if (bruteLoop % 1000000 == 0) printf("\n%20LdM %f%%", bruteLoop/1000000, (100.0*bruteLoop/bruteCap));
  766.       if (!permutationNoGood){
  767.          DB("|\n");
  768.          //check for solution
  769.          if (validSolution(bridges, islands, bridgeVal, linkDirections, islandX, islandY)){
  770.             bruteLoop = bruteCap;
  771.             solutionFound = 1;
  772.          }
  773.       }
  774.    }
  775.    DB("\n");
  776.    if (!solutionFound) printf("***No solution found***\n");
  777.                                                                                          printf("\n");
  778. }
  779.  
  780. 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]){
  781.    int i = 0, j = 0;
  782.    int from = 0, to = 0;
  783.    int n = 0;
  784.    int direction = NO_DIRECTION;
  785.    char bridgeChar = 0;
  786.    for (i=0; i<xDim; i++)
  787.       for (j=0; j<=yDim; j++)
  788.          output[i][j] = ' ';
  789.    for (i=0; i<islands; i++)
  790.       output[islandX[i]][islandY[i]] = bridgeVal[i] + '0'; //draw islands
  791.    for (from=0; from<islands; from++){
  792.       for (to=0; to<islands; to++){
  793.          if (bridges[from][to] > 0){
  794.             direction = linkDirections[from][to];
  795.             if (direction == UP || direction == DOWN){
  796.                bridgeChar = (bridges[from][to] == 1 ? VERT_SINGLE : VERT_DOUBLE);
  797.             }else{
  798.                assert(direction == LEFT || direction == RIGHT);
  799.                bridgeChar = (bridges[from][to] == 1 ? HOR_SINGLE : HOR_DOUBLE);
  800.             }
  801.             switch (direction){
  802.             case UP:
  803.                assert (islandX[from] == islandX[to]);
  804.                for (n=islandY[from]-1; n > islandY[to]; n--)
  805.                   output[islandX[from]][n] = bridgeChar;
  806.                break;
  807.             case DOWN:
  808.                assert (islandX[from] == islandX[to]);
  809.                for (n=islandY[from]+1; n < islandY[to]; n++)
  810.                   output[islandX[from]][n] = bridgeChar;
  811.                break;
  812.             case LEFT:
  813.                assert (islandY[from] == islandY[to]);
  814.                for (n=islandX[from]-1; n > islandX[to]; n--)
  815.                   output[n][islandY[from]] = bridgeChar;
  816.                break;
  817.             case RIGHT:
  818.                assert (islandY[from] == islandY[to]);
  819.                for (n=islandX[from]+1; n < islandX[to]; n++)
  820.                   output[n][islandY[from]] = bridgeChar;
  821.                break;
  822.  
  823.             default:;
  824.             }
  825.          }
  826.       }
  827.    }  
  828. }
  829.  
  830. void displayOutput(char output[MAX_DIM][MAX_DIM], int xDim, int yDim){
  831.    int i, j;
  832.    for (j=0; j<=yDim; j++){
  833.       for (i=0; i<xDim; i++){
  834.          putchar(output[i][j]);
  835.       }
  836.       putchar('\n');
  837.    }
  838. }
RAW Paste Data
Top