From 567db82c8988932fe27e695e6dbf0e3e7b1c020a Mon Sep 17 00:00:00 2001 From: tslil Date: Thu, 31 Dec 2020 20:07:21 -0500 Subject: Fixed road DFS errors --- include/tak.c | 106 ++++++++++++++++++++++++++++++++++------------------------ include/tak.h | 4 +-- src/ctaklm.c | 102 ++++++++++++++++++++++++++++--------------------------- 3 files changed, 117 insertions(+), 95 deletions(-) diff --git a/include/tak.c b/include/tak.c index 6bb11ec..7fa4f14 100644 --- a/include/tak.c +++ b/include/tak.c @@ -3,10 +3,12 @@ // ------------------------------------------------------------------- // Helpers -#define NUM_INC (0x1< board_size * board_size) return ACT_ILLEGAL; + if (location + delta * steps > NUM_SQUARES) return ACT_ILLEGAL; break; }; case M_DOWN: { @@ -122,7 +125,7 @@ try_move(const int8_t location, const enum MOVE_DIRECTION direction, }; case M_RIGHT: { delta = +1; - if (location + delta * steps > board_size * board_size) return ACT_ILLEGAL; + if (location + delta * steps > NUM_SQUARES) return ACT_ILLEGAL; break; }; default: // Why do i need this to satisfy GCC? @@ -183,46 +186,56 @@ try_move(const int8_t location, const enum MOVE_DIRECTION direction, static uint8_t board_full(void) { - for (uint8_t k = 0; k < board_size*board_size; k++) { + for (uint8_t k = 0; k < NUM_SQUARES; k++) { if (COUNT_AT(k) == 0) return 0; } return 1; } -// direction == 0 --> left-to-right, otherwise --> top-to-bottom +// direction == 0 --> left-to-right, direction == 1 --> bottom-to-top static uint8_t -dfs_road(uint8_t dfs_stack[board_size*board_size], uint8_t dfs_pntr, +dfs_road(uint8_t dfs_stack[NUM_SQUARES], 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) + if ( (direction == 1 && cur >= board_size * (board_size - 1)) + || (direction == 0 && cur % board_size == 1) ) return 1; - } - // Add neighbours of appropriate colour - if ( (cur + 1 < board_size * board_size) + + // Check the four neighbours of this cell, provided they exist, + // are inhabited, and are of the appropriate colour + + // Direction: > (same row) + if ( (cur + 1 < NUM_SQUARES) && ((cur + 1) % board_size > 0) + && (COUNT_AT(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 >= 1) + + // Direction: < (same row) + if ( (cur % board_size > 0) + && (COUNT_AT(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) + + // Direction: + + if ( (cur + board_size < NUM_SQUARES) + && (COUNT_AT(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; } + + // Direction: - if ( (cur >= board_size) + && (COUNT_AT(cur - board_size)) && ((colours[cur-board_size] & 1) == colour) && ((celldat[cur-board_size] & DFS_MASK) == 0) ) { dfs_stack[dfs_pntr++] = cur - board_size; @@ -234,8 +247,8 @@ dfs_road(uint8_t dfs_stack[board_size*board_size], uint8_t dfs_pntr, static enum E_RESULT check_road_colour(const enum COLOUR colour) { - uint8_t dfs_stack[board_size * board_size]; - uint8_t dfs_pntr = 0; + uint8_t dfs_stack[NUM_SQUARES]; + uint8_t dfs_pntr; // Prime the depth-first-search stack with all boundary cells of // colour COLOUR. @@ -243,18 +256,32 @@ check_road_colour(const enum COLOUR colour) { const enum E_RESULT winner = (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; + // We're using the two left-over bits in data_t to track whether + // we've seen it. Reset those before anything. + + for (uint8_t k=0; k 1) return check_win(); + next_ply(); + // Could be less conservative here :) + if (ply > 2) return check_win(); } return res; diff --git a/include/tak.h b/include/tak.h index 0a6fcf1..6773bcd 100644 --- a/include/tak.h +++ b/include/tak.h @@ -26,10 +26,10 @@ 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; +uint8_t white_flats, black_flats, white_caps, black_caps, ply; void reset_state(const uint8_t new_board_size); -void next_turn(void); +void next_ply(void); enum E_RESULT try_place(const int8_t location, const enum COLOUR colour, diff --git a/src/ctaklm.c b/src/ctaklm.c index dee1855..ad8ab6e 100644 --- a/src/ctaklm.c +++ b/src/ctaklm.c @@ -19,7 +19,7 @@ char *rst = "\033[0m"; #define CHAR_STN '/' #define CHAR_CAP '*' -void +static void put_stone(const enum STONE_VARIANT stone, const enum COLOUR colour, const uint8_t top, const uint8_t beyond_carry_limit) { if (beyond_carry_limit) { @@ -40,7 +40,7 @@ put_stone(const enum STONE_VARIANT stone, const enum COLOUR colour, fputs(rst,stdout); } -void +static void print_cell_line(const uint8_t line, const uint8_t col, const uint8_t row) { @@ -71,7 +71,7 @@ print_cell_line(const uint8_t line, } } -void +static void print_board_line(const uint8_t line) { const uint8_t mod = line % (SQUARE_H + 1), row = board_size - line/(SQUARE_H + 1) - 1; @@ -89,7 +89,7 @@ print_board_line(const uint8_t line) { if (line < board_size*(SQUARE_H+1)) { for (uint8_t x = 0; x < board_size; x++) { putchar('|'); - print_cell_line(line - 1 , x, row); + print_cell_line(mod - 1 , x, row); } puts("|"); } else { @@ -103,7 +103,14 @@ print_board_line(const uint8_t line) { } } -void +static void +print_board(void) { + for (uint8_t k = 0; k<=board_size*(SQUARE_H+1)+1; k++) { + print_board_line(k); + } +} + +static void print_square(const uint8_t col, const uint8_t row) { if (row < board_size && col < board_size) { printf("%c%c: ",'a'+col,'1'+row); @@ -129,55 +136,50 @@ int main(int argc, char **argv) { reset_state(5); - enum E_RESULT r = try_place(THE_COORDS(0, 4), C_WHITE, STONE_STANDING); print_square(0, 4); - r = try_place(THE_COORDS(1, 4), C_BLACK, STONE_CAPSTONE); print_square(1, 4); - uint8_t drops[5] = {1,0,0,0,0}; - r = try_move(THE_COORDS(1, 4), M_LEFT, 1, drops); print_square(0, 4); - - uint8_t location; - enum STONE_VARIANT stone; - r = parse_place(5, "Cb3", &location, &stone); - - printf("Place <%d>: stone %d at (%d,%d)\n",r != PTN_VALID,stone,location%5,location/5); - - enum MOVE_DIRECTION direction; - uint8_t steps; - r = parse_move(5, "1c2+", &location, &direction, &steps, drops); - - printf("Move <%d>: from (%d,%d) step %d sequence [%d,%d,%d,%d,%d]\n", - r != PTN_VALID,location%5,location/5, - steps,drops[0],drops[1],drops[2],drops[3],drops[4]); - - char buf[10]; - generate_move(5, 2+5*1, M_UP, 1, drops, buf); - printf("Generated move: %s\n",buf); - - generate_place(5,1+5*2, STONE_CAPSTONE, buf); - printf("Generated place: %s\n",buf); - - for (uint8_t k = 0; k<=board_size*(SQUARE_H+1)+1; k++) { - print_board_line(k); + for (uint8_t k = 0; k ")) != NULL) { - /* Do something with the string. */ - if (line[0] != '\0' && line[0] != '/') { - printf("echo: '%s'\n", line); - linenoiseHistoryAdd(line); /* Add to the history. */ - /* linenoiseHistorySave("history.txt"); /\* Save the history on disk. *\/ */ - } else if (!strncmp(line,"/historylen",11)) { - /* The "/historylen" command will change the history len. */ - int len = atoi(line+11); - linenoiseHistorySetMaxLen(len); - } else if (!strncmp(line, "/mask", 5)) { - linenoiseMaskModeEnable(); - } else if (!strncmp(line, "/unmask", 7)) { - linenoiseMaskModeDisable(); - } else if (line[0] == '/') { - printf("Unreconized command: %s\n", line); + while((line = linenoise("ctaklm> ")) != NULL) { + if (!strncmp(line,"board",6)) { + print_board(); + } else if (!strncmp(line,"square",6)) { + if (strnlen(line, 9) >= 9 + && line[7] >= 'a' && line[7] <= '`'+board_size + && line[8] >= '1' && line[8] <= '0'+board_size) { + print_square(line[7]-'a', line[8]-'1'); + } else { + printf("Usage: square [a-%c][1-%c]\n",'`'+board_size,'0'+board_size); + } + } else { + r = do_ptn(line); + printf("%d\n",r); + print_board(); } + + /* /\* Do something with the string. *\/ */ + /* if (line[0] != '\0' && line[0] != '/') { */ + /* printf("echo: '%s'\n", line); */ + /* linenoiseHistoryAdd(line); /\* Add to the history. *\/ */ + /* /\* linenoiseHistorySave("history.txt"); /\\* Save the history on disk. *\\/ *\/ */ + /* } else if (!strncmp(line,"/historylen",11)) { */ + /* /\* The "/historylen" command will change the history len. *\/ */ + /* int len = atoi(line+11); */ + /* linenoiseHistorySetMaxLen(len); */ + /* } else if (!strncmp(line, "/mask", 5)) { */ + /* linenoiseMaskModeEnable(); */ + /* } else if (!strncmp(line, "/unmask", 7)) { */ + /* linenoiseMaskModeDisable(); */ + /* } else if (line[0] == '/') { */ + /* printf("Unreconized command: %s\n", line); */ + /* } */ + free(line); } return 0; -- cgit v1.3.1