SHARE
TWEET

Untitled

a guest Feb 16th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stddef.h>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <stdbool.h>
  5.  
  6. #define CHIPS_AMOUNT 10
  7. #define BOARD_WIDTH 4
  8. #define BOARD_HEIGHT 5
  9. #define MAX_REC_DEPTH 50
  10.  
  11. typedef enum {   // action type of chip movement
  12.     UP,
  13.     RIGHT,
  14.     DOWN,
  15.     LEFT,
  16.     NONE
  17. } action;
  18.  
  19. typedef struct {
  20.     int x;
  21.     int y;
  22. } point;
  23.  
  24. typedef point * point_ptr;
  25.  
  26. typedef struct int_node int_node;
  27. typedef int_node * int_node_ptr;
  28. struct int_node {
  29.     int data;
  30.    
  31.     int_node_ptr next;
  32. };
  33.  
  34. void push_int(int_node_ptr queue, int val) {
  35.     int_node_ptr head = malloc(sizeof(int_node));
  36.     head->data = val;
  37.     head->next = queue->next;
  38.     queue->next = head;
  39. }
  40.  
  41. bool contains(int_node_ptr queue, int val) {
  42.     while (queue->next != NULL) {
  43.         if (queue->data == val) {
  44.             return true;
  45.         }
  46.         queue = queue->next;
  47.     }
  48.     return false;
  49. }
  50.  
  51. typedef struct {
  52.     int chip_idx;
  53.     action a;
  54. } chip_move;
  55.  
  56. typedef struct chip_move_node chip_move_node;
  57. typedef chip_move_node * chip_move_node_ptr;
  58. struct chip_move_node {
  59.     chip_move data;
  60.    
  61.     chip_move_node_ptr next;
  62. };
  63.  
  64. void push_chip_move(chip_move_node_ptr queue, chip_move val) {
  65.     chip_move_node_ptr head = malloc(sizeof(chip_move_node));
  66.     head->data = val;
  67.     head->next = queue->next;
  68.     queue->next = head;
  69. }
  70.  
  71. void pop_chip_move(chip_move_node_ptr queue) {
  72.     chip_move_node_ptr temp = queue->next->next;
  73.     free(queue->next);
  74.     queue->next = temp;
  75. }
  76.  
  77. typedef struct {
  78.     int width;  // width of the chip
  79.     int height; // height of the chip
  80.    
  81.     point coordinates;
  82. } chip;         // rectangle, which represents one chip
  83.  
  84. typedef chip * chip_ptr;
  85.  
  86. typedef struct {
  87.     int width;  // width of the board
  88.     int height; // height of the board
  89.    
  90.     point free_p1;
  91.     point free_p2;
  92.    
  93.     chip chips[CHIPS_AMOUNT];
  94. } board;        // bounded 2D lattice, which represents the initial box
  95.  
  96. typedef board * board_ptr; // pointer to board
  97.  
  98. void init_board(board_ptr b) {
  99.     b->width = BOARD_WIDTH;
  100.     b->height = BOARD_HEIGHT;
  101.    
  102.     // initialize chips according to conditions of the initial problem
  103.     b->chips[0] = (chip) {
  104.         .width = 1, .height = 2,
  105.         .coordinates = (point) { .x = 0, .y = 0 }
  106.     };
  107.     b->chips[1] = (chip) {
  108.         .width = 2, .height = 2,
  109.         .coordinates = (point) { .x = 1, .y = 0 }
  110.     };
  111.     b->chips[2] = (chip) {
  112.         .width = 1, .height = 2,
  113.         .coordinates = (point) { .x = 3, .y = 0 }
  114.     };
  115.     b->chips[3] = (chip) {
  116.         .width = 1, .height = 2,
  117.         .coordinates = (point) { .x = 0, .y = 2 }
  118.     };
  119.     b->chips[4] = (chip) {
  120.         .width = 2, .height = 1,
  121.         .coordinates = (point) { .x = 1, .y = 2 }
  122.     };
  123.     b->chips[5] = (chip) {
  124.         .width = 1, .height = 2,
  125.         .coordinates = (point) { .x = 3, .y = 2 }
  126.     };
  127.     b->chips[6] = (chip) {
  128.         .width = 1, .height = 1,
  129.         .coordinates = (point) { .x = 1, .y = 3 }
  130.     };
  131.     b->chips[7] = (chip) {
  132.         .width = 1, .height = 1,
  133.         .coordinates = (point) { .x = 2, .y = 3 }
  134.     };
  135.     b->chips[8] = (chip) {
  136.         .width = 1, .height = 1,
  137.         .coordinates = (point) { .x = 0, .y = 4 }
  138.     };
  139.     b->chips[9] = (chip) {
  140.         .width = 1, .height = 1,
  141.         .coordinates = (point) { .x = 3, .y = 4 }
  142.     };
  143.    
  144.     b->free_p1 = (point) {
  145.         .x = 1, .y = 4
  146.     };
  147.     b->free_p2 = (point) {
  148.         .x = 2, .y = 4
  149.     };
  150. }
  151.  
  152. int board_hash(board_ptr b, int chip_idx, action a) {
  153.     int hash = 17;
  154.     for (int i = 0; i < CHIPS_AMOUNT; ++i) {
  155.         point_ptr current = &b->chips[i].coordinates;
  156.         if (a != NONE && i == chip_idx) {
  157.             switch (a) {
  158.                 case UP: {
  159.                     hash = hash * 19 + current->x;
  160.                     hash = hash * 19 + current->y + 1;
  161.                     break;
  162.                 }
  163.                 case RIGHT: {
  164.                     hash = hash * 19 + current->x + 1;
  165.                     hash = hash * 19 + current->y;
  166.                     break;
  167.                 }
  168.                 case DOWN: {
  169.                     hash = hash * 19 + current->x;
  170.                     hash = hash * 19 + current->y - 1;
  171.                     break;
  172.                 }
  173.                 case LEFT: {
  174.                     hash = hash * 19 + current->x - 1;
  175.                     hash = hash * 19 + current->y;
  176.                     break;
  177.                 }
  178.                 default: {
  179.                     break; // code should never reach this line
  180.                 }
  181.             }
  182.         } else {
  183.             hash = hash * 19 + current->x;
  184.             hash = hash * 19 + current->y;
  185.         }
  186.     }
  187.    
  188.     return hash;
  189. }
  190.  
  191. int board_hash_wrap(board_ptr b) {
  192.     return board_hash(b, 0, NONE); // second arg is a dummy
  193. }
  194.  
  195. bool is_overlapping(board_ptr b, int chip_idx, action a) { // ensures a != NONE
  196.     chip_ptr current = &b->chips[chip_idx];
  197.     switch (a) {
  198.         case UP: {
  199.             if (current->coordinates.y == 0) {
  200.                 return true;
  201.             }
  202.            
  203.             if (current->width == 1) {
  204.                 return b->free_p1.x != current->coordinates.x && b->free_p1.y != current->coordinates.y - 1
  205.                     && b->free_p2.x != current->coordinates.x && b->free_p2.y != current->coordinates.y - 1;
  206.             }
  207.             if (b->free_p1.x == current->coordinates.x) {
  208.                 if (b->free_p2.x != current->coordinates.x + 1) {
  209.                     return true;
  210.                 }
  211.             } else if (b->free_p2.x == current->coordinates.x) {
  212.                 if (b->free_p1.x != current->coordinates.x + 1) {
  213.                     return true;
  214.                 }
  215.             } else {
  216.                 return true;
  217.             }
  218.             return b->free_p1.y != current->coordinates.y - 1 || b->free_p2.y != current->coordinates.y - 1;
  219.         }
  220.         case RIGHT: {
  221.             if (current->coordinates.x == BOARD_WIDTH - 1) {
  222.                 return true;
  223.             }
  224.            
  225.             if (current->height == 1) {
  226.                 return b->free_p1.y != current->coordinates.y && b->free_p1.x != current->coordinates.x + current->width
  227.                     && b->free_p2.y != current->coordinates.y && b->free_p2.x != current->coordinates.x + current->width;
  228.             }
  229.             if (b->free_p1.y == current->coordinates.y) {
  230.                 if (b->free_p2.y != current->coordinates.y + 1) {
  231.                     return true;
  232.                 }
  233.             } else if (b->free_p2.y == current->coordinates.y) {
  234.                 if (b->free_p1.y != current->coordinates.y + 1) {
  235.                     return true;
  236.                 }
  237.             } else {
  238.                 return true;
  239.             }
  240.             return b->free_p1.x != current->coordinates.x + current->width || b->free_p2.x != current->coordinates.x - 1;
  241.         }
  242.         case DOWN: {
  243.             if (current->coordinates.y == BOARD_HEIGHT - 1) {
  244.                 return true;
  245.             }
  246.            
  247.             if (current->width == 1) {
  248.                 return b->free_p1.x != current->coordinates.x && b->free_p1.y != current->coordinates.y + current->height
  249.                     && b->free_p2.x != current->coordinates.x && b->free_p2.y != current->coordinates.y + current->height;
  250.             }
  251.             if (b->free_p1.x == current->coordinates.x) {
  252.                 if (b->free_p2.x != current->coordinates.x + 1) {
  253.                     return true;
  254.                 }
  255.             } else if (b->free_p2.x == current->coordinates.x) {
  256.                 if (b->free_p1.x != current->coordinates.x + 1) {
  257.                     return true;
  258.                 }
  259.             } else {
  260.                 return true;
  261.             }
  262.             return b->free_p1.y != current->coordinates.y + current->height || b->free_p2.y != current->coordinates.y + current->height;
  263.         }
  264.         case LEFT: {
  265.             if (current->coordinates.x == CHIPS_AMOUNT) {
  266.                 return true;
  267.             }
  268.            
  269.             if (current->height == 1) {
  270.                 return b->free_p1.y != current->coordinates.y && b->free_p1.x != current->coordinates.x - 1
  271.                     && b->free_p2.y != current->coordinates.y && b->free_p2.x != current->coordinates.x - 1;
  272.             }
  273.             if (b->free_p1.y == current->coordinates.y) {
  274.                 if (b->free_p2.y != current->coordinates.y + 1) {
  275.                     return true;
  276.                 }
  277.             } else if (b->free_p2.y == current->coordinates.y) {
  278.                 if (b->free_p1.y != current->coordinates.y + 1) {
  279.                     return true;
  280.                 }
  281.             } else {
  282.                 return true;
  283.             }
  284.             return b->free_p1.x != current->coordinates.x - 1 || b->free_p2.x != current->coordinates.x - 1;
  285.         }
  286.         default:
  287.             return true; // code should never reach this line
  288.     }
  289. }
  290.  
  291. bool solve(board b, int chip_idx, action a, int depth, chip_move_node_ptr answer, int_node_ptr used) {
  292.     if (a != NONE) {
  293.         chip_ptr current = &b.chips[chip_idx];
  294.         switch (a) {
  295.             case UP: {
  296.                 if (current->width == 1) {
  297.                     if (b.free_p1.x == current->coordinates.x && b.free_p1.y == current->coordinates.y - 1) {
  298.                         ++b.free_p1.y;
  299.                     } else {
  300.                         ++b.free_p2.y;
  301.                     }
  302.                 } else {
  303.                     ++b.free_p1.y;
  304.                     ++b.free_p2.y;
  305.                 }
  306.                 ++current->coordinates.y;
  307.                
  308.                 break;
  309.             }
  310.             case RIGHT: {
  311.                 if (current->height == 1) {
  312.                     if (b.free_p1.y == current->coordinates.y && b.free_p1.x == current->coordinates.x + current->width) {
  313.                         ++b.free_p1.x;
  314.                     } else {
  315.                         ++b.free_p2.x;
  316.                     }
  317.                 } else {
  318.                     ++b.free_p1.x;
  319.                     ++b.free_p2.x;
  320.                 }
  321.                 ++current->coordinates.x;
  322.                
  323.                 break;
  324.             }
  325.             case DOWN: {
  326.                 if (current->width == 1) {
  327.                     if (b.free_p1.x == current->coordinates.x && b.free_p1.y == current->coordinates.y + current->height) {
  328.                         --b.free_p1.y;
  329.                     } else {
  330.                         --b.free_p2.y;
  331.                     }
  332.                 } else {
  333.                     --b.free_p1.y;
  334.                     --b.free_p2.y;
  335.                 }
  336.                 --current->coordinates.y;
  337.  
  338.                 break;
  339.             }
  340.             case LEFT: {
  341.                 if (current->height == 1) {
  342.                     if (b.free_p1.y == current->coordinates.y && b.free_p1.x == current->coordinates.x - 1) {
  343.                         --b.free_p1.x;
  344.                     } else {
  345.                         --b.free_p2.x;
  346.                     }
  347.                 } else {
  348.                     --b.free_p1.x;
  349.                     --b.free_p2.x;
  350.                 }
  351.                 --current->coordinates.x;
  352.                
  353.                 break;
  354.             }
  355.             default: {
  356.                 break; // code should never reach this line
  357.             }
  358.         }
  359.     }
  360.     push_int(used, board_hash_wrap(&b));
  361.    
  362.     if (b.chips[1].coordinates.x == 1 && b.chips[1].coordinates.y == 3) {
  363.         return true;
  364.     }
  365.  
  366.     if (depth == MAX_REC_DEPTH) {
  367.         return false;
  368.     }
  369.    
  370.     for (int i = 0; i < CHIPS_AMOUNT; ++i) {
  371.         if (!contains(used, board_hash(&b, i, UP)) && !is_overlapping(&b, i, UP) && solve(b, i, UP, depth + 1, answer, used)) {
  372.             push_chip_move(answer, (chip_move) { .chip_idx = i, .a = UP });
  373.             return true;
  374.         }
  375.         if (!contains(used, board_hash(&b, i, RIGHT)) && !is_overlapping(&b, i, RIGHT) && solve(b, i, RIGHT, depth + 1, answer, used)) {
  376.             push_chip_move(answer, (chip_move) { .chip_idx = i, .a = RIGHT });
  377.             return true;
  378.         }
  379.         if (!contains(used, board_hash(&b, i, DOWN)) && !is_overlapping(&b, i, DOWN) && solve(b, i, DOWN, depth + 1, answer, used)) {
  380.             push_chip_move(answer, (chip_move) { .chip_idx = i, .a = DOWN });
  381.             return true;
  382.         }
  383.         if (!contains(used, board_hash(&b, i, LEFT)) && !is_overlapping(&b, i, LEFT) && solve(b, i, LEFT, depth + 1, answer, used)) {
  384.             push_chip_move(answer, (chip_move) { .chip_idx = i, .a = LEFT });
  385.             return true;
  386.         }
  387.     }
  388.    
  389.     return false;
  390. }
  391.  
  392. bool solve_wrap(board_ptr b, chip_move_node_ptr answer, int_node_ptr used) {
  393.     return solve(*b, 0, NONE, 0, answer, used); // second arg is a dummy
  394. }
  395.  
  396. int main(void) {
  397.     board b;
  398.     init_board(&b);
  399.    
  400.     chip_move_node answer;
  401.     int_node used;
  402.    
  403.     if (solve_wrap(&b, &answer, &used)) {
  404.         print("solved");
  405.     } else {
  406.         print("unsolved");
  407.     }
  408.    
  409.     return 0;
  410. }
RAW Paste Data
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
 
Top