I was practicing question 3a of the British Informatics Olympiad 2023 past paper.
In the Tower of Oxford game there are four pegs and four balls (numbered 1, 2, 3, 4) which can be stacked on the pegs. Each peg has a height of four, i.e. it can support a stack of all four balls. We will denote a stack, running from the bottom to the top, by a sequence of digits running left (bottom) to right (top). E.g. 1234 is the stack with the balls in order and 1 on the bottom. An empty stack will be denoted by the digit 0. The current state of the game will be shown by giving each peg’s stack. A valid move in the game consists of moving the top ball from a peg’s stack and placing it on top of a (possibly empty) stack on another peg. Given a start position, the object of the game is to make the minimum number of moves to get to a given end position.
Write a program to determine the minimum number of moves required to get between two game states. Your program should first input four numbers showing the initial state of the game. The next line of input will contain another four numbers giving the end state of the game. You should output the minimum number of moves required to get from the start to the end state. It is possible to get between any two game states.
This is the code I wrote:
Code:
#include <stdlib.h>#include <stdbool.h>#include <string.h>#include <stdio.h>#define N_BALLS 4#define N_SPIRES 4#define N_NEXT_STATE_ITEMS (N_SPIRES * (N_SPIRES - 1))#define MAX_INPUT_STR_SIZE 12 // length of "1234 0 0 0\n" or equivelenttypedef struct State State;struct State { int val[N_SPIRES][N_BALLS]; int steps_so_far;};typedef struct QueueNode QueueNode;struct QueueNode { State *state; QueueNode *next;};void enqueue(QueueNode **head, State *state) { QueueNode *new_node = malloc(sizeof(QueueNode)); new_node->state = state; new_node->next = *head; *head = new_node;}State *dequeue(QueueNode **head) { QueueNode *current, *prev = NULL; State *ret = NULL; if (*head == NULL) return NULL; current = *head; while (current->next != NULL) { prev = current; current = current->next; } ret = current->state; free(current); if (prev != NULL) { prev->next = NULL; } else { *head = NULL; } return ret;}void free_all(QueueNode **head) { State *item; do { item = dequeue(head); } while (item != NULL);}// find the top of a spireint *top(int *spire) { int *p = spire; do { ++p; if (p == spire + (N_BALLS)) return NULL; // check for full spire } while (*p != 0); return p - 1;}void move(State *start_state, int start_spire, int end_spire) { if (start_spire == end_spire) return; int *start = top(start_state->val[start_spire]); int *end = top(start_state->val[end_spire]); if (start == NULL || end == NULL) return; if (*start == 0) return; if (*end != 0) { ++end; } *end = *start; *start = 0;}// returns a State[] with the length N_NEXT_STATE_ITEMSState *get_possible_next_states(State start_state) { State *possible_next_states = calloc(N_NEXT_STATE_ITEMS, sizeof(State)); State *ptr = possible_next_states; for (int start_spire = 0; start_spire < N_SPIRES; ++start_spire) { for (int end_spire = 0; end_spire < N_SPIRES; ++end_spire) { if (start_spire == end_spire) continue; memcpy(ptr, &start_state, sizeof start_state); move(ptr, start_spire, end_spire); ++(ptr->steps_so_far); ++ptr; } } return possible_next_states;}bool are_states_equal(State *state1, State *state2) { for (int i = 0; i < N_SPIRES; ++i) { for (int j = 0; j < N_SPIRES; ++j) { if (state1->val[i][j] != state2->val[i][j]) { return false; } } } return true;}// find the minimum moves it takes to get between two states.int find_min_moves(State start_state, State end_state) { if (are_states_equal(&start_state, &end_state)) return 0; QueueNode *states_head = NULL; enqueue(&states_head, &start_state); State *next_states; while (true) { next_states = get_possible_next_states(*dequeue(&states_head)); for (int i = 0; i < N_NEXT_STATE_ITEMS; ++i) { if (are_states_equal(&(next_states[i]), &end_state)) { int steps_taken = next_states[i].steps_so_far; // save value before free'd free_all(&states_head); free(next_states); return steps_taken; } State *state_copy = malloc(sizeof(State)); memcpy(state_copy, &(next_states[i]), sizeof(State)); enqueue(&states_head, state_copy); } free(next_states); }}void parse_state(char *str, State *state) { state->steps_so_far = 0; char *token = strtok(str, " "); for (int i = 0; i < N_SPIRES; ++i) { if (token == NULL) return; for (int j = 0; j < N_BALLS; ++j) { if (token[j] == '\0' || token[j] == '0') { break; } char str[2] = {token[j], '\0'}; state->val[i][j] = atoi(str); } token = strtok(NULL, " "); }}int main() { char start_str[MAX_INPUT_STR_SIZE] = {0}; char end_str[MAX_INPUT_STR_SIZE] = {0}; printf("Enter states:\n"); fgets(start_str, MAX_INPUT_STR_SIZE, stdin); fgets(end_str, MAX_INPUT_STR_SIZE, stdin); State start_state = {0}; State end_state = {0}; parse_state(start_str, &start_state); parse_state(end_str, &end_state); printf("%d\n", find_min_moves(start_state, end_state));}Example run:
Code:
Enter states:12 0 3 41 32 4 03(More test cases can be found in the mark scheme)
I would be grateful to hear about any possible improvements to the code. I would also be grateful to hear about any possible optimizations, as at the moment, the code hangs for some of the more complex inputs in the mark scheme.
