Faça uma jogada em um tabuleiro Go

13

Você recebe uma posição no tabuleiro de um jogo Go e uma jogada para jogar. Você precisa mostrar se a mudança é legal ou não, e a nova posição no conselho, se for legal.

Uma breve explicação dos movimentos do Go: o jogo consiste em colocar, alternativamente, peças em preto e branco ("pedras") em lugares vazios em um tabuleiro quadrado. Conjuntos de peças da mesma cor que são conectados um ao outro (quatro vias) são chamados de grupos. Lugares vazios no quadro que são adjacentes a um grupo (também de quatro vias) são considerados "liberdades" desse grupo. Um grupo com 0 liberdades é capturado (removido do quadro). Uma jogada que faria com que seu próprio grupo fosse capturado ("suicídio") é ilegal, a menos que esteja capturando um ou mais grupos de oponentes (ganhando liberdades no processo para que não seja realmente capturado).

Para os interessados, você não precisa lidar com ko (e superko), ou seja, você pode assumir que uma captura de ko é legal. Se você não sabe o que isso significa, basta seguir as regras acima e tudo ficará bem.

Entrada: um número n entre 2 e 19 (inclusive) representando o tamanho do quadro, seguido por n linhas de n números entre 0 e 2 (inclusive) representando a posição do quadro, seguidos por 3 números separados por espaço, representando o movimento a ser realizado. Na posição do tabuleiro, 0 significa lugar vazio, 1 significa pedra preta e 2 significa pedra branca. O movimento indica a coluna, a linha e a cor (1 ou 2) da pedra. A coluna e a linha são baseadas em 0, variando de 0 a n-1 (inclusive) e contadas na mesma ordem que a entrada da placa.

Você pode assumir que a posição do conselho é legal (todos os grupos têm pelo menos uma liberdade).

Saída: uma linha contendo 1 ou 0 (ou verdadeiro / falso, se você preferir) se a jogada for legal ou não, seguida (apenas no caso de uma jogada legal) pela nova posição da placa no mesmo formato da entrada.

Pontuação: número de bytes do código fonte completo, quanto menor, melhor. 20% de multa adicional pelo uso de caracteres não-ascii e 20% de multa adicional se o seu código não puder ser testado no Linux usando software disponível gratuitamente.

Regras: sem conexões de rede e sem bibliotecas de terceiros. Seu programa deve usar os fluxos de entrada e saída padrão ou o equivalente padrão para sua linguagem de programação.

Exemplos:

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
aditsu sair porque SE é MAU
fonte

Respostas:

2

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

Usa 3 campos de bits para representar o quadro - um para espaços em preto, branco e vazios. Torna os vizinhos encontrados Ne torna as hoperações da cadeia muito concisas.

Uma versão ungolfed com muitos comentários: https://gist.github.com/airfrog/8429006

airfrog
fonte
Você tem muitos espaços no final de cada linha, o arquivo que você publicou possui 2732 bytes.
aditsu saiu porque SE é MAU 14/01
@aditsu Isso deve ser corrigido agora
airfrog
O tamanho ainda está errado, deve ser 555 agora :) Também me pergunto se você ainda pode salvar alguns bytes usando mais pontos e vírgulas.
aditsu saiu porque SE é MAU 14/01
Erro? Entrada: 6 000000 011221 121121 122221 011110 000000 4 0 1Saída: 0. Adicionado agora como exemplo 4.
aditsu foi encerrado porque o SE é EVIL
Esse bug foi corrigido, eu também encontrei e corrigi outro bug enquanto jogava golfe que você pode adicionar como exemplo. Entrada: A 5 22100 20211 12211 12120 01120 1 1 2saída deve ser 0.
airfrog
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()

Percorra: analise a entrada, verifique se o movimento está em um local vazio, faça o movimento, inicie a grade do "grupo", simplifique / minimize a grade do grupo verificando a cor das pedras adjacentes (s = 0) e continue repetindo até que esteja totalmente minimizada , verifique para liberdades de grupo (s = 1), remova pedras oponentes para grupos sem liberdade (s = 2), repita s = 0 es = 1, verifique se todos os grupos de jogadores têm liberdades, retorne resultado.

Provavelmente isso pode ser reduzido significativamente ...

Exemplo interativo é executado:

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
jur
fonte
1
Seu programa não faz nada, apenas define uma função.
aditsu saiu porque SE é MAU 14/01
Executá-lo de forma interativa e chamá-lo com impressão o (), como mostrado no exemplo de execução ...
jur
Não. É suposto ser um programa independente que você executa a partir da linha de comando. Além disso, isso também o tornaria mais curto.
aditsu saiu porque SE é MAU 14/01
Corrigido adicionando print o () na última linha
jur
Por que não usar apenas o corpo da função (ultrapassado)? E acho que você também não o exemplo recém-adicionado 4.
aditsu sair porque SE é MAU