Initial commitHEADmaster

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
diff --git a/board.c b/board.c
new file mode 100644
index 0000000..e9ad9ad
--- /dev/null
+++ b/board.c
@@ -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);
+    }
+}
diff --git a/board.h b/board.h
new file mode 100644
index 0000000..7374b9e
--- /dev/null
+++ b/board.h
@@ -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 */
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..6280d4e
--- /dev/null
+++ b/main.c
@@ -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;
+}