diff options
-rw-r--r-- | Makefile | 19 | ||||
-rw-r--r-- | board.c | 362 | ||||
-rw-r--r-- | board.h | 44 | ||||
-rw-r--r-- | main.c | 135 |
4 files changed, 560 insertions, 0 deletions
diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..8bff220 --- /dev/null +++ b/Makefile @@ -0,0 +1,19 @@ +CC = gcc +CFLAGS = \ + -Wall -Wmissing-prototypes -Wstrict-prototypes \ + -O2 -std=gnu11 -ggdb3 + +BINARY = c1024 +SOURCES = $(wildcard *.c) +OBJECTS = $(SOURCES:.c=.o) + +$(BINARY): $(OBJECTS) + $(CC) -o $@ $^ $(LIBS) + +%.o: %.c + $(CC) $(CFLAGS) -c -o $@ $< + +clean: + rm -f $(BINARY) $(OBJECTS) + +.PHONY: clean @@ -0,0 +1,362 @@ +/* + * Copyright (c) 2019 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <assert.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdlib.h> +#include <stdio.h> + +#include "board.h" + +struct board { + unsigned int *matrix; + size_t order; + unsigned int target_value; + bool won; +}; + +/* + * The slide algorithm, including the move and merge parts, only implements + * sliding to the right. Sliding to another direction uses the same algorithm + * with a different index computation function. + */ +typedef size_t (*board_compute_index_fn)(const struct board *board, + size_t row_index, size_t col_index); + +static unsigned int +board_make_value(void) +{ + return ((rand() % 2) + 1) * 2; +} + +static size_t +board_order(const struct board *board) +{ + return board->order; +} + +static size_t +board_size(const struct board *board) +{ + return board_order(board) * board_order(board); +} + +static unsigned int +board_target_value(const struct board *board) +{ + return board->target_value; +} + +static void +board_set_won(struct board *board) +{ + board->won = true; +} + +static bool +board_won(const struct board *board) +{ + return board->won; +} + +static bool +board_index_valid(const struct board *board, size_t index) +{ + return index < board_size(board); +} + +static bool +board_row_index_valid(const struct board *board, size_t row_index) +{ + return row_index < board_order(board); +} + +static bool +board_col_index_valid(const struct board *board, size_t col_index) +{ + return col_index < board_order(board); +} + +static unsigned int +board_get(const struct board *board, size_t index) +{ + assert(board_index_valid(board, index)); + return board->matrix[index]; +} + +static void +board_set(struct board *board, size_t index, unsigned int value) +{ + assert(board_index_valid(board, index)); + assert(value != 0); + + board->matrix[index] = value; + + if (value == board_target_value(board)) { + board_set_won(board); + } +} + +static void +board_clear(struct board *board, size_t index) +{ + assert(board_index_valid(board, index)); + board->matrix[index] = 0; +} + +static size_t +board_compute_index(const struct board *board, + size_t row_index, size_t col_index) +{ + assert(board_row_index_valid(board, row_index)); + assert(board_col_index_valid(board, col_index)); + return (row_index * board_order(board)) + col_index; +} + +static bool +board_should_set_tile(const struct board *board) +{ + return (rand() % board_size(board)) == 0; +} + +static void +board_add_tiles(struct board *board, size_t target_nr_tiles) +{ + size_t size, nr_tiles; + bool zero_tile_found; + + size = board_size(board); + nr_tiles = 0; + + do { + zero_tile_found = false; + + for (size_t i = 0; i < size; i++) { + if (board_get(board, i) == 0) { + + if (board_should_set_tile(board)) { + board_set(board, i, board_make_value()); + nr_tiles++; + + if (nr_tiles == target_nr_tiles) { + return; + } + } else { + zero_tile_found = true; + } + } + } + } while (zero_tile_found); +} + +struct board * +board_create(size_t order, unsigned int target_value) +{ + struct board *board; + + if (order <= 2) { + fprintf(stderr, "invalid order\n"); + return NULL; + } + + board = malloc(sizeof(*board)); + + if (!board) { + goto out; + } + + board->matrix = calloc(order * order, sizeof(*board->matrix)); + + if (!board->matrix) { + free(board); + board = NULL; + goto out; + } + + board->order = order; + board->target_value = target_value; + board->won = false; + + board_add_tiles(board, 2); + +out: + return board; +} + +static bool +board_move_row(struct board *board, board_compute_index_fn compute_index_fn, + size_t row_index) +{ + size_t zero_tile_index = 0; /* Silence false positive warning */ + bool zero_tile_found; + + zero_tile_found = false; + + for (size_t i = board_order(board) - 1; i < board_order(board); i--) { + unsigned int value; + size_t index; + + index = compute_index_fn(board, row_index, i); + value = board_get(board, index); + + if (value == 0) { + if (!zero_tile_found) { + zero_tile_index = index; + zero_tile_found = true; + } + } else { + if (zero_tile_found && (index != zero_tile_index)) { + board_set(board, zero_tile_index, value); + board_clear(board, index); + return true; + } + } + } + + return false; +} + +static bool +board_merge_row(struct board *board, board_compute_index_fn compute_index_fn, + size_t row_index) +{ + for (size_t i = board_order(board) - 1; i != 0; i--) { + unsigned int left_value, right_value; + size_t left_index, right_index; + + left_index = compute_index_fn(board, row_index, i - 1); + left_value = board_get(board, left_index); + + right_index = compute_index_fn(board, row_index, i); + right_value = board_get(board, right_index); + + if ((left_value != 0) && (left_value == right_value)) { + board_set(board, right_index, left_value + right_value); + board_clear(board, left_index); + return true; + } + } + + return false; +} + +static void +board_slide_row(struct board *board, board_compute_index_fn compute_index_fn, + size_t row_index) +{ + bool moved, merged; + + do { + moved = board_move_row(board, compute_index_fn, row_index); + merged = board_merge_row(board, compute_index_fn, row_index); + } while (moved || merged); +} + +static void +board_slide(struct board *board, board_compute_index_fn compute_index_fn) +{ + for (size_t i = 0; i < board_order(board); i++) { + board_slide_row(board, compute_index_fn, i); + } +} + +static size_t +board_compute_index_up(const struct board *board, + size_t row_index, size_t col_index) +{ + return board_compute_index(board, board_order(board) - col_index - 1, + row_index); +} + +static size_t +board_compute_index_left(const struct board *board, + size_t row_index, size_t col_index) +{ + return board_compute_index(board, row_index, + board_order(board) - col_index - 1); +} + +static size_t +board_compute_index_right(const struct board *board, + size_t row_index, size_t col_index) +{ + return board_compute_index(board, row_index, col_index); +} + +static size_t +board_compute_index_down(const struct board *board, + size_t row_index, size_t col_index) +{ + return board_compute_index(board, col_index, row_index); +} + +bool +board_apply(struct board *board, enum board_dir dir) +{ + board_compute_index_fn compute_index_fn; + + switch (dir) { + case BOARD_UP: + compute_index_fn = board_compute_index_up; + break; + case BOARD_LEFT: + compute_index_fn = board_compute_index_left; + break; + case BOARD_DOWN: + compute_index_fn = board_compute_index_down; + break; + case BOARD_RIGHT: + compute_index_fn = board_compute_index_right; + break; + default: + fprintf(stderr, "invalid direction\n"); + goto out; + } + + board_slide(board, compute_index_fn); + board_add_tiles(board, 1); + +out: + return board_won(board); +} + +static void +board_print_row(const struct board *board, size_t row_index) +{ + size_t index; + + for (size_t i = 0; i < board_order(board); i++) { + index = board_compute_index(board, row_index, i); + printf(" %6u", board_get(board, index)); + } + + printf("\n"); +} + +void +board_print(const struct board *board) +{ + for (size_t i = 0; i < board_order(board); i++) { + board_print_row(board, i); + } +} @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2019 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#ifndef BOARD_H +#define BOARD_H + +#include <stdbool.h> +#include <stddef.h> + +enum board_dir { + BOARD_UP, + BOARD_LEFT, + BOARD_DOWN, + BOARD_RIGHT, +}; + +struct board; + +struct board * board_create(size_t order, unsigned int target_value); + +bool board_apply(struct board *board, enum board_dir dir); + +void board_print(const struct board *board); + +#endif /* BOARD_H */ @@ -0,0 +1,135 @@ +/* + * Copyright (c) 2019 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <time.h> + +#include "board.h" + +#define DEFAULT_ORDER 4 +#define DEFAULT_TARGET 1024 + +static int +convert_char(enum board_dir *dir, char c) +{ + /* Handle both QWERTY and AZERTY layouts */ + switch (c) { + case 'w': + case 'z': + *dir = BOARD_UP; + break; + case 'a': + case 'q': + *dir = BOARD_LEFT; + break; + case 's': + *dir = BOARD_DOWN; + break; + case 'd': + *dir = BOARD_RIGHT; + break; + default: + if ((c != '\r') && (c != '\n')) { + fprintf(stderr, "invalid input\n"); + } + + return -1; + } + + return 0; +} + +int +main(int argc, char **argv) +{ + struct board *board; + bool won, congratulated; + unsigned int target; + size_t order; + int error; + + won = false; + congratulated = false; + + srand(time(NULL)); + + if (argc < 2) { + order = DEFAULT_ORDER; + target = DEFAULT_TARGET; + } else { + int ret; + + if (strcmp(argv[1], "-h") == 0) { + printf("c1024 -h\n" + "c1024 [<order> [<target>]]\n"); + return EXIT_SUCCESS; + } + + ret = sscanf(argv[1], "%zu", &order); + + if (ret != 1) { + fprintf(stderr, "invalid order\n"); + return EXIT_FAILURE; + } + + if (argc > 2) { + ret = sscanf(argv[2], "%u", &target); + + if (ret != 1) { + fprintf(stderr, "invalid target\n"); + return EXIT_FAILURE; + } + } else { + target = DEFAULT_TARGET; + } + } + + board = board_create(order, target); + + if (!board) { + return EXIT_FAILURE; + } + + board_print(board); + + for (;;) { + enum board_dir dir; + + error = convert_char(&dir, getchar()); + + if (error) { + continue; + } + + won = board_apply(board, dir); + board_print(board); + + if (won && !congratulated) { + printf("Well done !\n"); + congratulated = true; + } + } + + return EXIT_SUCCESS; +} |