22
\$\begingroup\$

Background

This challenge is about the Game of Go. Here are some rules and terminology relevant to this challenge:

  • Game of Go is a two-player game, played over a square board of size 19x19.

  • One of the players plays Black, and the other plays White. The game is turn-based, and each player makes a single move each turn, starting with Black. In the diagrams below, we use O for White and X for Black. Any other symbol is a blank.

  • A move consists of placing a new stone of the player's own color on an empty spot on the board.

  • Given a group of orthogonally connected stones of single color, the liberty is the number of empty positions orthogonally around it. For example, the following group has liberty of 7:

    . . . .
. O O .
. O . .
. . . .

    and the following configuration has two groups having liberties of 6 and 4 respectively:

    . . . . .
. O O . .
. . . O .
. . . . .

  • The opponent can reduce the liberty by placing their own stones around the target group. The following group of O has liberty 1 (the only empty adjacent position being a):

    . X X .
X O O X
X O X .
. a . .

  • If the Black places another black stone at a, the white group's liberty reduces to 0, where capture happens, and the white group is removed from the board.

  • A player cannot make a move where their own stone(s) would be captured, unless it is itself a capturing move. For example, the Black cannot make a move at a or b (where one or two black stones would be captured immediately), but they can make a move at c because it captures two White stones on its right.

    . . . . . O . . . O X .
. O . . O X O . O X O X
O a O . O b O . O c O X
. O . . . O . . . O X .

Finally, some terminology that is exclusive to this challenge:

  • A configuration is one or more groups of stones of the same color.
  • A configuration of White (color fixed for ease of explanation) is fully alive if Black cannot capture any of the given white stones even if arbitrarily many turns are given to Black.

Challenge

Given a Game of Go configuration, test if it is fully alive.

The input is a rectangular 2D array representing the state of the board, where each cell is either occupied (O in the example below) or empty (.).

  • You can choose any two distinct values to represent an occupied and an empty cell respectively.

  • You can assume the input is always rectangular, and contains at least one stone.

  • You can assume the input will always contain a margin of empty cells around the entire configuration of stones. For example, you don't need to handle this:

    O O O .
O . O O
. O . O
. . O O

    which will be given as the following instead:

    . . . . . .
. O O O . .
. O . O O .
. . O . O .
. . . O O .
. . . . . .

  • You may assume that the entire input (including the margin) will not exceed 19 rows and 19 columns.

  • For output, you can choose to

    1. output truthy/falsy using your language's convention (swapping is allowed), or
    2. use two distinct values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code wins.

Test cases

Truthy (fully alive)

. . . . . . .
. . O O O O .
. O . O . O .
. O O O O . .
. . . . . . .

. . . . . .
. O O . . .
. O . O O .
. O O . O .
. . . O O .
. . . . . .

. . . . . .
. . O O . .
. O . O O .
. O O . O .
. . O O . .
. . . . . .

. . . . . .
. O O . . .
. O . O . .
. O O . O .
. . O O O .
. . . . . .

Truthy since both eyes must be filled in order to capture any of the two groups
. . . . . . .
. . O O O . .
. O . . O O .
. O O O . O .
. . . O O . .
. . . . . . .

Ditto
. . . . . . . .
. . O O O . . .
. O . . O O O .
. O O O . . O .
. . . O O O . .
. . . . . . . .

. . . . . . .
. . O O O . .
. . O . . O .
. O . O O O .
. O O . O . .
. . . O O . .
. . . . . . .

. . . . . . .
. . . O O O .
. . . O . O .
. O O . O O .
. O . O . . .
. O O O . . .
. . . . . . .

. . . . . . . . .
. . O O O O O O .
. O . . O . . O .
. O . . O . . O .
. O O O O O O . .
. . . . . . . . .

Falsy (not fully alive)

. . .
. O .
. . .

. . . . .
. O O O .
. O . O .
. O O . .
. . . . .

. . . . . . . . .
. O O O . . O O .
. O . O . O . O .
. O O . . O O O .
. . . . . . . . .

. . . . . . .
. O O . O O .
. O . O . O .
. O O . O O .
. . . . . . .

The right group can be captured by Black, since Black doesn't need to fill
the upper area (of size 2) to capture it
. . . . . . .
. O O O . . .
. O . . O O .
. O O O . O .
. . . . O O .
. . . . . . .

The center singleton can be captured by Black
. . . . . . . . .
. . . O O O . . .
. O O O . O O O .
. O . . O . . O .
. O O O . O O O .
. . . O . O . . .
. . . O O O . . .
. . . . . . . . .

. . . . . . . . .
. . O O O O O O .
. O . . . O . O .
. O . . . O . O .
. O . . . O . O .
. O O O O O O . .
. . . . . . . . .

One part is fully alive but the other is not
. . . . . . . . . .
. O O O . . . O O .
. O . O O . O . O .
. . O . O . O O . .
. . O O . . . . . .
. . . . . . . . . .
Improve this question
\$\endgroup\$
13
  • \$\begingroup\$ I must be missing something obvious, but how is the capture made in Falsy case #2? \$\endgroup\$
    – Jonah
    Commented Mar 4, 2021 at 1:45
  • 1
    \$\begingroup\$ @Jonah ... Yes, OOO\\O.O\\OOO can be captured too. \$\endgroup\$
    – user202729
    Commented Mar 4, 2021 at 2:14
  • 1
    \$\begingroup\$ @Jonah .XXXXXXXX/XXOOOOOOX/XOXXXOXOX/XOX.XOXOX/XOXXXOaOX/XOOOOOOXX/XXXXXXXX. \$\endgroup\$
    – tsh
    Commented Mar 4, 2021 at 3:20
  • 1
    \$\begingroup\$ @Jonah To capture that group of White, you need to put Blacks on all the adjacent empty cells. Black can play this way to capture it: surround the white stones from the outside first, put 8 stones in the left inner region (except the center), and then put 3 stones in the right inner region. \$\endgroup\$
    – Bubbler
    Commented Mar 4, 2021 at 3:22
  • 1
    \$\begingroup\$ @tsh Black can capture White in that case, because Black doesn't need to fill up the four corners to capture it. (Remember, liberty in Game of Go uses four-way neighborhood) \$\endgroup\$
    – Bubbler
    Commented Mar 4, 2021 at 3:34

1 Answer 1

Reset to default
15
\$\begingroup\$

JavaScript, 178 bytes

(a,w,Q=(a,v)=>q=o=>a[o]?a[o]-v?0:[o+w,o-w,o+1,o-1].map(q,a[o]++).some(x=>x):a[o]=v/2)=>!a.some((c,i)=>c&&(E=Q(b=[...a],2)(i),b.map((d,j)=>d==1&&!Q([...b],1)(j)&&--b[E++,j]),E<3))


f=

(a,w,Q=(a,v)=>q=o=>a[o]?a[o]-v?0:[o+w,o-w,o+1,o-1].map(q,a[o]++).some(x=>x):a[o]=v/2)=>!a.some((c,i)=>c&&(E=Q(b=[...a],2)(i),b.map((d,j)=>d==1&&!Q([...b],1)(j)&&--b[E++,j]),E<3))



testcases = `
. . . . . . .
. . O O O O .
. O . O . O .
. O O O O . .
. . . . . . .

. . . . . .
. O O . . .
. O . O O .
. O O . O .
. . . O O .
. . . . . .

. . . . . .
. . O O . .
. O . O O .
. O O . O .
. . O O . .
. . . . . .

. . . . . .
. O O . . .
. O . O . .
. O O . O .
. . O O O .
. . . . . .

Truthy since both eyes must be filled in order to capture any of the two groups
. . . . . . .
. . O O O . .
. O . . O O .
. O O O . O .
. . . O O . .
. . . . . . .

Ditto
. . . . . . . .
. . O O O . . .
. O . . O O O .
. O O O . . O .
. . . O O O . .
. . . . . . . .

. . . . . . .
. . O O O . .
. . O . . O .
. O . O O O .
. O O . O . .
. . . O O . .
. . . . . . .

. . . . . . .
. . . O O O .
. . . O . O .
. O O . O O .
. O . O . . .
. O O O . . .
. . . . . . .

. . . . . . . . .
. . O O O O O O .
. O . . O . . O .
. O . . O . . O .
. O O O O O O . .
. . . . . . . . .

. . .
. O .
. . .

. . . . .
. O O O .
. O . O .
. O O . .
. . . . .

. . . . . . . . .
. O O O . . O O .
. O . O . O . O .
. O O . . O O O .
. . . . . . . . .

. . . . . . .
. O O . O O .
. O . O . O .
. O O . O O .
. . . . . . .

The right group can be captured by Black, since Black doesn't need to fill
the upper area (of size 2) to capture it
. . . . . . .
. O O O . . .
. O . . O O .
. O O O . O .
. . . . O O .
. . . . . . .

The center singleton can be captured by Black
. . . . . . . . .
. . . O O O . . .
. O O O . O O O .
. O . . O . . O .
. O O O . O O O .
. . . O . O . . .
. . . O O O . . .
. . . . . . . . .

. . . . . . . . .
. . O O O O O O .
. O . . . O . O .
. O . . . O . O .
. O . . . O . O .
. O O O O O O . .
. . . . . . . . .

One part is fully alive but the other is not
. . . . . . . . . .
. O O O . . . O O .
. O . O O . O . O .
. . O . O . O O . .
. . O O . . . . . .
. . . . . . . . . .

`.trim().split('\n').filter(x => !/[^\.O ]/.test(x)).join('\n').split('\n\n');
testcases.forEach(test => {
  grid = test.match(/[\.O]/g).map(v => v == 'O' ? 2 : 0);
  width = test.match(/(?<!\n.*)[\.O]/g).length;
  table = document.body.appendChild(document.createElement('table'));
  grid.forEach((v, i) => {
    if (i % width == 0) row = table.appendChild(document.createElement('tr'));
    ceil = row.appendChild(document.createElement('td'));
    ceil.textContent = v ? '◯' : '';
  });
  output = document.body.appendChild(document.createElement('output'));
  output.value = f(grid, width);
  document.body.appendChild(document.createElement('hr'));
});
// P=(a,n=[],o='')=>{for(i=0;i<w*w;i++){if(n[i])o+='+';else o+='.XO'[a[i]];if((i+1)%w==0){print(o);o=''}}}
table { font-family: monospace; table-layout: fixed; border-collapse: collapse; }
table, tr, td { padding: 0; border: 0; }
td { line-height: 22px;width: 22px; height: 22px; text-align: center;
background: linear-gradient(to bottom, transparent 0, transparent 10px, #80808080 10px, #80808080 11px, transparent 11px, transparent 100%), linear-gradient(to right, transparent 0, transparent 10px, #80808080 10px, #80808080 11px, transparent 11px, transparent 100%); }

Input two parameters. First one is the board. The board is an 1d array, 2 for white, 0 for empty. Second one is its width, an integer.

Details (with comments):

(a, // input board as 1d array; 2 = white; 0 = empty
 w, // input width of board
 Q= // test if some stones on board `a` is alive
 (a, // board to test
  v  // color of stone to test
 )=>q=o=> // stone to test (when invoke by outside, a[o]==v always hold)
 /*
    We modify the board in-place. So caller need to duplicate a board if it requires the original one.
    For input, we test if stones with color `v` connected to `a[o]` has at least 1 liberty.
    And we modify connected stones by +1; modify all liberty by +v/2
    Here, {0, v/2, v} should / would not be equal.
  */
   a[o]? // If current ceil is not a liberty
    a[o]-v?
     0: // If current stone is something already visited or with wrong color (opposite color)
        // It is not a liberty, we return 0
     // If current ceil is connected stone which never visited
     [o+w,o-w,o+1,o-1].map(q, // visit all its neighbors
       a[o]++ // modify current ceil to remeber we had visited it
     ).some(x=>x): // Is there any liberty?
    a[o]=v/2 // Current ceil is a liberty; mark it as visited, also return something truthy
)=>
  !a.some( // Try to find out any stones may be captured
   (c, // stone on board
    i // position of stone
   )=>c&& // current ceil is white stone (not empty)
   (E= // Initial E to true (1)
       // Input only contains white, and have an empty border
       // So every white stones on inputed board has liberty as we known
       // And Q(...)(...) would always return true
       // We use this value to initialize variable E
    Q(
      b=[...a], // b is a duplicate of board, also used later
      2 // White = 2
    )(i),
    b.map( // Try to find some black (black = 1 here) stones without liberty
      (d,j)=>
       d==1&& // Current ceil is black
       !Q([...b],1)(j)&& // Current ceil has no liberty
       --b[
       E++, // We found a real eye for white, count it
       j] // Pick current black stone up, as it should be placed as final move
    ),
    E<3 // If white stones has less than 2 real eyes
        // (E is initialized to 1, so E<3 means less than two E++ happened)
        // we would be able to capture these white stones
        // thus, we found some white stones not fully alived
  ))
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can save a byte by using for..of instead of .forEach \$\endgroup\$
    – user81655
    Commented Mar 5, 2021 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.