Advertisement
Guest User

Untitled

a guest
Feb 16th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.98 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement