From 567db82c8988932fe27e695e6dbf0e3e7b1c020a Mon Sep 17 00:00:00 2001
From: tslil <tslil@posteo.de>
Date: Thu, 31 Dec 2020 20:07:21 -0500
Subject: Fixed road DFS errors

---
 include/tak.c | 106 ++++++++++++++++++++++++++++++++++------------------------
 1 file changed, 63 insertions(+), 43 deletions(-)

(limited to 'include/tak.c')

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<<NUM_SHIFT) // 0b00010000
-#define NUM_MASK   (0xF<<NUM_SHIFT) // 0b11110000
-#define DFS_MASK   0b00001100
-#define USED_MASK  0b11110011
+#define NUM_INC       (0x1<<NUM_SHIFT) // 0b00010000
+#define NUM_MASK      (0xF<<NUM_SHIFT) // 0b11110000
+#define DFS_MASK      0b00001100
+#define NOT_DFS_MASK  0b11110011
+
+#define NUM_SQUARES   (board_size * board_size)
 
 // -------------------------------------------------------------------
 // General state stuff
@@ -23,18 +25,18 @@ reset_state(const uint8_t new_board_size) {
   white_caps = 1;
   black_caps = 1;
 
-  turn = 0;
+  ply = 0;
   current_colour = C_BLACK;
 
-  for (uint8_t k = 0; k < board_size * board_size; k++ ) {
+  for (uint8_t k = 0; k < NUM_SQUARES; k++ ) {
     celldat[k] = 0;
   }
 }
 
 void
-next_turn(void) {
-  turn++;
-  if (turn == 2) {
+next_ply(void) {
+  ply++;
+  if (ply == 2) {
    current_colour = C_WHITE;
   } else {
     if (current_colour == C_BLACK) current_colour = C_WHITE;
@@ -54,7 +56,7 @@ try_place(const int8_t location, const enum COLOUR colour,
     return ACT_ILLEGAL;
   } else {
     switch (stone) {
-      case STONE_STANDING: ;
+      case STONE_STANDING: if (ply < 2) return ACT_ILLEGAL;
       case STONE_FLAT: {
         if (colour == C_BLACK) {
           if (black_flats) black_flats--;
@@ -66,6 +68,7 @@ try_place(const int8_t location, const enum COLOUR colour,
         break;
       }
       case STONE_CAPSTONE: {
+        if (ply < 2) return ACT_ILLEGAL;
         if (colour == C_BLACK) {
           if (black_caps) black_caps--;
           else return ACT_ILLEGAL;
@@ -112,7 +115,7 @@ try_move(const int8_t location, const enum MOVE_DIRECTION direction,
   switch (direction) {
     case M_UP:    {
       delta = +board_size;
-      if (location + delta * steps > 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<NUM_SQUARES; k++)
+    celldat[k] &= NOT_DFS_MASK;
+
   // First left-to-right
+  dfs_pntr = 0;
   for (uint8_t y=0; y<board_size; y++) {
-    if ( (colours[THE_COORDS(0, y)] & 1) == colour) {
+    if ( COUNT_AT(THE_COORDS(0, y)) &&
+        (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) {
+  // Clear visited squares
+  for (uint8_t k=0; k<NUM_SQUARES; k++)
+    celldat[k] &= NOT_DFS_MASK;
+
+  // Then bottom-to-top
+  dfs_pntr = 0;
+  for (uint8_t x=0; x<board_size; x++) {
+    if ( COUNT_AT(THE_COORDS(x, 0)) &&
+         (colours[THE_COORDS(x, 0)] & 1) == colour) {
       dfs_stack[dfs_pntr++] = THE_COORDS(x, 0);
       celldat[THE_COORDS(x, 0)] |= DFS_MASK;
     }
@@ -269,7 +296,7 @@ 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++) {
+      for (uint8_t k = 0; k < NUM_SQUARES; k++) {
         if (STONE_AT(k) == STONE_FLAT) {
           total += ((colours[k] & 1) == C_BLACK) ? +1 : -1 ;
         }
@@ -285,14 +312,6 @@ check_win(void) {
 
   // 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);
@@ -488,7 +507,7 @@ do_ptn(char *ptn) {
     res = parse_move(board_size, ptn, &location,
                      &direction, &steps, drops);
     if (res == PTN_VALID) {
-      if (turn < 2) return ACT_ILLEGAL;
+      if (ply < 2) return ACT_ILLEGAL;
       res = try_move(location, direction, steps, drops);
     }
   } else {
@@ -499,8 +518,9 @@ do_ptn(char *ptn) {
   }
 
   if (res == ACT_OK) {
-    next_turn();
-    if (turn > 1) return check_win();
+    next_ply();
+    // Could be less conservative here :)
+    if (ply > 2) return check_win();
   }
 
    return res;
-- 
cgit v1.2.3