API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 25th, 2017
68
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 25.88 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <ctype.h>
  3. #include <assert.h>
  4.  
  5. #define DEBUG 0
  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.  
  36. int max(int a, int b);
  37. long long int power(int base, int index);
  38. char* directionName(int direction);
  39. int oppositeDirection(int direction);
  40. int findIsland(int x, int y, int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int islands);
  41. void inputGame(char map[MAX_DIM][MAX_DIM], int *xDim, int *yDim);
  42. int countIslands(char map[MAX_DIM][MAX_DIM], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int bridgeVal[MAX_ISLANDS], int xDim, int yDim);
  43. 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);
  44. void checkConnections(int connected[MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int island);
  45. 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]);
  46. void addMandatoryBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]);
  47. void solvePuzzleSmartBrute(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]);
  48. void solvePuzzleStupidBrute(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]);
  49. void solvePuzzle(int bridges[MAX_ISLANDS][MAX_ISLANDS], int algorithm, int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS]);
  50. 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]);
  51. void displayOutput(char output[MAX_DIM][MAX_DIM], int xDim, int yDim);
  52.  
  53. int main(int argc, char** argv){
  54.    
  55.    int i=0, j=0;
  56.    
  57.    int xDim = 0, yDim = 0; //the size of the map
  58.    char map[MAX_DIM][MAX_DIM];
  59.    //The layout of the game, as input
  60.    //
  61.    // 2..2
  62.    // ....  xDim = 4, yDim = 3
  63.    // 2..2
  64.  
  65.    int islands = 0;
  66.    int bridgeVal[MAX_ISLANDS];
  67.    int islandX[MAX_ISLANDS];
  68.    int islandY[MAX_ISLANDS];
  69.    //The grid co-ordinates and numeric value of each island
  70.    //
  71.    //    X Y bridgeVal
  72.    //    -----
  73.    // 0 |0 0 2
  74.    // 1 |3 0 2   islands = 4
  75.    // 2 |0 2 2
  76.    // 3 |3 2 2
  77.    
  78.    int links = 0;
  79.    int linkDirections[MAX_ISLANDS][MAX_ISLANDS];
  80.    //The direction of adjacency between two islands.  Opposites about the diagonal have opposite directions.
  81.    //
  82.    //    0123
  83.    //    ----  0 = No link
  84.    // 0 |0230  1 = Up
  85.    // 1 |4003  2 = Right
  86.    // 2 |1002  3 = Down
  87.    // 3 |0140  4 = Left
  88.    
  89.    int bridges[MAX_ISLANDS][MAX_ISLANDS];
  90.    //The answer to the puzzle.  0, 1, 2 indicates the number of bridges between two islands.  Symmetrical about the diagonal.
  91.    //
  92.    //    0123
  93.    //    ----
  94.    // 0 |0110
  95.    // 1 |1001
  96.    // 2 |1001
  97.    // 3 |0110
  98.    
  99.    char output[MAX_DIM][MAX_DIM];
  100.    //The program's output.
  101.    //
  102.    // 2--2
  103.    // |  |
  104.    // 2--2
  105.    
  106.    //init
  107.    for (i=0; i<MAX_DIM; i++){
  108.       for (j=0; j<MAX_DIM; j++){
  109.          map[i][j] = 0;
  110.       }
  111.    }
  112.    for (i=0; i<MAX_ISLANDS; i++){
  113.       bridgeVal[i] = 0;
  114.       islandX[i] = 0;
  115.       islandY[i] = 0;
  116.       for (j=0; j<MAX_ISLANDS; j++){
  117.          linkDirections[i][j] = NO_DIRECTION;
  118.          bridges[i][i] = NO_LINK;
  119.       }
  120.    }
  121.    
  122.    //Read and map out the game
  123.    DB("Inputting game...\n");
  124.    inputGame(map, &xDim, &yDim);
  125.    
  126.    DB("Counting islands...\n");
  127.    islands = countIslands(map, islandX, islandY, bridgeVal, xDim, yDim);
  128.    
  129.    DB("Determining adjacencies...\n");
  130.    findLinks(linkDirections, map, bridges, islandX, islandY, xDim, yDim, islands, &links);
  131.    
  132.    DB("Solving puzzle...\n");
  133.    solvePuzzle(bridges, SMART_BRUTE, islands, bridgeVal, linkDirections, islandX, islandY);
  134.    
  135.    DB("Building output...\n");
  136.    buildOutput(output, linkDirections, bridges, islandX, islandY, xDim, yDim, islands, bridgeVal);
  137.    
  138.    DB("Displaying output...\n");
  139.    displayOutput(output, xDim, yDim);
  140.  
  141.    return 0;
  142. }
  143.  
  144. int max(int a, int b){
  145.    return (a>b ? a : b);
  146. }
  147.  
  148. long long int power(int base, int index){
  149.    int i = 0;
  150.    long long int answer = 1;
  151.    for (i=0; i<index; i++)
  152.       answer *= base;
  153.    return answer;
  154. }
  155.  
  156. //Should be substantially faster than the above power()
  157. long long int power3(int index){
  158.    int i = 0;
  159.    long long int answer = 1;
  160.    switch(index){
  161.    case  0: return 1;
  162.    case  1: return 3;
  163.    case  2: return 9;
  164.    case  3: return 27;
  165.    case  4: return 81;
  166.    case  5: return 243;
  167.    case  6: return 729;
  168.    case  7: return 2187;
  169.    case  8: return 6561;
  170.    case  9: return 19683;
  171.    case 10: return 59049;
  172.    case 11: return 177147;
  173.    case 12: return 531441;
  174.    case 13: return 1594323;
  175.    case 14: return 4782969;
  176.    case 15: return 14348907;
  177.    case 16: return 43046721;
  178.    case 17: return 129140163;
  179.    case 18: return 387420489;
  180.    default:
  181.       for (i=0; i<index; i++)
  182.          answer *= 3;
  183.       return answer;
  184.    }
  185. }
  186.  
  187. char* directionName(int direction){
  188.    switch (direction){
  189.    case UP: return "up";
  190.    case DOWN: return "down";
  191.    case LEFT: return "left";
  192.    case RIGHT: return "right";
  193.    case NO_DIRECTION: return "no direction";
  194.    default: return "invalid direction";
  195.    }
  196. }
  197.  
  198. int oppositeDirection(int direction){
  199.    switch (direction){
  200.    case UP: return DOWN;
  201.    case DOWN: return UP;
  202.    case LEFT: return RIGHT;
  203.    case RIGHT: return LEFT;
  204.    default: return NO_DIRECTION;
  205.    }
  206. }
  207.  
  208. int findIsland(int x, int y, int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int islands){
  209.    int i;
  210.    for (i=0; i<islands; i++)
  211.       if (x == islandX[i] && y == islandY[i])
  212.          return i;
  213.    return -1; //if no island found
  214. }
  215.  
  216. void inputGame(char map[MAX_DIM][MAX_DIM], int *xDim, int *yDim){
  217.    int x = 0, y = 0;
  218.    char c;
  219.    c = getchar();
  220.    while (c != '\n' && c != EOF){
  221.       map[x][y] = c;
  222.       x ++;
  223.       c = getchar();
  224.       if (c == '\n'){
  225.          y ++;
  226.          *yDim = y;
  227.          if (x != 0)
  228.             *xDim = x;
  229.          x = 0;
  230.          c = getchar();
  231.       }
  232.    }
  233. }
  234.  
  235. int countIslands(char map[MAX_DIM][MAX_DIM], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS], int bridgeVal[MAX_ISLANDS], int xDim, int yDim){
  236.    int i, j;
  237.    int islands = 0;
  238.    DB("Dimensions: %dx%d\n", xDim, yDim);
  239.    for (j=0; j<=yDim; j++){
  240.       for (i=0; i<=xDim; i++){
  241.          if (isdigit(map[i][j])){
  242.             islandX[islands] = i;
  243.             islandY[islands] = j;
  244.             bridgeVal[islands] = (int) (map[i][j] - '0');
  245.             DB("Island %d: x=%d, y=%d.  Value = %d.\n", islands, i, j, bridgeVal[islands]);
  246.             islands ++;
  247.          }
  248.       }
  249.    }
  250.    DB("%d islands\n", islands);
  251.    return islands;
  252. }
  253.  
  254. 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){
  255.    int from = 0, to = 0;
  256.    int x = 0, y = 0;
  257.    int n = 0;
  258.    
  259.    for (from = 0; from<islands; from ++){
  260.       x = islandX[from];
  261.       y = islandY[from];
  262.      
  263.       // up
  264.       for (n = y-1; n>=0; n--){
  265.          if (isdigit(map[x][n])){
  266.             to = findIsland(x, n, islandX, islandY, islands);
  267.             assert (to >= 0); //we know about this island
  268.             DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  269.             assert (
  270.                linkDirections[from][to] == NO_DIRECTION ||
  271.                linkDirections[from][to] == UP
  272.             );
  273.             linkDirections[from][to] = UP;
  274.             linkDirections[to][from] = DOWN;
  275.             bridges[from][to] = 0; //bridges are allowed here
  276.             bridges[to][from] = 0;
  277.             n = 0;
  278.             DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  279.             (*links) ++;
  280.          }
  281.       }
  282.       // down
  283.       for (n = y+1; n<=yDim; n++){
  284.          if (isdigit(map[x][n])){
  285.             to = findIsland(x, n, islandX, islandY, islands);
  286.             assert (to >= 0); //we know about this island
  287.             DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  288.             assert (
  289.                linkDirections[from][to] == NO_DIRECTION ||
  290.                linkDirections[from][to] == DOWN
  291.             );
  292.             linkDirections[from][to] = DOWN;
  293.             linkDirections[to][from] = UP;
  294.             bridges[from][to] = 0; //bridges are allowed here
  295.             bridges[to][from] = 0;
  296.             n = yDim;
  297.             DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  298.             (*links) ++;
  299.          }
  300.       }
  301.       // left
  302.       for (n = x-1; n>=0; n--){
  303.          if (isdigit(map[n][y])){
  304.             to = findIsland(n, y, islandX, islandY, islands);
  305.             assert (to >= 0); //we know about this island
  306.             DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  307.             assert (
  308.                linkDirections[from][to] == NO_DIRECTION ||
  309.                linkDirections[from][to] == LEFT
  310.             );
  311.             linkDirections[from][to] = LEFT;
  312.             linkDirections[to][from] = RIGHT;
  313.             bridges[from][to] = 0; //bridges are allowed here
  314.             bridges[to][from] = 0;
  315.             n = 0;
  316.             DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  317.             (*links) ++;
  318.          }
  319.       }
  320.       // RIGHT
  321.       for (n = x+1; n<=xDim; n++){
  322.          if (isdigit(map[n][y])){
  323.             to = findIsland(n, y, islandX, islandY, islands);
  324.             assert (to >= 0); //we know about this island
  325.             DB("Direction from island %d to island %d = %d, %s (before processing).\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  326.             assert (
  327.                linkDirections[from][to] == NO_DIRECTION ||
  328.                linkDirections[from][to] == RIGHT
  329.             );
  330.             linkDirections[from][to] = RIGHT;
  331.             linkDirections[to][from] = LEFT;
  332.             bridges[from][to] = 0; //bridges are allowed here
  333.             bridges[to][from] = 0;
  334.             n = xDim;
  335.             DB("Direction from island %d to island %d = %d, %s.\n", from, to, linkDirections[from][to], directionName(linkDirections[from][to]));
  336.             (*links) ++;
  337.          }
  338.       }
  339.    }
  340.    assert (*links % 2 == 0);
  341.    (*links) /= 2;
  342.    DB("%d possible links.\n", *links);
  343. }
  344.  
  345. void checkConnections(int connected[MAX_ISLANDS], int bridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int island){
  346.    DB("Checking connections from island %d\n", island);
  347.    int i = 0;
  348.    connected[island] = CONNECTED;
  349.    for (i=0; i<islands; i++){
  350.       if (bridges[island][i] > 0){
  351.          if (connected[i] == NOT_CONNECTED){
  352.             checkConnections(connected, bridges, islands, i);
  353.          }
  354.       }
  355.    }
  356. }
  357.  
  358. 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]){
  359.    int i=0, j=0;
  360.    int n=0;
  361.    int islandBridge[islands]; //the number of bridges connected to each island
  362.    int connected[MAX_ISLANDS]; //whether each island is connected to island 0
  363.    int bridgeMap[MAX_DIM][MAX_DIM];
  364.    
  365.    for (i=0; i<MAX_DIM; i++){
  366.       for (j=0; j<MAX_DIM; j++){
  367.          bridgeMap[i][j] = NO_BRIDGE;
  368.       }
  369.    }
  370.    
  371.    //the total number of bridges connected to each island must be equal to the number on the island
  372.    for (i=0; i<islands; i++){
  373.       islandBridge[i] = 0; //init
  374.       connected[i] = NOT_CONNECTED;
  375.       for (j=0; j<islands; j++){
  376.          if (bridges[i][j] != NO_LINK){
  377.             islandBridge[i] += bridges[i][j];
  378.             //DB("{%d->%d = %d} ", i, j, bridges[i][j]);
  379.          }
  380.       }
  381.       if (islandBridge[i] != bridgeVal[i]){
  382.          return 0;
  383.       }
  384.    }
  385.  
  386.    //all the islands must be connected to each other
  387.    checkConnections(connected, bridges, islands, 0);
  388.    for (i=0; i<islands; i++){
  389.       if (connected[i] == NOT_CONNECTED){
  390.          DB("All nodes are not connected.  This is not a solution.\n");
  391.          return 0;
  392.       }
  393.    }
  394.    
  395.  
  396.    //bridges are not allowed to cross each other
  397.    for (i=0; i<islands; i++){
  398.       for (j=0; j<islands; j++){
  399.          switch (linkDirections[i][j]){
  400.          case UP:
  401.             assert (islandX[i] == islandX[j]);
  402.             for (n=islandY[i]-1; n > islandY[j]; n--)
  403.                if (bridgeMap[i][j] == BRIDGE)
  404.                   return 0;
  405.                bridgeMap[i][j] = BRIDGE;
  406.             break;
  407.          case DOWN:
  408.             assert (islandX[i] == islandX[j]);
  409.             for (n=islandY[i]+1; n < islandY[j]; n++)
  410.                if (bridgeMap[i][j] == BRIDGE)
  411.                   return 0;
  412.                bridgeMap[i][j] = BRIDGE;
  413.             break;
  414.          case LEFT:
  415.             assert (islandY[i] == islandY[j]);
  416.             for (n=islandX[i]-1; n > islandX[j]; n--)
  417.                if (bridgeMap[i][j] == BRIDGE)
  418.                   return 0;
  419.                bridgeMap[i][j] = BRIDGE;
  420.             break;
  421.          case RIGHT:
  422.             assert (islandY[i] == islandY[j]);
  423.             for (n=islandX[i]+1; n < islandX[j]; n++)
  424.                if (bridgeMap[i][j] == BRIDGE)
  425.                   return 0;
  426.                bridgeMap[i][j] = BRIDGE;
  427.             break;
  428.  
  429.             default:;
  430.          }
  431.       }
  432.    }
  433.    DB("Solution\n");
  434.    return 1;
  435. }
  436.  
  437. void addMandatoryBridges(int preparedBridges[MAX_ISLANDS][MAX_ISLANDS], int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS]){
  438.    int i = 0, j = 0;
  439.    int linkCounter = 0; //How many islands are adjacent to the current one
  440.    
  441.    for (i=0; i<islands; i++){
  442.       linkCounter = 0;
  443.       for (j=0; j<islands; j++){
  444.          if (linkDirections[i][j] != NO_DIRECTION){
  445.             linkCounter ++;
  446.          }
  447.       }
  448.       DB("Island %d: linkCounter = %d, bridgeVal = %d", i, linkCounter, bridgeVal[i]);
  449.       if (linkCounter == ((bridgeVal[i] + 1) / 2)){
  450.          DB(" - mandatory bridges here");
  451.          for (j=0; j<islands; j++){
  452.             if (linkDirections[i][j] != NO_DIRECTION){
  453.                preparedBridges[i][j] = (bridgeVal[i] / linkCounter);
  454.             }
  455.          }
  456.       }
  457.       DB("\n");
  458.    }
  459.    DB("\n");
  460.    for (i=0; i<islands; i++){
  461.       for (j=0; j<islands; j++){
  462.          preparedBridges[i][j] = preparedBridges[j][i] = max(preparedBridges[i][j], preparedBridges[j][i]);
  463.          //DB("%d,%d = %d.  %d,%d = %d.\n", i, j, preparedBridges[i][j], j, i, preparedBridges[j][i]);
  464.          assert(preparedBridges[i][j] == preparedBridges[j][i]);
  465.          if (preparedBridges[i][j] > 0) DB("Prepared bridge: %d%c%d\n", i,preparedBridges[i][j] == 1 ? HOR_SINGLE : HOR_DOUBLE, j);
  466.       }
  467.    }
  468. }
  469.  
  470. void solvePuzzleSmartBrute(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]){
  471.    //brief algorithm:
  472.    //Similar to Stupid Brute, but skips some branches by initially building a list of mandatory bridges
  473.    int solutionFound = 0;
  474.    int potential[3][islands*2];
  475.    int i=0, j=0, k=0;
  476.    int potentials = 0;
  477.    int listed = 0;
  478.    long long int bruteCap = 0;
  479.    long long int bruteLoop = 0;
  480.    int preparedBridges[MAX_ISLANDS][MAX_ISLANDS];
  481.    int permutationNoGood = 0; //flags the current permutation as bad
  482.    
  483.    //init
  484.    for (i=0; i<islands; i++){
  485.       for (j=0; j<islands; j++){
  486.          preparedBridges[i][j] = 0;
  487.       }
  488.    }
  489.    for (i=0; i<=2; i++){
  490.       for (j=0; j<islands*2; j++){
  491.          potential[i][j] = 0;
  492.       }
  493.    }
  494.    addMandatoryBridges(preparedBridges, islands, bridgeVal, linkDirections);
  495.    DB("Mandatory bridges over %d islands:\n", islands);
  496.    for (i=0; i<islands; i++){
  497.       for (j=0; j<islands; j++){
  498.          DB("%c", preparedBridges[i][j] == 0 ? ' ' : preparedBridges[i][j]+'0');
  499.       }
  500.       DB("\n");
  501.    }
  502.    for (i=0; i<islands; i++){
  503.       for (j=0; j<islands; j++){
  504.          DB("%c", preparedBridges[j][i] == 0 ? ' ' : preparedBridges[j][i]+'0');
  505.       }
  506.       DB("\n");
  507.    }
  508.    
  509.    
  510.    //assemble list of potential bridges
  511.    for (i=0; i<islands; i++){
  512.       for (j=0; j<islands; j++){
  513.          if (preparedBridges[i][j] == 2){
  514.             bridges[i][j] = bridges[j][i] = 2;
  515.          }else{
  516.             if (linkDirections[i][j] != NO_DIRECTION){
  517.                //make sure this isn't already on the list
  518.                listed = 0;
  519.                for (k=0; k<potentials; k++){
  520.                   if (potential[0][k] == j && potential[1][k] == i){
  521.                      listed = 1;
  522.                      k = potentials;
  523.                   }
  524.                }
  525.                if (!listed){
  526.                   potential[0][potentials] = i;
  527.                   potential[1][potentials] = j;
  528.                   potential[2][potentials] = preparedBridges[i][j];
  529.                   potentials ++;
  530.                }
  531.             }
  532.          }
  533.       }
  534.    }
  535.    DB("%d potential bridge locations:\n", potentials);
  536.    for (i=0; i<potentials; i++){
  537.       DB("Island %d to island %d\n", potential[0][i], potential[1][i]);
  538.    }
  539.    //the variable "potentials" is the number of triplets we need to loop through.
  540.    bruteCap = power3(potentials);
  541.    DB("we're counting up to the number %Ld = 3^%d-1\n", bruteCap-1, potentials);
  542.                                                                                         //assert(0);
  543.    for (bruteLoop=0; bruteLoop<bruteCap; bruteLoop++){
  544.       DB("%20Ld %f%% |", bruteLoop, (100.0*bruteLoop/(bruteCap-1)));
  545.       permutationNoGood = 0;
  546.       for (i=0; i<potentials; i++){
  547.          //DB ("(%Ld - %Ld) / %Ld\n", bruteLoop % power(3, i+1), bruteLoop % power(3, i), power(3, i));
  548.          bridges[potential[0][i]][potential[1][i]] = ((bruteLoop % power3(i+1)) - (bruteLoop % power3(i))) / power3(i);
  549.          DB("%c", bridges[potential[0][i]][potential[1][i]]+'0');
  550.          if (bridges[potential[0][i]][potential[1][i]] < potential[2][i]){
  551.                                                                                     //printf("* - bad bridge at potential #%d", i);
  552.             DB("\n");
  553.             i=potentials; //exit loop
  554.             permutationNoGood = 1;
  555.          }else{
  556.             bridges[potential[1][i]][potential[0][i]] = bridges[potential[0][i]][potential[1][i]];
  557.          }
  558.       }
  559.                                                                                          if (bruteLoop % 1000000 == 0) printf("\n%20LdM %f%%", bruteLoop/1000000, (100.0*bruteLoop/bruteCap));
  560.       if (!permutationNoGood){
  561.          DB("|\n");
  562.          //check for solution
  563.          if (validSolution(bridges, islands, bridgeVal, linkDirections, islandX, islandY)){
  564.             bruteLoop = bruteCap;
  565.             solutionFound = 1;
  566.          }
  567.       }
  568.    }
  569.    DB("\n");
  570.    if (!solutionFound) printf("***No solution found***\n");
  571.                                                                                          printf("\n");
  572. }
  573.  
  574. void solvePuzzleStupidBrute(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]){
  575.    //brief algorithm:
  576.    //assemble list of possible bridges, including the two islands in question
  577.    //loop:
  578.    //   I'll be working through a list of ternary numbers. 00, 01, 02, 10, 11, 12, 20, 21, 22.
  579.    //   in the above example, with 2 possible bridges, there are 9 possible permutations.
  580.    //   assign the current number to the bridge pattern
  581.    //   check whether it's a solution
  582.    //   if so, exit loop
  583.    
  584.    int solutionFound = 0;
  585.    int potential[2][islands*2];
  586.    int i=0, j=0, k=0;
  587.    int potentials = 0;
  588.    int listed = 0;
  589.    long long int bruteCap = 0;
  590.    long long int bruteLoop = 0;
  591.    
  592.    //assemble list of potential bridges
  593.    for (i=0; i<islands; i++){
  594.       for (j=0; j<islands; j++){
  595.          if (linkDirections[i][j] != NO_DIRECTION){
  596.             //make sure this isn't already on the list
  597.             listed = 0;
  598.             for (k=0; k<potentials; k++){
  599.                if (potential[0][k] == j && potential[1][k] == i){
  600.                   listed = 1;
  601.                   k = potentials;
  602.                }
  603.             }
  604.             if (!listed){
  605.                potential[0][potentials] = i;
  606.                potential[1][potentials] = j;
  607.                potentials ++;
  608.             }
  609.          }
  610.       }
  611.    }
  612.    DB("%d potential bridge locations:\n", potentials);
  613.    for (i=0; i<potentials; i++){
  614.       DB("Island %d to island %d\n", potential[0][i], potential[1][i]);
  615.    }
  616.    
  617.    //the variable "potentials" is the number of triplets we need to loop through.
  618.    bruteCap = power(3, potentials);
  619.    DB("we're counting up to the number %Ld = 3^%d-1\n", bruteCap-1, potentials);
  620.    
  621.    for (bruteLoop=0; bruteLoop<bruteCap; bruteLoop++){
  622.       DB("%20Ld %f%% |", bruteLoop, (100.0*bruteLoop/bruteCap));
  623.       for (i=0; i<potentials; i++){
  624.          //DB ("(%Ld - %Ld) / %Ld\n", bruteLoop % power(3, i+1), bruteLoop % power(3, i), power(3, i));
  625.          bridges[potential[0][i]][potential[1][i]] = ((bruteLoop % power(3, i+1)) - (bruteLoop % power(3, i))) / power(3, i);
  626.          bridges[potential[1][i]][potential[0][i]] = bridges[potential[0][i]][potential[1][i]];
  627.          DB("%c", bridges[potential[0][i]][potential[1][i]]+'0');
  628.       }
  629.       DB("| ");
  630.                                                                                    if (bruteLoop % 1000000 == 0) printf("\n%20LdM %f%%", bruteLoop/1000000, (100.0*bruteLoop/bruteCap));
  631.       //check for solution
  632.       if (validSolution(bridges, islands, bridgeVal, linkDirections, islandX, islandY)){
  633.          bruteLoop = bruteCap;
  634.          solutionFound = 1;
  635.       }
  636.    }
  637.    DB("\n");
  638.    if (!solutionFound) printf("***No solution found***\n");
  639. }
  640.  
  641. void solvePuzzle(int bridges[MAX_ISLANDS][MAX_ISLANDS], int algorithm, int islands, int bridgeVal[MAX_ISLANDS], int linkDirections[MAX_ISLANDS][MAX_ISLANDS], int islandX[MAX_ISLANDS], int islandY[MAX_ISLANDS]){
  642.    switch (algorithm){
  643.    case STUPID_BRUTE:
  644.       solvePuzzleStupidBrute(bridges, islands, bridgeVal, linkDirections, islandX, islandY);
  645.       break;
  646.    case SMART_BRUTE:
  647.       solvePuzzleSmartBrute(bridges, islands, bridgeVal, linkDirections, islandX, islandY);
  648.       break;
  649.      
  650.    default:;
  651.    }
  652. }
  653.  
  654. 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]){
  655.    int i = 0, j = 0;
  656.    int from = 0, to = 0;
  657.    int n = 0;
  658.    int direction = NO_DIRECTION;
  659.    char bridgeChar = 0;
  660.    for (i=0; i<xDim; i++)
  661.       for (j=0; j<=yDim; j++)
  662.          output[i][j] = ' ';
  663.    for (i=0; i<islands; i++)
  664.       output[islandX[i]][islandY[i]] = bridgeVal[i] + '0'; //draw islands
  665.    for (from=0; from<islands; from++){
  666.       for (to=0; to<islands; to++){
  667.          if (bridges[from][to] > 0){
  668.             direction = linkDirections[from][to];
  669.             if (direction == UP || direction == DOWN){
  670.                bridgeChar = (bridges[from][to] == 1 ? VERT_SINGLE : VERT_DOUBLE);
  671.             }else{
  672.                assert(direction == LEFT || direction == RIGHT);
  673.                bridgeChar = (bridges[from][to] == 1 ? HOR_SINGLE : HOR_DOUBLE);
  674.             }
  675.             switch (direction){
  676.             case UP:
  677.                assert (islandX[from] == islandX[to]);
  678.                for (n=islandY[from]-1; n > islandY[to]; n--)
  679.                   output[islandX[from]][n] = bridgeChar;
  680.                break;
  681.             case DOWN:
  682.                assert (islandX[from] == islandX[to]);
  683.                for (n=islandY[from]+1; n < islandY[to]; n++)
  684.                   output[islandX[from]][n] = bridgeChar;
  685.                break;
  686.             case LEFT:
  687.                assert (islandY[from] == islandY[to]);
  688.                for (n=islandX[from]-1; n > islandX[to]; n--)
  689.                   output[n][islandY[from]] = bridgeChar;
  690.                break;
  691.             case RIGHT:
  692.                assert (islandY[from] == islandY[to]);
  693.                for (n=islandX[from]+1; n < islandX[to]; n++)
  694.                   output[n][islandY[from]] = bridgeChar;
  695.                break;
  696.  
  697.             default:;
  698.             }
  699.          }
  700.       }
  701.    }  
  702. }
  703.  
  704. void displayOutput(char output[MAX_DIM][MAX_DIM], int xDim, int yDim){
  705.    int i, j;
  706.    for (j=0; j<=yDim; j++){
  707.       for (i=0; i<xDim; i++){
  708.          putchar(output[i][j]);
  709.       }
  710.       putchar('\n');
  711.    }
  712. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!