13
\$\begingroup\$

Here's an advanced version of the Count the Liberties challenge.

The definitions of the terms liberty and group are the same as the previous challenge, so have a look at the previous one for details, but briefly put,

  • A group is a group of stones that are connected horizontally or vertically.
  • Liberty is the number of empty spaces connected horizontally or vertically to a group.

For example,

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

black's group (X) has 5 liberties, the upper group of white (O) has 2 liberties, and the lower group of white has 3 liberties.

For input, you will be given an 2D array of arbitrary size, in which each cell has one of black, white, or empty. You may map any value of any data type for black, white, and empty; but 1 value can be mapped to each.

All groups in the input will always have 1 or more liberties.

For output, the cells that had empty will be 0, and the cells that had black or white will be filled with the number of liberties of its group.

Examples

. . O .      0 0 2 0
. X X .  ->  0 5 5 0
. X . .      0 5 0 0
. O O .      0 3 3 0

. X . O  ->  0 2 0 1

X      1
X      1
.  ->  0
.      0
O      2
.      0

. X X .      0 3 3 0
X . X O  ->  2 0 3 2
X X O .      2 2 1 0

If you have participated in the previous challenge, having to count the liberties of multiple groups may require a quite different strategy.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ you should say that this is from the game of Go. Just for people to see some more sense behind it than just a competition for shortest code ;) \$\endgroup\$
    – Tomas
    May 18, 2022 at 11:55

8 Answers 8

4
\$\begingroup\$

05AB1E, 85 81 bytes

2FINi(}Θ©˜ƶIgäΔ2Fø0δ.ø}2Fø€ü3}®*εεÅsyøÅs«à]+ÐU˜ê¦©vyX®y†AS:¾1:'a0:4FJTx:€Søí}S2¢:

"If you have participated in the previous challenge, having to count the liberties of multiple groups may require a quite different strategy." That's an understatement, haha. This answer is almost 8 times as large as my 05AB1E answer for the related challenge. Although this is primarily because flood-filling is so expensive in 05AB1E; and the conversion I use is currently pretty verbose as well..

Uses -1/1 for O/X and 0 for empty spaces.

Try it online or verify all test cases.

Explanation:

Step 1: Flood-fill the individual islands. I've done this before in 05AB1E for this challenge (which actually contained a bug that I discovered thanks to the final test case here):

2F            # Loop 2 times (for each 1/-1 type of piece individually):
  I           #  Push the input-matrix
   Ni }       #  If the 0-based loop-index is 1:
     (        #   Negate all values
       Θ      #  Check which values are equal to 1 (maps 1→1; 0→0; -1→0)
        ©     #  Store this in variable `®` (without popping)
  ˜           #  Flatten it to a list
   ƶ          #  Multiply each value by its 1-based index
      ä       #  Convert it back to the matrix,
    Ig        #  using the input-length amount of rows
  Δ           #  Loop until it no longer changes to flood-fill:
   2Fø0δ.ø}   #   Add a border of 0s around the matrix:
   2F     }   #    Loop 2 times:
     ø        #     Zip/transpose; swapping rows/columns
       δ      #     Map over each row:
      0 .ø    #      Add a leading/trailing 0
   2Fø€ü3}    #   Convert it into overlapping 3x3 blocks: 
   2F    }    #    Loop 2 times again:
     ø        #     Zip/transpose; swapping rows/columns
      €       #     Map over each inner list:
       ü3     #      Convert it to a list of overlapping triplets
   ®*         #   Multiply each 3x3 block by the value in matrix `®`
              #   (so the 0s remain 0s)
   εεÅsyøÅs«à #   Get the largest value from the horizontal/vertical cross of
              #   each 3x3 block:
   εε         #    Nested map over each 3x3 block:
     Ås       #     Pop and push its middle row
       y      #     Push the 3x3 block again
        ø     #     Zip/transpose; swapping rows/columns
         Ås   #     Pop and push its middle rows as well (the middle column)
           «  #     Merge the middle row and column together to a single list
            à #     Pop and push its maximum
]             # Close the nested maps, flood-fill loop, and outer loop
 +            # Add the values in the two matrices together

Try just step 1 online.

Step 2: Loop over the individual islands, and convert all 0s to 1s; the current island to 0s; and all other islands to lowercase letters, as preparation for the next step:

Ð             # Triplicate the resulting matrix
 U            # Pop one, and save it in variable `X`
  ˜           # Flatten another one
   ê          # Sort and uniquify the values
    ¦         # Remove the leading 0
     ©        # Store these island-values in variable `®` (without popping)
v             # Loop over each island-value `y`:
  X           #  Push matrix `X`
   ®          #  Push list `®`
    y†        #  Filter the current island to the front
      AS      #  Push the lowercase alphabet as list
        :     #  Replace the island-values with letters
   ¾1:        #  Replace all 0s with 1s
   'a0:       #  Replace all "a" (the current island) with 0s

Try the first 2 steps online (with some added debug-lines).

Step 3: Use the same method as in the linked challenge to get the liberty-counts of each island:

  4F          #  Loop 4 times:
    J         #  Join the inner rows together to strings
     T        #  Push 10
      x       #  Double it (without popping): 20
       :      #  Replace all "10" with "20"
        €S    #  Convert each row back to a list again
          øí  #  Rotate the matrix 90 degrees clockwise:
          ø   #   Zip/transpose; swapping rows/columns
           í  #   Reverse each inner row
   }          #  Close the loop
    S         #  Convert the matrix to a flattened list of characters
     2¢       #  Count how many 2s are in this list

Try the first 3 steps online (again with added debug-lines).

Step 4: Convert the current island to this count in the matrix:

              # The matrix from the triplicate of step 2 is still on the stack
 y            #  Push island-value `y` from the still open loop of step 2
       :      #  Replace all of these islands with its count from step 3
              # (after which the resulting matrix is output implicitly)
\$\endgroup\$
4
\$\begingroup\$

APL(Dyalog Unicode), 43 bytes SBCS

Takes an integer matrix with 0 for blanks and any positive integer for a color (Supports any number of colors)

⍴⍴,+.<∘.(2>+⍥|.-)⍨⍤,⍤⍳⍤⍴∨.∧⍨⍣≡⍤∧,∘.(=≠0=⊣),

Try it on APLgolf!

The general strategy is to build an adjacency matrix for positions on the board, find the transitive closure, and, for each position with a color, count how many blank squares are connected to it. Some step-by-step results can be seen on APLgolf.

, Flatten the board matrix. To work with 2d adjacency matrices, we must represent the board in 1d. In the end ⍴⍴ will put the result into the correct shape.

,∘.(...), Create a matrix by applying the inner function between each pair of values:
= are the values equal (of same color)?
XOR
0=⊣ is the right one a zero.
This connects places of equal colors, and colored pieces to blank squares in one direction.

(2>+⍥|.-)⍨⍤,⍤⍳⍤⍴ adjacency matrix for horizontal and vertical neighbourhood on the grid.
,⍤⍳⍤⍴ Indices of the grid, flattened
(...)⍨⍤ Table for all pairs of these values
2>+⍥|.- Is the absolute distance less than 2?

The final adjancency table is generated by of the two matrices, then ∨.∧⍨⍣≡ finds the transitive closure (The matrix that has 1's where there is a valid path between two nodes)

,+.< Magic inner product, counting for each node on the grid, to how many blank spaces it is connected.

⍴⍴ Reshape the resulting flat vector into a matrix of the same shape of the input.

\$\endgroup\$
4
  • \$\begingroup\$ I'm having a hard time trying to understand what's goring on. I'm ready to spend many hours on it, but it would be so nice if you could explain a bit on how this works. \$\endgroup\$
    – xiver77
    May 18, 2022 at 16:16
  • \$\begingroup\$ @xiver77 I had a typo in the step-by-step runner, there was instead of , sorry for that. In general we treat the grid as a graph, where each field on the board is represented as a vertex. For vertices to be connected by an edge they have to be adjacent on the board. And all edges go either from a colored vertex to a vertex of the same color, or to a blank vertex (Note that this is a directed graph). Then the task is to find connected components, and count blanks in the connected component of a colored vertex \$\endgroup\$
    – ovs
    May 18, 2022 at 19:20
  • \$\begingroup\$ For understanding the algorithm, you'll have to understand adjacency matrices and know what the transitive closure of a graph is, if you have any specific questions feel free to ask \$\endgroup\$
    – ovs
    May 18, 2022 at 19:21
  • 1
    \$\begingroup\$ @xiver here is the graph that is constructed for your first example (this is the large case on the step-by-step link), maybe that helps \$\endgroup\$
    – ovs
    May 18, 2022 at 19:37
3
\$\begingroup\$

05AB1E, 37 bytes

Port of my APL answer. Really not the right language for the job but still slightly beats it.

˜©DδÊ®Ā^IāsнgLâDδαO2‹*ΔDøδ*OĀ}®›øOIgä

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice approach! I knew my answer was the wrong way to go after I saw how big the flood-fill algorithm already was, but still had fun making it, haha. ;) You can golf 1 byte by changing the first D to a triplicate Ð, and then changing the ®› to . \$\endgroup\$ May 17, 2022 at 18:58
3
\$\begingroup\$

JavaScript (ES7),  153 135 133  130 bytes

Expects a matrix of integers with \$0\$ for empty, \$1\$ for white, \$2\$ for black.

f=(m,V,X,Y,n=0,M=m.map((r,y)=>r.map((v,x)=>V?n+=V[k=[x,y]]|(x-X)**2+(y-Y)**2-1?0:(V[k]=1,v-V)?!v:f(m,V,x,y):f(m,[v],x,y))))=>V?n:M

Try it online!

How?

When defined, the parameter \$V\$ is a singleton array whose value is the reference color that triggered the recursion and whose underlying object is used to store the positions of the connected squares that were already visited.

On the initial call, we walk through the matrix and simply trigger a recursive call for each square \$v\$ at position \$(x,y)\$:

f(m, [v], x, y)

On subsequent calls, we receive \$V\$ along with the reference position \$(X,Y)\$. We walk through the matrix again, this time applying the following logic:

n +=                 // update the liberty counter n:
  V[k = [x, y]] |    //   if this square was already visited
  (x - X) ** 2 +     //   or the squared Euclidean distance between
  (y - Y) ** 2 - 1 ? //   (x, y) and (X, Y) is not equal to 1:
    0                //     do nothing
  :                  //   else:
    (                //   
      V[k] = 1,      //     mark this square as visited
      v - V          //     NB: V is coerced to an integer
    ) ?              //     if v is not equal to V:
      !v             //       increment n if v = 0
    :                //     else:
      f(m, V, x, y)  //       do another recursive call

NB: We do not prevent the recursion from starting when the reference square is empty. This is harmless because we simply flood-fill the empty space without updating \$n\$.

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

Python3, 510 bytes:

E=enumerate
def S(b,x,y):
 for X,Y in[(0,1),(0,-1),(1,0),(-1,0)]:
  try:
   if(A:=x+X)>=0 and(B:=y+Y)>=0:yield(A,B,b[A][B])
  except:1
def f(b):
 a,s=[],[]
 while(o:=[(x,y,c)for x,t in E(b)for y,c in E(t)if c in['X','O']and(x,y,c)not in s]):
  q,A=[o[0]],[]
  while q:x,y,c=q.pop(0);A+=[(x,y,c)];q+=[i for i in S(b,x,y)if i[-1]==c and i not in A]
  a+=[A];s+=A
 for i in a:
  for x,y,_ in i:b[x][y]=str(len({k for X,Y,_ in i for k in S(b,X,Y)if k[-1]=='.'}))
 return '\n'.join(map(' '.join,b)).replace('.','0')

Try it online!

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

Octave, 157 bytes

function E=f(B)
A=([W,k]=(l=@bwlabel)(B==1,4))+([R,n]=l(B>1,4))+k.*~~R;
E=0*B;
for x=1:n+k
E=E+(X=A==x)*nnz(conv2(X,[0 1 0;1 0 1;0 1 0],'same').*~B);
end
end

Try it online!

I suspect there are further improvements that can be made.

\$\endgroup\$
0
\$\begingroup\$

PARI/GP, 157 bytes

m->matrix(#m~,#m,i,j,p=0*m;a=p[i,j]=m[i,j];while(s=0;p!=q=matrix(#m~,#m,k,l,matrix(#m~,#m,u,v,normlp([u-k,l-v],1)<2&&p[u,v])&&!if(a-b=m[k,l],b||s++)),p=q);s)

Attempt This Online!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 88 bytes

WS⊞υι≔Eυ⟦⟧θFLυFL§υι«≔§§υικη≔⁰ζF№αη«Eυ⭆μ⎇⁼ξηψξJκι¤*FLυFL§υι«Jνμ≧⁺∧№KV*⁼KK.ζ»⎚»⊞§θιζ»Eθ⪫ιω

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings of letters (indicating a group) and . and outputs a list of strings of digits. Explanation:

WS⊞υι≔

Read the input array.

Eυ⟦⟧θ

Create an empty output array of the same height.

FLυFL§υι«

Loop over all of the cells in the array.

≔§§υικη

Get the current cell.

≔⁰ζ

Assume this cell is empty.

 F№αη«

If this cell is a letter, then:

Eυ⭆μ⎇⁼ξηψξ

Write the array to the canvas, but replacing that letter with the null character.

Jκι¤*

Fill the canvas with * starting at the current cell.

FLυFL§υι«

Loop over all of the cells again.

Jνμ≧⁺∧№KV*⁼KK.ζ

Keep a running total of any liberties found.

»⎚

Clear the canvas after counting the liberties ready for the next iteration or the output.

»⊞§θιζ

Save the result to the output array.

»Eθ⪫ιω

Output the final array of liberties. Note that this format smashes digits together so is only suitable for values up to 9 but the ω can be replaced with a separator character such as a space or comma.

\$\endgroup\$

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.