Thank you for all those interesting and helpful ideas. Another approach I was implementing didn't go well, so I'll definitely have a serious read of the replies.
Although it failed, it was interesting enough that I'd like to share the idea. It's not my idea. I got it from
here.
The code is this single line of APL.
Code:
⍴⍴,+.<∘.(2>+⍥|.-)⍨⍤,⍤⍳⍤⍴∨.∧⍨⍣≡⍤∧,∘.(=≠0=⊣),
For an input of,
Code:
|0 1 0│
│2 1 0│
│0 2 0│
the output is,
Code:
│0 3 0│
│2 3 0│
│0 2 0│
The positive integers in the input each represents a color mapped to a single positive integer, and there could be more than 2 colors.
The output is the liberty count for all groups in the arbitrarily sized input board.
Since the given input has 3x3 = 9 entries, we will do some operations with 9x9 boolean matrices.
(step-1) The first boolean matrix is the adjacency matrix defining solid connection between stones.
Code:
│1 1 0 1 0 0 0 0 0│
│1 1 1 0 1 0 0 0 0│
│0 1 1 0 0 1 0 0 0│
│1 0 0 1 1 0 1 0 0│
│0 1 0 1 1 1 0 1 0│
│0 0 1 0 1 1 0 0 1│
│0 0 0 1 0 0 1 1 0│
│0 0 0 0 1 0 1 1 1│
│0 0 0 0 0 1 0 1 1│
(step-2) The second boolean matrix is the adjacency matrix that connects the stones of the same color and connects all empty points to all stones.
Code:
│0 1 0 1 1 0 0 1 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 1 1 0 0 1 0│
│0 0 0 1 0 0 0 1 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 1 1 0 0 1 0│
│0 1 0 1 1 0 0 1 0│
│0 0 0 1 0 0 0 1 0│
│0 1 0 1 1 0 0 1 0│
(step-3) Do a bitwise-and of these matrices.
Code:
│0 1 0 1 0 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 0 0 0 0 0 0│
│0 0 0 1 0 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 0 0 0 1 0 0 0 0│
│0 0 0 1 0 0 0 1 0│
│0 0 0 0 0 0 0 1 0│
│0 0 0 0 0 0 0 1 0│
(step-4) Compute the
transitive closure of step-3. I honestly have no idea what this is, but to compute this we have to do ∨.∧ with two step-3 matrices. ∨.∧ is the inner product of bitwise-and and bitwise-or. In other words, it's a generalized matrix multiplication with multiplication changed to bitwise-and and addition change to bitwise-or.
Code:
│0 1 0 1 1 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 0 0 1 0 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 0 0 1 0 0 0 1 0│
│0 0 0 0 0 0 0 1 0│
│0 0 0 0 0 0 0 1 0│
(step-5) Count the liberties by applying ,+.< to step-4. I haven't investigated what this is yet because I couldn't think of an efficient way to do step-4.
Code:
│0 3 0 2 3 0 0 2 0│
I'm currently dealing with 4x8 boards, and this will produce a 32x32 boolean matrix for each step. I actually wrote reasonable AVX optimized code up to step-3. However, the
inner product (∨.∧) operation scales badly as the input size gets bigger.
Although it may not be the fastest solution, I still think it's somewhat elegant.