Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stddef.h>
- #include <stdlib.h>
- #include <stdio.h>
- #include <stdbool.h>
- #define CHIPS_AMOUNT 10
- #define BOARD_WIDTH 4
- #define BOARD_HEIGHT 5
- #define MAX_REC_DEPTH 50
- typedef enum { // action type of chip movement
- UP,
- RIGHT,
- DOWN,
- LEFT,
- NONE
- } action;
- typedef struct {
- int x;
- int y;
- } point;
- typedef point * point_ptr;
- typedef struct int_node int_node;
- typedef int_node * int_node_ptr;
- struct int_node {
- int data;
- int_node_ptr next;
- };
- void push_int(int_node_ptr queue, int val) {
- int_node_ptr head = malloc(sizeof(int_node));
- head->data = val;
- head->next = queue->next;
- queue->next = head;
- }
- bool contains(int_node_ptr queue, int val) {
- while (queue->next != NULL) {
- if (queue->data == val) {
- return true;
- }
- queue = queue->next;
- }
- return false;
- }
- typedef struct {
- int chip_idx;
- action a;
- } chip_move;
- typedef struct chip_move_node chip_move_node;
- typedef chip_move_node * chip_move_node_ptr;
- struct chip_move_node {
- chip_move data;
- chip_move_node_ptr next;
- };
- void push_chip_move(chip_move_node_ptr queue, chip_move val) {
- chip_move_node_ptr head = malloc(sizeof(chip_move_node));
- head->data = val;
- head->next = queue->next;
- queue->next = head;
- }
- void pop_chip_move(chip_move_node_ptr queue) {
- chip_move_node_ptr temp = queue->next->next;
- free(queue->next);
- queue->next = temp;
- }
- typedef struct {
- int width; // width of the chip
- int height; // height of the chip
- point coordinates;
- } chip; // rectangle, which represents one chip
- typedef chip * chip_ptr;
- typedef struct {
- int width; // width of the board
- int height; // height of the board
- point free_p1;
- point free_p2;
- chip chips[CHIPS_AMOUNT];
- } board; // bounded 2D lattice, which represents the initial box
- typedef board * board_ptr; // pointer to board
- void init_board(board_ptr b) {
- b->width = BOARD_WIDTH;
- b->height = BOARD_HEIGHT;
- // initialize chips according to conditions of the initial problem
- b->chips[0] = (chip) {
- .width = 1, .height = 2,
- .coordinates = (point) { .x = 0, .y = 0 }
- };
- b->chips[1] = (chip) {
- .width = 2, .height = 2,
- .coordinates = (point) { .x = 1, .y = 0 }
- };
- b->chips[2] = (chip) {
- .width = 1, .height = 2,
- .coordinates = (point) { .x = 3, .y = 0 }
- };
- b->chips[3] = (chip) {
- .width = 1, .height = 2,
- .coordinates = (point) { .x = 0, .y = 2 }
- };
- b->chips[4] = (chip) {
- .width = 2, .height = 1,
- .coordinates = (point) { .x = 1, .y = 2 }
- };
- b->chips[5] = (chip) {
- .width = 1, .height = 2,
- .coordinates = (point) { .x = 3, .y = 2 }
- };
- b->chips[6] = (chip) {
- .width = 1, .height = 1,
- .coordinates = (point) { .x = 1, .y = 3 }
- };
- b->chips[7] = (chip) {
- .width = 1, .height = 1,
- .coordinates = (point) { .x = 2, .y = 3 }
- };
- b->chips[8] = (chip) {
- .width = 1, .height = 1,
- .coordinates = (point) { .x = 0, .y = 4 }
- };
- b->chips[9] = (chip) {
- .width = 1, .height = 1,
- .coordinates = (point) { .x = 3, .y = 4 }
- };
- b->free_p1 = (point) {
- .x = 1, .y = 4
- };
- b->free_p2 = (point) {
- .x = 2, .y = 4
- };
- }
- int board_hash(board_ptr b, int chip_idx, action a) {
- int hash = 17;
- for (int i = 0; i < CHIPS_AMOUNT; ++i) {
- point_ptr current = &b->chips[i].coordinates;
- if (a != NONE && i == chip_idx) {
- switch (a) {
- case UP: {
- hash = hash * 19 + current->x;
- hash = hash * 19 + current->y + 1;
- break;
- }
- case RIGHT: {
- hash = hash * 19 + current->x + 1;
- hash = hash * 19 + current->y;
- break;
- }
- case DOWN: {
- hash = hash * 19 + current->x;
- hash = hash * 19 + current->y - 1;
- break;
- }
- case LEFT: {
- hash = hash * 19 + current->x - 1;
- hash = hash * 19 + current->y;
- break;
- }
- default: {
- break; // code should never reach this line
- }
- }
- } else {
- hash = hash * 19 + current->x;
- hash = hash * 19 + current->y;
- }
- }
- return hash;
- }
- int board_hash_wrap(board_ptr b) {
- return board_hash(b, 0, NONE); // second arg is a dummy
- }
- bool is_overlapping(board_ptr b, int chip_idx, action a) { // ensures a != NONE
- chip_ptr current = &b->chips[chip_idx];
- switch (a) {
- case UP: {
- if (current->coordinates.y == 0) {
- return true;
- }
- if (current->width == 1) {
- return b->free_p1.x != current->coordinates.x && b->free_p1.y != current->coordinates.y - 1
- && b->free_p2.x != current->coordinates.x && b->free_p2.y != current->coordinates.y - 1;
- }
- if (b->free_p1.x == current->coordinates.x) {
- if (b->free_p2.x != current->coordinates.x + 1) {
- return true;
- }
- } else if (b->free_p2.x == current->coordinates.x) {
- if (b->free_p1.x != current->coordinates.x + 1) {
- return true;
- }
- } else {
- return true;
- }
- return b->free_p1.y != current->coordinates.y - 1 || b->free_p2.y != current->coordinates.y - 1;
- }
- case RIGHT: {
- if (current->coordinates.x == BOARD_WIDTH - 1) {
- return true;
- }
- if (current->height == 1) {
- return b->free_p1.y != current->coordinates.y && b->free_p1.x != current->coordinates.x + current->width
- && b->free_p2.y != current->coordinates.y && b->free_p2.x != current->coordinates.x + current->width;
- }
- if (b->free_p1.y == current->coordinates.y) {
- if (b->free_p2.y != current->coordinates.y + 1) {
- return true;
- }
- } else if (b->free_p2.y == current->coordinates.y) {
- if (b->free_p1.y != current->coordinates.y + 1) {
- return true;
- }
- } else {
- return true;
- }
- return b->free_p1.x != current->coordinates.x + current->width || b->free_p2.x != current->coordinates.x - 1;
- }
- case DOWN: {
- if (current->coordinates.y == BOARD_HEIGHT - 1) {
- return true;
- }
- if (current->width == 1) {
- return b->free_p1.x != current->coordinates.x && b->free_p1.y != current->coordinates.y + current->height
- && b->free_p2.x != current->coordinates.x && b->free_p2.y != current->coordinates.y + current->height;
- }
- if (b->free_p1.x == current->coordinates.x) {
- if (b->free_p2.x != current->coordinates.x + 1) {
- return true;
- }
- } else if (b->free_p2.x == current->coordinates.x) {
- if (b->free_p1.x != current->coordinates.x + 1) {
- return true;
- }
- } else {
- return true;
- }
- return b->free_p1.y != current->coordinates.y + current->height || b->free_p2.y != current->coordinates.y + current->height;
- }
- case LEFT: {
- if (current->coordinates.x == CHIPS_AMOUNT) {
- return true;
- }
- if (current->height == 1) {
- return b->free_p1.y != current->coordinates.y && b->free_p1.x != current->coordinates.x - 1
- && b->free_p2.y != current->coordinates.y && b->free_p2.x != current->coordinates.x - 1;
- }
- if (b->free_p1.y == current->coordinates.y) {
- if (b->free_p2.y != current->coordinates.y + 1) {
- return true;
- }
- } else if (b->free_p2.y == current->coordinates.y) {
- if (b->free_p1.y != current->coordinates.y + 1) {
- return true;
- }
- } else {
- return true;
- }
- return b->free_p1.x != current->coordinates.x - 1 || b->free_p2.x != current->coordinates.x - 1;
- }
- default:
- return true; // code should never reach this line
- }
- }
- bool solve(board b, int chip_idx, action a, int depth, chip_move_node_ptr answer, int_node_ptr used) {
- if (a != NONE) {
- chip_ptr current = &b.chips[chip_idx];
- switch (a) {
- case UP: {
- if (current->width == 1) {
- if (b.free_p1.x == current->coordinates.x && b.free_p1.y == current->coordinates.y - 1) {
- ++b.free_p1.y;
- } else {
- ++b.free_p2.y;
- }
- } else {
- ++b.free_p1.y;
- ++b.free_p2.y;
- }
- ++current->coordinates.y;
- break;
- }
- case RIGHT: {
- if (current->height == 1) {
- if (b.free_p1.y == current->coordinates.y && b.free_p1.x == current->coordinates.x + current->width) {
- ++b.free_p1.x;
- } else {
- ++b.free_p2.x;
- }
- } else {
- ++b.free_p1.x;
- ++b.free_p2.x;
- }
- ++current->coordinates.x;
- break;
- }
- case DOWN: {
- if (current->width == 1) {
- if (b.free_p1.x == current->coordinates.x && b.free_p1.y == current->coordinates.y + current->height) {
- --b.free_p1.y;
- } else {
- --b.free_p2.y;
- }
- } else {
- --b.free_p1.y;
- --b.free_p2.y;
- }
- --current->coordinates.y;
- break;
- }
- case LEFT: {
- if (current->height == 1) {
- if (b.free_p1.y == current->coordinates.y && b.free_p1.x == current->coordinates.x - 1) {
- --b.free_p1.x;
- } else {
- --b.free_p2.x;
- }
- } else {
- --b.free_p1.x;
- --b.free_p2.x;
- }
- --current->coordinates.x;
- break;
- }
- default: {
- break; // code should never reach this line
- }
- }
- }
- push_int(used, board_hash_wrap(&b));
- if (b.chips[1].coordinates.x == 1 && b.chips[1].coordinates.y == 3) {
- return true;
- }
- if (depth == MAX_REC_DEPTH) {
- return false;
- }
- for (int i = 0; i < CHIPS_AMOUNT; ++i) {
- if (!contains(used, board_hash(&b, i, UP)) && !is_overlapping(&b, i, UP) && solve(b, i, UP, depth + 1, answer, used)) {
- push_chip_move(answer, (chip_move) { .chip_idx = i, .a = UP });
- return true;
- }
- if (!contains(used, board_hash(&b, i, RIGHT)) && !is_overlapping(&b, i, RIGHT) && solve(b, i, RIGHT, depth + 1, answer, used)) {
- push_chip_move(answer, (chip_move) { .chip_idx = i, .a = RIGHT });
- return true;
- }
- if (!contains(used, board_hash(&b, i, DOWN)) && !is_overlapping(&b, i, DOWN) && solve(b, i, DOWN, depth + 1, answer, used)) {
- push_chip_move(answer, (chip_move) { .chip_idx = i, .a = DOWN });
- return true;
- }
- if (!contains(used, board_hash(&b, i, LEFT)) && !is_overlapping(&b, i, LEFT) && solve(b, i, LEFT, depth + 1, answer, used)) {
- push_chip_move(answer, (chip_move) { .chip_idx = i, .a = LEFT });
- return true;
- }
- }
- return false;
- }
- bool solve_wrap(board_ptr b, chip_move_node_ptr answer, int_node_ptr used) {
- return solve(*b, 0, NONE, 0, answer, used); // second arg is a dummy
- }
- int main(void) {
- board b;
- init_board(&b);
- chip_move_node answer;
- int_node used;
- if (solve_wrap(&b, &answer, &used)) {
- print("solved");
- } else {
- print("unsolved");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement