diff options
| -rw-r--r-- | include/enums.h | 11 | ||||
| -rw-r--r-- | include/ptn.c | 156 | ||||
| -rw-r--r-- | include/ptn.h | 24 | ||||
| -rw-r--r-- | include/state.c | 315 | ||||
| -rw-r--r-- | include/state.h | 25 | ||||
| -rw-r--r-- | src/ctaklm.c | 3 |
6 files changed, 1 insertions, 533 deletions
diff --git a/include/enums.h b/include/enums.h deleted file mode 100644 index 752c678..0000000 --- a/include/enums.h +++ /dev/null @@ -1,11 +0,0 @@ -#ifndef ENUMS_H_INCLUDE -#define ENUMS_H_INCLUDE -enum COLOUR { C_WHITE, C_BLACK }; -enum STONE_VARIANT { STONE_FLAT, STONE_STANDING, STONE_CAPSTONE }; -enum MOVE_DIRECTION { M_UP, M_DOWN, M_LEFT, M_RIGHT }; -enum E_RESULT { A_OK, A_ILLEGAL, A_OVERFLOW, - PTN_VALID, PTN_INVALID, - W_NONE, W_DRAW, W_DRAGON, - W_ROAD_WHITE, W_ROAD_BLACK, - W_FLAT_WHITE, W_FLAT_BLACK }; -#endif diff --git a/include/ptn.c b/include/ptn.c deleted file mode 100644 index 3d9c0a5..0000000 --- a/include/ptn.c +++ /dev/null @@ -1,156 +0,0 @@ -#include "ptn.h" - -#define ASSERT_NONEMPTY { if (ptn == 0 || *ptn == 0) return PTN_INVALID; } -#define ASSERT_MORE { if (*ptn == 0) return PTN_INVALID; } - -uint8_t -likely_move(char *ptn) { - if (ptn == 0) return 0; - for (;;ptn++) { - switch (*ptn) { - case '+': - case '-': - case '>': - case '<': return 1; - case 0: return 0; - } - } -} - -enum E_RESULT -parse_place(const uint8_t board_size, char *ptn, - uint8_t *out_location, enum STONE_VARIANT *out_stone) { - - if (board_size < 5 || board_size > 6) return PTN_INVALID; - - ASSERT_NONEMPTY; - - *out_stone = STONE_FLAT; - switch (*ptn) { - case 'C' : { ptn++; *out_stone = STONE_CAPSTONE; break; }; - case 'S' : { ptn++; *out_stone = STONE_STANDING; break; }; - case 'F' : { ptn++; break; }; - } - - ASSERT_MORE; - - if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; - *out_location = *ptn - 'a'; - - ptn++; ASSERT_MORE; - - if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; - *out_location += board_size * (*ptn - '1'); - - if (*(++ptn) > 0) return PTN_INVALID; - - return PTN_VALID; -} - -enum E_RESULT -parse_move(const uint8_t board_size, char *ptn, - uint8_t *out_location, enum MOVE_DIRECTION *out_direction, - uint8_t *out_steps, uint8_t out_drops[5]) { - - if (board_size < 5 || board_size > 6) return PTN_INVALID; - - ASSERT_NONEMPTY; - - uint8_t picked_up = 1; - - if ( (*ptn >= '1') && (*ptn <= '0' + board_size)) { - picked_up = *ptn - '0'; - ptn++; ASSERT_MORE; - } - - if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; - *out_location = *ptn - 'a'; - - ptn++; ASSERT_MORE; - - if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; - *out_location += board_size * (*ptn - '1'); - - ptn++; ASSERT_MORE; - - switch (*ptn) { - case '+': { *out_direction = M_UP; break; } - case '-': { *out_direction = M_DOWN; break; } - case '<': { *out_direction = M_LEFT; break; } - case '>': { *out_direction = M_RIGHT; break; } - default: return PTN_INVALID; - } - - ptn++; - // Handle the case '[1]<column><row><direction>' as - // '1<column><row><direction>1' for convenience - if (*ptn == 0) { - if (picked_up == 1) { - *out_steps = 1; - out_drops[0] = 1; - } else { - return PTN_INVALID; - } - } - - *out_steps = 0; - uint8_t total = 0; - while (*ptn) { - if ( (*ptn < '1') || (*ptn > '0' + board_size) ) { - return PTN_INVALID; - } - - if ( (*out_steps + 1 >= board_size) && *ptn) return PTN_INVALID; - - out_drops[*out_steps] = *ptn - '0'; - total += out_drops[*out_steps]; - *out_steps += 1; - ptn++; - } - - if ( total != picked_up ) return PTN_INVALID; - - return PTN_VALID; -} - -void -generate_place(const uint8_t board_size, const uint8_t in_location, - const enum STONE_VARIANT in_stone, char out_ptn[4]) { - switch (in_stone) { - case STONE_FLAT: { break; } - case STONE_STANDING: { *out_ptn = 'S'; out_ptn++; break; } - case STONE_CAPSTONE: { *out_ptn = 'C'; out_ptn++; break; } - } - *out_ptn = 'a' + (in_location % board_size); out_ptn++; - *out_ptn = '1' + (in_location / board_size); out_ptn++; - *out_ptn = 0; -} - -void -generate_move(const uint8_t board_size, const uint8_t in_location, - const enum MOVE_DIRECTION in_direction, - const uint8_t in_steps, const uint8_t in_drops[5], - char out_ptn[10]) { - uint8_t total = 0; - for (uint8_t k = 0; k<in_steps; k++) total+=in_drops[k]; - if (total > 1) { - *out_ptn = '0' + total; out_ptn++; - } - - *out_ptn = 'a' + (in_location % board_size); out_ptn++; - *out_ptn = '1' + (in_location / board_size); out_ptn++; - - switch (in_direction) { - case M_UP: { *out_ptn = '+'; break; } - case M_DOWN: { *out_ptn = '-'; break; } - case M_LEFT: { *out_ptn = '<'; break; } - case M_RIGHT: { *out_ptn = '>'; break; } - }; out_ptn++; - - - for (uint8_t k = 0; (total > 1) && (k < in_steps); k++) { - *out_ptn = '0' + in_drops[k]; out_ptn++; - } - - *out_ptn = 0; -} diff --git a/include/ptn.h b/include/ptn.h deleted file mode 100644 index fd154f9..0000000 --- a/include/ptn.h +++ /dev/null @@ -1,24 +0,0 @@ -#include <stdint.h> -#include "enums.h" - -uint8_t -likely_move(char *ptn); - -enum E_RESULT -parse_place(const uint8_t board_size, char *ptn, - uint8_t *out_location, enum STONE_VARIANT *out_stone); - -enum E_RESULT -parse_move(const uint8_t board_size, char *ptn, - uint8_t *out_location, enum MOVE_DIRECTION *out_direction, - uint8_t *out_steps, uint8_t out_drops[5]); - -void -generate_place(const uint8_t board_size, const uint8_t in_location, - const enum STONE_VARIANT in_stone, char out_ptn[4]); - -void -generate_move(const uint8_t board_size, const uint8_t in_location, - const enum MOVE_DIRECTION in_direction, - const uint8_t in_steps, const uint8_t in_drops[5], - char out_ptn[10]); diff --git a/include/state.c b/include/state.c deleted file mode 100644 index 94d0773..0000000 --- a/include/state.c +++ /dev/null @@ -1,315 +0,0 @@ -#include <state.h> - -// ------------------------------------------------------------------- -// Helpers - -#define NUM_SHIFT 4 -#define NUM_INC (0x1<<NUM_SHIFT) // 0b00010000 -#define NUM_MASK (0xF<<NUM_SHIFT) // 0b11110000 -#define STONE_MASK 0b00000011 -#define DFS_MASK 0b00001100 -#define USED_MASK 0b11110011 - -#define STONE_AT(l) (celldat[(l)] & STONE_MASK) -#define COUNT_AT(l) (celldat[(l)] >> NUM_SHIFT) - -#define THE_COORDS(x,y) ((x)+(y)*board_size) - -// ------------------------------------------------------------------- -// Game management - -void -reset_state(const uint8_t new_board_size) { - if (new_board_size == 6) { - board_size = 6; - white_flats = 30; black_flats = 30; - } else { - board_size = 5; - white_flats = 21; black_flats = 21; - } - white_caps = 1; - black_caps = 1; - - turn = 0; - current_colour = C_BLACK; - - for (uint8_t k = 0; k < board_size * board_size; k++ ) { - celldat[k] = 0; - } -} - -void -next_turn(void) { - turn++; - if (turn == 2) { - current_colour = C_WHITE; - } else { - if (current_colour == C_BLACK) current_colour = C_WHITE; - else current_colour = C_BLACK; - } -} - -// ------------------------------------------------------------------- -// Place stone - -enum E_RESULT -try_place(const int8_t location, const enum COLOUR colour, - const enum STONE_VARIANT stone) -{ - // Can't place on an occupied square - if (COUNT_AT(location)) { - return A_ILLEGAL; - } else { - switch (stone) { - case STONE_STANDING: ; - case STONE_FLAT: { - if (colour == C_BLACK) { - if (black_flats) black_flats--; - else return A_ILLEGAL; - } else { - if (white_flats) white_flats--; - else return A_ILLEGAL; - } - break; - } - case STONE_CAPSTONE: { - if (colour == C_BLACK) { - if (black_caps) black_caps--; - else return A_ILLEGAL; - } else { - if (white_caps) white_caps--; - else return A_ILLEGAL; - } - break; - } - } - - colours[location] = colour; - celldat[location] = NUM_INC | stone; - return A_OK; - } -} - -// ------------------------------------------------------------------- -// Move stack - -static void -push_stones(const int8_t location, const uint8_t count, const uint8_t new_colours, - const enum STONE_VARIANT top_stone) { - colours[location] = (colours[location] << count) | new_colours; - celldat[location] = ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK) | top_stone; -} - -static void -drop_stones(const int8_t location, const uint8_t count) { - // Calling this with count = 0 is destructive - colours[location] >>= count; - const uint8_t dec_count = celldat[location] - (count << NUM_SHIFT); - celldat[location] = dec_count & NUM_MASK; -} - -enum E_RESULT -try_move(const int8_t location, const enum MOVE_DIRECTION direction, - const uint8_t steps, const uint8_t drops[5]) { - // Can't do this - if (steps == 0 || steps > 5) return A_ILLEGAL; - - int8_t delta; - // Is the desired direction and count on the board? - switch (direction) { - case M_UP: { - delta = +board_size; - if (location + delta * steps > board_size * board_size) return A_ILLEGAL; - else break; - }; - case M_DOWN: { - delta = -board_size; - if (location + delta * steps < 0) return A_ILLEGAL; - else break; - }; - case M_RIGHT: { - delta = +1; - if (location + delta * steps > board_size * board_size) return A_ILLEGAL; - else break; - }; - case M_LEFT: { - delta = -1; - if (location + delta * steps < 0) return A_ILLEGAL; - else break; - }; - }; - - // For every square in the direction - uint8_t total = 0; - for (uint8_t k = 0; k < steps; k++) { - // Can't drop 0 anywhere because we're past the first square - if (drops[k] == 0) - return A_ILLEGAL; - // Can't drop more than BOARD_SIZE stones in a square - if (drops[k] > board_size) - return A_ILLEGAL; - // Check for overflows - if (COUNT_AT(location+(k+1)*delta) + drops[k] > 0x0F) - return A_OVERFLOW; - // Check for capstone - if (STONE_AT(location+(k+1)*delta) == STONE_CAPSTONE) - return A_ILLEGAL; - // Check for wall - if ( (STONE_AT(location+(k+1)*delta) == STONE_STANDING) - // If not last drop, or not dropping just one, or not a cap - && ( (k+1 < steps) - || (drops[k] != 1) - || (STONE_AT(location) != STONE_CAPSTONE) ) - ) - return A_ILLEGAL; - total += drops[k]; - } - - // Can't ask to move more than BOARD_SIZE or stones available - if ( (total > board_size) || (total > COUNT_AT(location)) ) - return A_ILLEGAL; - - // Nothing illegal, do it - uint8_t j = total; - for (uint8_t k = 0; k < steps; k++) { - j -= drops[k]; - push_stones(location+(k+1)*delta, - drops[k], - (colours[location] >> j) & (0xFFFF >> (0x10 - drops[k])), - (k == steps - 1) ? STONE_AT(location) : STONE_FLAT); - } - - drop_stones(location, total); - - return A_OK; -} - -// ------------------------------------------------------------------- -// Win conditions - -static uint8_t -board_full(void) { - for (uint8_t k; k < board_size*board_size; k++) { - if (COUNT_AT(k) == 0) return 0; - } - return 1; -} - -// direction == 0 --> left-to-right, otherwise --> top-to-bottom -static uint8_t -dfs_road(uint8_t dfs_stack[board_size*board_size], uint8_t dfs_pntr, - const enum COLOUR colour, const uint8_t direction) { - while (dfs_pntr > 0) { - const uint8_t cur = dfs_stack[--dfs_pntr]; - // Made it to the other side? - if (direction) { - if (cur >= board_size * (board_size - 1)) - return 1; - } else { - if (cur % board_size == 0) - return 1; - } - // Add neighbours of appropriate colour - if ( (cur + 1 < board_size * board_size) - && ((colours[cur+1] & 1) == colour) - && ((celldat[cur+1] & DFS_MASK) == 0) ) { - dfs_stack[dfs_pntr++] = cur + 1; - celldat[cur+1] |= DFS_MASK; - } - if ( (cur >= 1) - && ((colours[cur-1] & 1) == colour) - && ((celldat[cur-1] & DFS_MASK) == 0) ) { - dfs_stack[dfs_pntr++] = cur - 1; - celldat[cur-1] |= DFS_MASK; - } - if ( (cur + board_size < board_size * board_size) - && ((colours[cur+board_size] & 1) == colour) - && ((celldat[cur+board_size] & DFS_MASK) == 0) ) { - dfs_stack[dfs_pntr++] = cur + board_size; - celldat[cur+board_size] |= DFS_MASK; - } - if ( (cur >= board_size) - && ((colours[cur-board_size] & 1) == colour) - && ((celldat[cur-board_size] & DFS_MASK) == 0) ) { - dfs_stack[dfs_pntr++] = cur - board_size; - celldat[cur-board_size] |= DFS_MASK; - } - } - return 0; -} - -static enum E_RESULT -check_road_colour(const enum COLOUR colour) { - uint8_t dfs_stack[board_size * board_size]; - uint8_t dfs_pntr = 0; - - // Prime the depth-first-search stack with all boundary cells of - // colour COLOUR. - - const enum E_RESULT winner = - (colour == C_BLACK) ? W_ROAD_BLACK : W_ROAD_WHITE; - - // First left-to-right - for (uint8_t y=0; y<board_size; y++) { - if ( (colours[THE_COORDS(0, y)] & 1) == colour) { - dfs_stack[dfs_pntr++] = THE_COORDS(0, y); - celldat[THE_COORDS(0, y)] |= DFS_MASK; - } - } - if (dfs_road(dfs_stack, dfs_pntr, colour, 0)) return winner; - - // Then top-to-bottom - for (uint8_t x=1; x+1<board_size; x++) { - if ( (colours[THE_COORDS(x, 0)] & 1) == colour) { - dfs_stack[dfs_pntr++] = THE_COORDS(x, 0); - celldat[THE_COORDS(x, 0)] |= DFS_MASK; - } - } - if (dfs_road(dfs_stack, dfs_pntr, colour, 1)) return winner; - - return W_NONE; -} - -enum E_RESULT -check_win(void) { - // Do we do a flat count? - if (black_flats == 0 || white_flats == 0 || board_full()) { - int8_t total = 0; - for (uint8_t k = 0; k < board_size * board_size; k++) { - if (STONE_AT(k) == STONE_FLAT) { - total += ((colours[k] & 1) == C_BLACK) ? +1 : -1 ; - } - } - if (total > 0) { - return W_FLAT_BLACK; - } else if (total < 0) { - return W_FLAT_WHITE; - } else { - return W_DRAW; - } - } - - // Road? - - // We're using the two left-over bits in data_t to track whether - // we've seen it. Reset those before anything. No need to do it - // between checks, however, as pieces are black XOR white. - - for (uint8_t k=0; k<board_size*board_size; k++) { - celldat[k] &= USED_MASK; - } - - enum E_RESULT rb, rw; - rb = check_road_colour(C_BLACK); - rw = check_road_colour(C_WHITE); - - if (rb == W_ROAD_BLACK) { - if (rw == W_ROAD_WHITE) { - return W_DRAGON; - } else { - return W_ROAD_BLACK; - } - } else { - return rw; - } -} diff --git a/include/state.h b/include/state.h deleted file mode 100644 index 4f0528c..0000000 --- a/include/state.h +++ /dev/null @@ -1,25 +0,0 @@ -#include <stdint.h> -#include "enums.h" - -typedef uint16_t colour_stack_t; -typedef uint8_t data_t; - -uint8_t board_size; -data_t celldat[36]; -colour_stack_t colours[36]; -enum COLOUR current_colour; -uint8_t white_flats, black_flats, white_caps, black_caps, turn; - -void reset_state(const uint8_t new_board_size); -void next_turn(void); - -enum E_RESULT -try_place(const int8_t location, const enum COLOUR colour, - const enum STONE_VARIANT stone); - -enum E_RESULT -try_move(const int8_t location, const enum MOVE_DIRECTION direction, - const uint8_t steps, const uint8_t drops[5]); - -enum E_RESULT -check_win(void); diff --git a/src/ctaklm.c b/src/ctaklm.c index 885da7a..b343d11 100644 --- a/src/ctaklm.c +++ b/src/ctaklm.c @@ -1,7 +1,6 @@ #include <stdio.h> -#include <state.h> -#include <ptn.h> +#include <tak.h> int main(int argc, char **argv) { reset_state(5); |