Make a move on a Go board

Question

You are given a board position for a Go game and a move to play. You need to output whether the move is legal or not, and the new board position if it is legal.

A brief explanation of Go moves: the game consists of alternatively placing black and white pieces ("stones") in empty places on a square board. Sets of pieces of the same color that are connected to each other (4-way) are called groups. Empty places on the board that are adjacent to a group (also 4-way) are considered to be that group's "liberties". A group with 0 liberties is captured (removed from the board). A move that would cause its own group to be captured ("suicide") is illegal, unless it is capturing one or more opponent's groups (gaining liberties in the process so it is not actually captured).

For those concerned, you don't need to deal with ko (and superko), i.e. you can assume a ko capture is legal. If you don't know what that means, just follow the rules above and it will be fine.

Input: a number n between 2 and 19 (inclusive) representing the board size, followed by n lines of n numbers between 0 and 2 (inclusive) representing the board position, followed by 3 numbers separated by space, representing the move to make. In the board position, 0 means empty place, 1 means black stone and 2 means white stone. The move gives the column, the row and the color (1 or 2) of the stone to place. The column and row are 0-based, ranging from 0 to n-1 (inclusive) and counted in the same order as the board input.

You can assume that the given board position is legal (all groups have at least one liberty).

Output: a line containing 1 or 0 (or true/false if you prefer) if the move is legal or not, followed (only in case of a legal move) by the new board position in the same format as the input.

Score: Number of bytes of the complete source code, smaller is better. 20% additional penalty for use of non-ascii characters, and 20% additional penalty if your code can't be tested in Linux using freely available software.

Rules: No network connections and no 3rd party libraries. Your program should use the standard input and output streams, or the standard equivalent for your programming language.

Examples:

1) Input:
2
10
01
1 0 2
Output:
0
2) Input:
2
10
11
1 0 2
Output:
1
02
00
3) Input:
5
22122
22021
11211
02120
00120
2 1 1
Output:
1
00100
00101
11011
02120
00120
4) Input:
6
000000
011221
121121
122221
011110
000000
4 0 1
Output:
1
000010
011221
121121
122221
011110
000000

Answer 1

Python 3 ((削除) 557 (削除ここまで) (削除) 504 (削除ここまで) 488)

import sys
s=sys.stdin
M=int(next(s))+1
j=Z=M*M-M
S=s.read(Z)
P=0
b=[0]*3
while j>0:j-=1+(j%M<1);b[int(S[j])]|=1<<j;P|=1<<j
N=lambda x:(x<<1|x>>1|x<<M|x>>M)&P&~x
def h(a,b):t=a|N(a)&b;return h(t,b)if t!=a else a
c,r,m=map(int,next(s).split())
o=m%2+1
p=1<<M*r+c
b[m]|=p
for n in(p<<1,p>>1,p<<M,p>>M):
 e=h(n&P,b[o])
 if~b[m]&N(e)<1<=n&b[o]:b[o]&=~e
_,B,W=b
g=~b[o]&N(h(p,b[m]))>=1>~_&p
print(+g)
q=''
while j<Z:
 r=1<<j
 if g*j%M>M-2:print(q);q=''
 else:q+='012E'[(r&B>0)+(r&W>0)*2]
 j+=1

Uses 3 bitfields to represent the board - one each for black, white, and empty spaces. Makes the find neighbors N and get chain h operations very concise.

An ungolfed version with lots of comments: https://gist.github.com/airfrog/8429006

• aditsu quit because SE is EVIL: You have a LOT of spaces at the end of each line, the file as you posted it has 2732 bytes.
• airfrog: @aditsu That should be fixed now
• aditsu quit because SE is EVIL: Size is still wrong, should be 555 now :) Also I wonder if you can still save a few bytes by using more semicolons.
• aditsu quit because SE is EVIL: Bug? Input: 6 000000 011221 121121 122221 011110 000000 4 0 1 Output: 0. Added now as example 4.
• airfrog: That bug is fixed, I also found and fixed another bug while golfing it that you may want to add as an example. Input: 5 22100 20211 12211 12120 01120 1 1 2 Output should be 0.

Answer 2

Python ((削除) 912 (削除ここまで)1004)

def o():
 n=int(raw_input(''))
 i=[raw_input('') for r in range(n+1)]
 b=[map(int,list(r)) for r in i[:n]]
 u,v,w=map(int,i[n].split(' '))
 if b[v][u]!=0:return 0
 b[v][u]=w
 if w==1:q=2
 elif w==2:q=1
 else:return 0
 f=[[],[],[]]
 h=[[],[],[]]
 g=[range(z*n,(z+1)*n) for z in range(n)]
 d=[(1,0),(-1,0),(0,1),(0,-1)]
 m=lambda z:max(0,min(n-1,z))
 t=[0,1,2,0,1]
 for j,s in enumerate(t):
 for r in range(n):
 for c in range(n):
 for y,x in map(lambda p:(m(r+p[0]),m(c+p[1])),d):
 if s==0:
 if b[y][x]==b[r][c]:
 if g[y][x]!=min(g[y][x],g[r][c]):
 t.insert(j+1,0)
 g[y][x]=g[r][c]=min(g[y][x],g[r][c])
 elif s==1:
 if g[r][c] not in h[b[r][c]]:
 h[b[r][c]].append(g[r][c])
 if b[y][x]==0 and g[r][c] not in f[b[r][c]]:
 f[b[r][c]].append(g[r][c])
 if s==2:
 if b[r][c]==q and g[r][c] not in f[b[r][c]]:
 b[r][c]=0
 h[w].sort()
 f[w].sort()
 if h[w]!=f[w]:return 0
 return "1\n"+'\n'.join([''.join(map(str,r)) for r in b])
print o()

Walk through: parse input, check if move is on an empty spot, make move, init "group" grid, simplify/minimize group grid by checking color of adjacant stones (s=0) and keep repeating until it is fully minimized, check for group liberties (s=1), remove opponent stones for groups with no liberties (s=2), repeat s=0 and s=1, check that all player groups have liberties, return result.

This can probably be shortened significantly...

(削除) Interactive (削除ここまで) Example runs:

2
10
01
1 0 2
0
2
10
11
1 0 2
1
02
00
5
22122
22021
11211
02120
00120
2 1 1
1
00100
00101
11011
02120
00120
6
000000
011221
121121
122221
011110
000000
4 0 1
1
000010
011221
121121
122221
011110
000000

• aditsu quit because SE is EVIL: Your program doesn't do anything, it only defines a function.
• jur: Run it interactively and call it with print o() as shown in the example run...
• aditsu quit because SE is EVIL: Nope. It is supposed to be a standalone program that you run from the command line. Besides, that would also make it shorter.
• jur: Fixed it by adding print o() on the last line
• aditsu quit because SE is EVIL: Why not just use the function body (outdented)? And I think you also fail the newly added example 4.

Answer 3

Python 3.8: (削除) 480 (削除ここまで) (削除) 479 (削除ここまで) (削除) 424 (削除ここまで) (削除) 359/366 (削除ここまで) 344/351 bytes

Inspired by airfrog's accepted answer. Try it online!

o=open(0)
r=o.read
m=int(o.readline())+1
C=[*r(m*m-m)]+[' ']*m
y,x,c=map(int,r().split())
N=lambda p:[p+1,p-1,p+m,p-m]
p=x*m+y
C[p]=c
s=lambda P,c:[S(P,'0'),any((C[R]=='0')|(t[R]==str(c)and[S(R,'0'),s(R,c)][1])for R in N(P))][1]
for P in N(p):
 if C[P]==str(3-c):t=C[:];S=t.__setitem__;s(P,3-c)or(C:=t[:])
print(n:=s(p,c))
if n:print(*C,sep='')

(change last line to if n:print(*C[-m-1],sep='') if trailing spaces not allowed)

Older/slightly-different ungolfed version with comments:

from copy import deepcopy
n = int(input())
in_ = lambda x,y: x>=0 and x<n and y>=0 and y<n
neighbors = lambda x,y: [(x+dx, y+dy) for dx, dy in ((0,1),(0,-1),(1,0),(-1,0)) if in_(x+dx,y+dy)]
chars = [[*map(int, input())] for i in range(n)]
y,x,c = map(int, input().split())
chars[x][y] = c
def search(xx,yy,c):
 global chars
 tmp = deepcopy(chars)
 cue = [(xx, yy)]
 tmp[xx][yy] = 0
 nolib = True # no liberty?
 while cue:
 xx,yy = cue.pop()
 for xxx,yyy in neighbors(xx,yy):
 if tmp[xxx][yyy]==c:
 cue.append((xxx,yyy))
 tmp[xxx][yyy] = 0
 elif chars[xxx][yyy]==0:
 nolib = False
 
 if nolib: chars = deepcopy(tmp)
 return nolib
 
for xx,yy in neighbors(x,y):
 if chars[xx][yy]==3-c: search(xx,yy,3-c)
if search(x,y,c):
 print(0)
else:
 print(1) 
 for row in chars: print(*row, sep='')