13
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You have a LOT of spaces at the end of each line, the file as you posted it has 2732 bytes. \$\endgroup\$ – aditsu Jan 14 '14 at 5:27
  • \$\begingroup\$ @aditsu That should be fixed now \$\endgroup\$ – airfrog Jan 14 '14 at 12:52
  • \$\begingroup\$ Size is still wrong, should be 555 now :) Also I wonder if you can still save a few bytes by using more semicolons. \$\endgroup\$ – aditsu Jan 14 '14 at 13:03
  • \$\begingroup\$ Bug? Input: 6 000000 011221 121121 122221 011110 000000 4 0 1 Output: 0. Added now as example 4. \$\endgroup\$ – aditsu Jan 14 '14 at 13:37
  • \$\begingroup\$ 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. \$\endgroup\$ – airfrog Jan 14 '14 at 15:06
2
\$\begingroup\$

Python (9121004)

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Your program doesn't do anything, it only defines a function. \$\endgroup\$ – aditsu Jan 14 '14 at 5:30
  • \$\begingroup\$ Run it interactively and call it with print o() as shown in the example run... \$\endgroup\$ – jur Jan 14 '14 at 8:04
  • \$\begingroup\$ Nope. It is supposed to be a standalone program that you run from the command line. Besides, that would also make it shorter. \$\endgroup\$ – aditsu Jan 14 '14 at 8:19
  • \$\begingroup\$ Fixed it by adding print o() on the last line \$\endgroup\$ – jur Jan 14 '14 at 8:38
  • \$\begingroup\$ Why not just use the function body (outdented)? And I think you also fail the newly added example 4. \$\endgroup\$ – aditsu Jan 14 '14 at 13:36

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.