15
\$\begingroup\$

Background

This challenge is about the game of Go. Go is a game played on a board with a square grid N x N. You don't have to know how to play the game to do this challenge, but if you are interested, google "Tromp-Taylor rules" for a minimal and precise set of rules to play a full game.

Let's use a 4 x 4 board. As the game starts, two players, black (X) and white (O), alternately place a stone on an empty grid starting with black.

At some point of the game, the board may look like this.

. . O .
. X X .
. X . .
. O O .

Black has 1 group, and white has 2 groups. A group is a group of stones that are connected horizontally or vertically.

. X X .
X . X .
X X . .
. . X X

Black has 3 groups on this board.

. . O .
. X X .
. X . .
. O O .

Back to the first example, the upper group of white has 2 liberties and the lower group of white has 3 liberties. Liberty is the number of empty spaces connected horizontally or vertically to a group.

X . O X
. . . .
. . . O
. . O X

There are 3 black groups on this board each with 2, 1, and 0 liberties. In an actual game a group with 0 liberties are taken out of the board, but you don't have to care about that in this challenge.

Challenge

The input is a 4 x 4 Go board position, where there is 1 black group and any number of white groups.

The output is the number of liberties that the black group has.

The input can be encoded in any way that can hold \$3^{4\times4}\$ distinct values.

The output is an integer, when optionally printed, up to base 16.

Examples

. . . .
. X . .
. . . .
. . . .  ->  4

. . . .
. X X .
. . . .
. . . .  ->  6

X X . .
X . . .
. . . .
. . . .  ->  3

X X O .
X O . .
O . . .
. . . .  ->  0

. X X .
. X . X
. X X X
. . . .  ->  8

O X X .
O X . X
O X X X
. O O O  ->  2

O X X O
O X O X
O X X X
. O O O  ->  0

The last case is an impossible position in the actual game, but it is valid for this challenge.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ I know this probably sounds ridiculous, but can I take a 36-element flat-list consisting of 6 rows and 6 columns (flattened), where the elements number (1-indexed) 8-11, 14-17, 20-23, 26-29 are the 16 elements that actually matter, and the rest are zeroes? \$\endgroup\$
    – ophact
    Mar 11 at 8:17
  • 1
    \$\begingroup\$ @ophact Since your input "can hold 3^16 distinct values", that should be fine. \$\endgroup\$
    – xiver77
    Mar 11 at 8:19
  • 1
    \$\begingroup\$ "The input can be encoded in any way that can hold \$3^{4\times4}\$ distinct values."—surely this can't be meant literally, since one such encoding involves each board state accompanied by the answer to this very challenge?! \$\endgroup\$ Mar 13 at 10:15
  • \$\begingroup\$ @GregMartin would putting "up to" make sense? \$\endgroup\$
    – xiver77
    Mar 13 at 10:17
  • \$\begingroup\$ @GregMartin No.. it doesn't, then what do you think is a better sentence to prevent something like you said? You can edit directly if you want. \$\endgroup\$
    – xiver77
    Mar 13 at 10:18

9 Answers 9

8
\$\begingroup\$

MATL, 10 bytes

~Go1Y6Z+*z

Try it online!

Takes input as a \$4\times 4\$ matrix with 0 representing an empty point, a 1 representing a black stone, and a 2 representing a white stone.

Bonus, contains Go!

        % implicit input M
~       % logically negate: push matrix of 1s where there are empty points
Go      % Push matrix, mod 2: get matrix of 1s where black stones are
1Y6     % Push [0 1 0; 1 0 1; 0 1 0], the matrix of adjacencies
Z+      % two-dimensional convolution maintaining size
*z      % multiply and count the number of nonzero entries.
        % (implicit) convert to string and display
\$\endgroup\$
0
4
\$\begingroup\$

BQN, 19 bytesSBCS

Takes input as an integer matrix with 1 for empty squares, 2 for white and 3 for black stones.

+´∘⥊1⊸=∧3=«˘⌈»˘⌈»⌈«

Run online!

«˘⌈»˘⌈»⌈« Shift the matrix by one from each of the four directions and take the element-wise maximum.
3= For each value in this new matrix, is it equal to 3? This gives 1 for each square adjacent to a black stone on the board.
1⊸=∧ And is the square empty?
+´∘⥊ Count the 1's by summing.

\$\endgroup\$
1
  • \$\begingroup\$ Those built in rotation directions are slick. \$\endgroup\$
    – Jonah
    Mar 11 at 6:23
3
\$\begingroup\$

Wolfram Language (Mathematica), 56 bytes

Count[ListConvolve[{r={0,1,0},1-r,r},#,2,0]^#,_.+_.a,2]&

Try it online!

Takes input as a 2d array, with 1 for empty, 0 for white, a for black.

\$\endgroup\$
1
  • \$\begingroup\$ No cellular automata? MMA expression manipulating is better than CA tho \$\endgroup\$
    – null
    Mar 11 at 5:46
2
\$\begingroup\$

Retina 0.8.2, 75 26 bytes

(?<=X....|X)_|_(?=X|....X)

Try it online! Link includes test suite that converts from double-spaced newline-delimited examples using . to comma-delimited strings using _. Works with boards of any height. Explanation: Counts the number of _s which are either adjacent or exactly 5 characters away from an X (which represents one directly above or below).

Edit: Saved 49 bytes thanks to @tsh by hard-coding the size of the board. Previous 75-byte answer works on any rectangular size of board:

(?<=X|X(?(1)$)(?<-1>.)*¶.*(?=.(.)*))_|_(?=X|(?<=(.)*.).*¶(?<-2>.)*(?(2)^)X)

Try it online! Link includes test suite that accepts double-spaced examples using . although code requires _. Explanation: Uses .NET balancing groups to count the number of _s with any X that is adjacent to the left, above, right or below respectively.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I don't know how to speak Retina. But maybe (?<=X....|X)_|_(?=X|....X)? \$\endgroup\$
    – tsh
    Mar 11 at 4:08
  • \$\begingroup\$ @tsh Ah, by hardcoding the size in? Yeah, I guess that works. \$\endgroup\$
    – Neil
    Mar 11 at 8:30
1
\$\begingroup\$

Vyxal, 14 bytes

4(36₄vV§↵R)∑2O

Try it Online!

Messy port of Kevin Cruijssen's 05AB1E answer.

Two things increase the byte count of this:

  • We have to explicitly vectorise replace (V)
  • Transposing creates a character matrix, so we use a more convoluted method.
4(        )    # Four times...
  36₄vV        # Replace 36 with 26
       §↵R     # Rotate 90°
           ∑2O # Count the 2s in the result.
\$\endgroup\$
1
\$\begingroup\$

05AB1E (legacy), 12 11 bytes

4FTx:øí}J2¢

-1 byte thanks to @emanresu

Takes a list of strings as input, with 1 for empty spots; 0 for black; and just O (could be any character besides 012) for white.

Try it online or verify all test cases.

Explanation:

Uses the legacy version of 05AB1E, because it can zip/transpose on a list of strings, where the new version would require character-matrices. In the new version the ø would be €SøJ (convert each to a character-list; zip/transpose; join back to strings), so using the legacy saves 3 bytes here.

4F     # Loop 4 times:
  T    #  Push 10
   x   #  Double it (without popping): 20
    :  #  Replace all "10" to "20" in the strings of the list
       #  (which uses the implicit input-list in the first iteration)
  øí   #  Rotate the 4x4 block once clockwise:
  ø    #   Zip/transpose; swapping rows/columns
   í   #   Reverse each inner row
 }J    # After the loop: join to have a single string
   2¢  # Count how many 2s are in this string
       # (after which it is output implicitly as result)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you use Tx instead to save a byte? \$\endgroup\$
    – emanresu A
    Mar 11 at 8:50
  • \$\begingroup\$ @emanresuA Ah, I indeed can. I was looking for 2 single-byte integers with overlapping digit, but didn't think about Tx. Thanks. \$\endgroup\$ Mar 11 at 8:57
1
\$\begingroup\$

Charcoal, 35 32 bytes

≔⪫E⁴S⸿θPθ≔⁰ηFθ«≧⁺∧№KVX⁼KK.ηι»⎚Iη

Try it online! Link is to verbose version of code. Only works for boards of height 4, but accepts any width (including variable width). Explanation:

≔⪫E⁴S⸿θ

Input the board. (Save 7 bytes if a JSON string with each line delimited by carriage returns is an acceptable input format, in which case this works for any size of board.)

Pθ

Output the board without moving the cursor.

≔⁰η

Start with 0 liberties.

Fθ«

Loop over the string.

≧⁺∧№KVX⁼KK.η

Increment the number of liberties if this is a . with at least one orthogonally adjacent X.

ι

Move to the next character.

»⎚Iη

Clear the canvas and output the final count of liberties.

Edit: Saved 3 bytes by hard-coding the size of the board as suggested by @tsh on my Retina answer. Previous 35-byte answer works for any size of board in human-readable format:

WS⊞υι≔⪫υ⸿θPθ≔⁰ηFθ«≧⁺∧№KVX⁼KK.ηι»⎚Iη

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation: WS⊞υι≔⪫υ⸿θ converts the input into a single carriage-return delimited string, after which the remaining 25 bytes are the same.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 121 112 90 bytes

def l(b,n=0):
 for i in range(36):
  if b[i]>0==b[i-1]*b[i+1]*b[i-6]*b[i+6]:n+=1
 return n

Edit -9 bytes: @LeopardShark outgolfed me with another Python3 answer, but luckily I was able to golf my code 1 byte lower than theirs, albeit by abusing lax input restrictions even more: the flattened 6x6 list is now lengthened to a 68 item list, where the first 32 items are total junk, and simply space the indices out properly.

Edit -22 bytes: @LeopardShark's 73 byter made me realize I could actually use range(36) instead of my solution iterating over a string with ord(), plus a few tweaks to the conditional, brings this down to 90 bytes, which is I think as short as I can get this code without wholesale copying LeopardShark's solution using sum(). But hey! at least the input doesn't need 32 garbage entries at the start of the list anymore.

I feel like there's way better ways to do this, but both getting the right range to iterate on and evaluating the conditional stumped me as to shorter ways than this.

Takes input as an list of length 36, representing a flattened 6x6 grid, where only the central 4x4 actually holds useful data. Black pieces are marked with 0, whites with -1, and empty spaces with 1. The "padding" on the exterior is also filled with -1.

The program just loops through each square in the board, and checks if any of the four adjacent squares are equal to 0. If it is, that square is a liberty, and a counter is incremented.

Working TIO link with test cases now that I've removed the walrus

\$\endgroup\$
1
\$\begingroup\$

Python 3, 71 bytes

lambda p:sum(p[x+1]+p[x-1]+p[x+6]+p[x-6]>8 for x in range(36)if p[x]<1)

This checks each cell next to a blank one to look for a black stone.

It takes its input as an array of 36 1 (white), 9 (black) and 0 (empty), with the board surrounded by 1.

This was much longer (113 B), but des54321’s 6×6 input strategy helped to shorten it.

Thanks to Chris for pointing out that f= was unnecessary.

Try it online!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ +1 for outgolfing me, but I think I've got something that just beats you lined up ;) \$\endgroup\$
    – des54321
    Mar 11 at 23:56
  • 1
    \$\begingroup\$ @des54321 So did I! 6×6 is very helpful, it turns out. \$\endgroup\$ Mar 12 at 0:07
  • 1
    \$\begingroup\$ oh wow 73!! I figured out how to golf off another 5 bytes off mine, but its gonna take me more thought to beat this score \$\endgroup\$
    – des54321
    Mar 12 at 0:17
  • 1
    \$\begingroup\$ This is 71 bytes if you remove the f=: anonymous lambda's are perfectly legitimate. I usually put the f= in the header part for the test cases so it doesn't show in the code or count towards the byte count: Try it online! \$\endgroup\$
    – Chris
    Mar 13 at 1:06
  • 1
    \$\begingroup\$ Maybe a little late. But you can remove the space between 8 and for \$\endgroup\$
    – friddo
    Mar 15 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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