Advertisement
aaaaaa123456789

JV's programming challenge, week 4

Dec 5th, 2012
114
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdlib.h>
  2.  
  3. unsigned short * tour(unsigned short);
  4.  
  5. unsigned move(unsigned, unsigned, unsigned char);
  6. unsigned short * findTour(unsigned short, unsigned, unsigned (*) (unsigned, unsigned, unsigned short));
  7. unsigned char degree(unsigned, unsigned char *, unsigned short);
  8. unsigned changeOrdering(unsigned, unsigned, unsigned short);
  9.  
  10. // just a way to convert the coordinates into one single value, and back
  11. #define row(A) ((A) & 65535)
  12. #define column(A) (((A) >> 16) & 65535)
  13. #define cellNumber(ROW, COL) (((ROW) & 65535) | (((COL) & 65535) << 16))
  14.  
  15. #define offset(CELL, SIZE) ((row(CELL) - 1) + ((column(CELL) - 1) * (SIZE)))
  16.  
  17. unsigned orderings[20] = {
  18.     076543210,
  19.     076543201,
  20.     076543102,
  21.     076543120,
  22.     076543021,
  23.     076543012,
  24.     076542013,
  25.     076542031,
  26.     076542130,
  27.     076542103,
  28.     076542301,
  29.     076542310,
  30.     076541320,
  31.     076541302,
  32.     076541203,
  33.     076541230,
  34.     076541032,
  35.     076541023,
  36.     076540123,
  37.     0 // just to indicate the list ends
  38. };
  39.  
  40. unsigned short * tour (unsigned short boardSize) {
  41.   // returns an array with the cells, first row then column. Returns NULL if no tour is found
  42.   if (boardSize < 5) return NULL; // no tours on smaller boards
  43.   if (boardSize < 112) {
  44.     unsigned * nextOrdering;
  45.     unsigned short * result;
  46.     for (nextOrdering = orderings; *nextOrdering; nextOrdering ++) {
  47.       result = findTour(boardSize, *nextOrdering, NULL);
  48.       if (result) return result;
  49.     }
  50.     return NULL;
  51.   }
  52.   return findTour(boardSize, changeOrdering(0, 0, boardSize), &changeOrdering);
  53. }
  54.  
  55.  
  56. unsigned move (unsigned initialCell, unsigned boardSize, unsigned char moveType) {
  57.   if (!initialCell) return 0;
  58.   switch (moveType) {
  59.     case 0:
  60.       if (row(initialCell) < 3) return 0;
  61.       if (column(initialCell) >= boardSize) return 0;
  62.       return initialCell + 65534; // 2 up, 1 right
  63.     case 1:
  64.       if (row(initialCell) < 2) return 0;
  65.       if (column(initialCell) >= (boardSize - 1)) return 0;
  66.       return initialCell + 131071; // 1 up, 2 right
  67.     case 2:
  68.       if (row(initialCell) >= boardSize) return 0;
  69.       if (column(initialCell) >= (boardSize - 1)) return 0;
  70.       return initialCell + 131073; // 1 down, 2 right
  71.     case 3:
  72.       if (row(initialCell) >= (boardSize - 1)) return 0;
  73.       if (column(initialCell) >= boardSize) return 0;
  74.       return initialCell + 65538; // 2 down, 1 right
  75.     case 4:
  76.       if (row(initialCell) >= (boardSize - 1)) return 0;
  77.       if (column(initialCell) < 2) return 0;
  78.       return initialCell - 65534; // 2 down, 1 left
  79.     case 5:
  80.       if (row(initialCell) >= boardSize) return 0;
  81.       if (column(initialCell) < 3) return 0;
  82.       return initialCell - 131071; // 1 down, 2 left
  83.     case 6:
  84.       if (row(initialCell) < 2) return 0;
  85.       if (column(initialCell) < 3) return 0;
  86.       return initialCell - 131073; // 1 up, 2 left
  87.     case 7:
  88.       if (row(initialCell) < 3) return 0;
  89.       if (column(initialCell) < 2) return 0;
  90.       return initialCell - 65538; // 2 up, 1 left
  91.     default:
  92.       return 0;
  93.   }
  94. }
  95.  
  96. unsigned short * findTour (unsigned short boardSize, unsigned ordering, unsigned (* orderingChangingCallback) (unsigned, unsigned, unsigned short)) {
  97.   unsigned char * cells = calloc(boardSize * boardSize, 1);
  98.   if (!cells) return NULL; // if there's no memory...
  99.   unsigned * moves = calloc(boardSize * boardSize * sizeof(unsigned), 1);
  100.   unsigned char neighbours[9];
  101.   unsigned char scores[8];
  102.   unsigned char a, b, min;
  103.   unsigned cell;
  104.   if (!moves) {
  105.     free(cells);
  106.     return NULL;
  107.   }
  108.   unsigned * finish = moves + boardSize * boardSize;
  109.   unsigned * nextMove = moves;
  110.   *(nextMove ++) = cellNumber(1, 1); // we always start here
  111.   *cells = 1; // so we take the cell away
  112.   for (; nextMove < finish; nextMove ++) {
  113.     for (a = b = 0; a < 8; a ++) {
  114.       cell = move(nextMove[-1], boardSize, a);
  115.       if (cell && !cells[offset(cell, boardSize)])
  116.         neighbours[b ++] = a;
  117.       else
  118.         scores[a] = 255;
  119.     }
  120.     if (!b) { // no moves
  121.       free(moves);
  122.       free(cells);
  123.       return NULL;
  124.     }
  125.     neighbours[b] = 255;
  126.     for (a = 0; neighbours[a] != 255; a ++)
  127.       scores[neighbours[a]] = degree(move(nextMove[-1], boardSize, neighbours[a]), cells, boardSize);
  128.     min = 255;
  129.     for (a = 0; a < 8; a ++)
  130.       if (scores[a] < min)
  131.         min = scores[a];
  132.     for (a = 0, b = 0; a < 8; a ++)
  133.       if (scores[a] == min)
  134.         neighbours[b ++] = a;
  135.     if (!b) { // shouldn't happen
  136.       free(moves);
  137.       free(cells);
  138.       return NULL;
  139.     }
  140.     if (b == 1)
  141.       cell = move(nextMove[-1], boardSize, *neighbours);
  142.     else {
  143.       neighbours[b] = 255;
  144.       unsigned current;
  145.       unsigned char search;
  146.       for (a = 0, current = ordering; a < 8; a ++, current >>= 3) {
  147.         search = current & 7;
  148.         for (b = 0; neighbours[b] != 255; b ++)
  149.           if (neighbours[b] == search)
  150.             break;
  151.         if (neighbours[b] != 255) break;
  152.       }
  153.       if (neighbours[b] == 255) { // shouldn't happen
  154.         free(moves);
  155.         free(cells);
  156.         return NULL;
  157.       }
  158.       cell = move(nextMove[-1], boardSize, neighbours[b]);
  159.     }
  160.     *nextMove = cell;
  161.     cells[offset(cell, boardSize)] = 1;
  162.     if (orderingChangingCallback)
  163.       ordering = (*orderingChangingCallback)(ordering, cell, boardSize);
  164.   }
  165.   free(cells);
  166.   unsigned short * result = malloc(2 * boardSize * boardSize * sizeof(unsigned short));
  167.   if (!result) { // no memory!
  168.     free(moves);
  169.     return NULL;
  170.   }
  171.   unsigned short * nextResult = result;
  172.   for (nextMove = moves; nextMove < finish; nextMove ++) {
  173.     *(nextResult ++) = row(*nextMove);
  174.     *(nextResult ++) = column(*nextMove);
  175.   }
  176.   free(moves);
  177.   return result;
  178. }
  179.  
  180. unsigned char degree (unsigned cell, unsigned char * cells, unsigned short boardSize) {
  181.   if (!cell) return 9;
  182.   unsigned char moveNumber, total;
  183.   unsigned neighbour;
  184.   for (moveNumber = total = 0; moveNumber < 8; moveNumber ++) {
  185.     neighbour = move(cell, boardSize, moveNumber);
  186.     if (neighbour) total += !cells[offset(neighbour, boardSize)];
  187.   }
  188.   return total;
  189. }
  190.  
  191. unsigned changeOrdering (unsigned ordering, unsigned cell, unsigned short boardSize) {
  192.   unsigned char type = boardSize & 7;
  193.   switch (type) {
  194.     case 0:
  195.       if (!cell) return 076405132;
  196.       if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 042013567;
  197.       if (cell == cellNumber(2, 2)) return 013265704;
  198.       if (cell == cellNumber(boardSize - 8, 1)) return 076513204;
  199.       if (cell == cellNumber(7, boardSize - 3)) return 076542301;
  200.       return ordering;
  201.     case 1:
  202.       if (!cell) return 076405132;
  203.       if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 042013567;
  204.       if (cell == cellNumber(2, 2)) return 076531204;
  205.       if (cell == cellNumber(boardSize - 6, (boardSize + 9) / 2)) return 045607312;
  206.       return ordering;
  207.     case 2:
  208.       if (!cell) return 076405132;
  209.       if (cell == cellNumber(6, 1)) return 042013567;
  210.       if (cell == cellNumber(3, 1)) return 076512034;
  211.       if (cell == cellNumber(boardSize - 15, 4)) return 076502314;
  212.       if (cell == cellNumber(10, boardSize - 2)) return 021063547;
  213.       if (cell == cellNumber(5, (boardSize - 6) / 2)) return 021753640;
  214.       return ordering;
  215.     case 3:
  216.       if (!cell) return 070641532;
  217.       if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 064207513;
  218.       if (cell == cellNumber(boardSize - 6, boardSize)) return 063210457;
  219.       if (cell == cellNumber(2, 5)) return 013265704;
  220.       if (cell == cellNumber(boardSize - 10, 3)) return 062341705;
  221.       if (cell == cellNumber((boardSize + 1) / 2, boardSize - 2)) return 072413506;
  222.       return ordering;
  223.     case 4:
  224.       if (!cell) return 076405132;
  225.       if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 042013567;
  226.       if (cell == cellNumber(2, 2)) return 013265704;
  227.       if (cell == cellNumber(boardSize - 8, 1)) return 076513204;
  228.       if (cell == cellNumber(10, boardSize - 5)) return 01324657;
  229.       if (cell == cellNumber(13, (boardSize + 2) / 2)) return 01325476;
  230.       return ordering;
  231.     case 5:
  232.       if (!cell) return 076405132;
  233.       if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 042013567;
  234.       if (cell == cellNumber(2, 2)) return 076531204;
  235.       if (cell == cellNumber(boardSize - 2, (boardSize & ~15) / 2)) return 076532140;
  236.       return ordering;
  237.     case 6:
  238.       if (!cell) return 076405132;
  239.       if (cell == cellNumber(6, 1)) return 042013567;
  240.       if (cell == cellNumber(3, 1)) return 076512034;
  241.       if (cell == cellNumber(boardSize - 10, 1)) return 076502314;
  242.       if (cell == cellNumber(10, boardSize - 2)) return 021063547;
  243.       if (cell == cellNumber(3, (boardSize + 8) / 2)) return 076524310;
  244.       return ordering;
  245.     case 7:
  246.       if (!cell) return 070641532;
  247.       if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 064207513;
  248.       if (cell == cellNumber(boardSize - 6, boardSize)) return 063210457;
  249.       if (cell == cellNumber(2, 5)) return 013265704;
  250.       if (cell == cellNumber(boardSize - 6, 3)) return 062341705;
  251.       if (cell == cellNumber((boardSize + 1) / 2, boardSize - 2)) return 037164205;
  252.       return ordering;
  253.   }
  254. }
Advertisement
RAW Paste Data Copied
Advertisement