Marcar um jogo Go é uma tarefa que não é muito fácil. No passado, houve vários debates sobre como criar regras para cobrir todos os casos estranhos que podem ocorrer. Felizmente, nesta tarefa, você não precisa fazer coisas complicadas, como a vida e a morte ou a detecção de seki. Nesta tarefa, você precisa implementar um programa que classifique um jogo de acordo com as regras de Tromp-Taylor sem Komi.
O procedimento de pontuação é bastante simples:
é dito que um ponto P, que não é da cor C, alcança C, se houver um caminho (vertical ou horizontal) de pontos adjacentes da cor de P de P até um ponto da cor C.
A pontuação de um jogador é o número de pontos de sua cor , mais o número de pontos vazios que atingem apenas a cor dela.
Por exemplo, considere a seguinte placa. X
, O
E -
denotam pretas, brancas e não corados: intersecções
- - - X - O - - -
- - - X - O - - -
- - - X - O - - -
- - - X O - - O -
X X X O - O O - -
- - - X O - - O O
- - - X - O - - -
- - - X - O - X -
- - - - - O - - -
A aplicação da regra de pontuação produz o seguinte resultado. x
, o
E -
representam cruzamentos incolores que são contadas como preto, branco e pontos de ninguém.
x x x X - O o o o
x x x X - O o o o
x x x X - O o o o
x x x X O o o O o
X X X O o O O o o
- - - X O - - O O
- - - X - O - - -
- - - X - O - X -
- - - - - O - - -
De acordo com o diagrama, o preto tem 23 pontos, o branco tem 29 pontos de território. Portanto, seu programa deve imprimir W+6
para este quadro.
Espero que seja claro o suficiente dessa maneira.
Entrada e saída
A entrada é uma cadeia que contém exatamente n² dos personagens X
, O
, -
onde n não é conhecido em tempo de compilação. Seu programa deve ignorar todos os outros caracteres no fluxo de entrada. O comportamento é indefinido se não houver um número inteiro n, de modo que a quantidade de XO-
caracteres seja igual a n² . Você pode assumir que n está em [0, 255] .
A sequência de caracteres deve ser interpretada como um Go-board de n linhas e colunas. A saída é o valor absoluto da diferença da quantidade total de pontos de branco e preto na representação decimal. Se o branco tiver mais pontos, será o prefixo de W+
, se o preto tiver mais pontos, o prefixo de B+
. No caso de ambos os jogadores terem uma quantidade igual de pontos, a saída é Jigo
.
A entrada deve ser lida de uma maneira definida pela implementação. A entrada pode não fazer parte do código fonte.
Condições vencedoras
Isso é código-golfe. Aplicam-se convenções usuais de código-golfe. A submissão com a menor quantidade de caracteres em sua origem vence. Somente programas que implementam completamente a especificação podem vencer.
Casos de teste
Entrada:
- - - X - O - - -
- - - X - O - - -
- - - X - O - - -
- - - X O - - O -
X X X O - O O - -
- - - X O - - O O
- - - X - O - - -
- - - X - O - X -
- - - - - O - - -
Saída: W+6
Entrada:
Xavier is insane -- says Oliver
Saída: Jigo
Entrada:
Code-Golf
Saída: Jigo
Entrada:
-XXXXXXX-XOOOOOOOXXO-OXXXOXXXOX--XOXXOOX
-
XOOXXOX--XOXXXOXXXO-OXXOOOOOOOX-XXXXXXX-
Saída: B+21
Entrada:
- - X O O O O X X - - - - - - X O O -
- X X O X O X X O X X X X X X - X O -
- X O O X X X - O O O X O O X X X O -
- X O O O X X O O O O O O X X X O - -
- - X X O X - X X X X O O O O O O O -
- - X O O X X X - X X X O O O X X O -
- - X O - O X O X O O O O O X X X O -
- X O O - O O O X X X X X O O X O - -
- X X X O - - - O X O X X X O X O - -
X O O O O - - O - O O O O X X X O O -
X X O - - - O - - O O X X - - X X O O
X O O O - - O - O O X - - - - X O O X
- X X X O O X O O X X - - - - X X X X
X - X X X O X X O O X - - X X O X O O
X X O O X O X O X X - - - X O O O O -
X O - O X X X O X - - - - - X O - - -
O O - O X O O O O X X - X X X X O - -
O O - O O O X O X X - - X - X X O - -
- - O - - O X X X - - - - X O O O - -
Saída: B+6
Mais casos de teste chegarão em breve.
implementação de referência
Eu criei uma implementação de referência escrita em ANSI C. Essa implementação lê a entrada da entrada padrão e grava a saída na saída padrão.
/* http://codegolf.stackexchange.com/q/6693/134
* reference implementation
* by user FUZxxl
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXBOARD 256
/* bit 0x01: black colour
* bit 0x02: white colour
* bit 0x04: there is a stone on the intersection
*/
enum colour {
UNCOLOURED = 0x0,
BLACK_REACHED = 0x1,
WHITE_REACHED = 0x2,
BOTH_REACHED = 0x3,
HAS_STONE = 0x4,
BLACK = 0x5,
WHITE = 0x6
};
static enum colour board[MAXBOARD * MAXBOARD] = { 0 };
static int bsize = 0;
static void read_input(void);
static void fill_board(void);
static void show_score(void);
int main()
{
read_input();
fill_board();
show_score();
return EXIT_SUCCESS;
}
static void read_input(void)
{
int n = 0;
int invalue;
while ((invalue = getchar()) != EOF) {
switch (invalue) {
case '-': board[n++] = UNCOLOURED; break;
case 'X': board[n++] = BLACK; break;
case 'O': board[n++] = WHITE; break;
}
}
while (bsize * bsize < n) bsize++;
/* your program may exhibit undefined behaviour if this is true */
if (bsize * bsize != n) exit(EXIT_FAILURE);
}
static void fill_board(void)
{
int i,j;
int changes;
enum colour here, top, bottom, left, right, accum;
do {
changes = 0;
for (i = 0; i < bsize; ++i) {
for (j = 0; j < bsize; ++j) {
here = board[i * bsize + j];
if (here >= BOTH_REACHED) continue;
top = i == 0 ? UNCOLOURED : board[(i - 1) * bsize + j];
left = j == 0 ? UNCOLOURED : board[i * bsize + j - 1];
bottom = i == bsize-1 ? UNCOLOURED : board[(i + 1) * bsize + j];
right = j == bsize-1 ? UNCOLOURED : board[i * bsize + j + 1];
accum = here | top | bottom | left | right;
accum &= ~HAS_STONE;
changes |= board[i * bsize + j] != accum;
board[i * bsize + j] = accum;
}
}
} while (changes);
}
static void show_score(void) {
int w = 0, b = 0, n;
for (n = 0; n < bsize*bsize; ++n) switch (board[n] & ~HAS_STONE) {
case BLACK_REACHED: ++b; break;
case WHITE_REACHED: ++w; break;
}
if (b != w)
printf("%s%i\n",b>w?"B+":"W+",abs(b-w));
else
printf("Jigo\n");
}
fonte
W+7
?S+
era um erro de digitação (por causa possível saída que você listadas anteriormente como querW+
,B+
ouJigo
) e eu olhei para o meu teclado e viu oS
está pertoW
... Ou você usar Dvorak?Respostas:
GolfScript (105 bytes)
Demonstração online .
Preenchimento adaptado a partir desta minha resposta anterior .
A solução preenche uma cópia da placa original com X e outra com O. Assim, as células vazias que são alcançáveis por ambas as cores são pontuadas para ambas, mas são canceladas na subtração.
fonte
C (
438434413382364336322298294292290 caracteres)Todas as novas linhas, exceto a primeira, foram inseridas para maior legibilidade. Uma versão comentada e um pouco mais legível pode ser encontrada aqui .
Essa resposta é essencialmente a solução de referência, mas com todas essas coisas inúteis (como tipos [quem precisa de algo diferente de
int
qualquer maneira?] E conformidade com os padrões [valor de retorno de main? Por favor!])Correções e melhorias
438 → 434
Largou a inicialização explícita de variáveis depois que me convenci de que elas eram automaticamente inicializadas de
0
acordo com o padrão.434 → 413
Declaração de caso removida: se uma interseção não colorida puder ser alcançada em preto e branco, podemos contar como um ponto para ambos, para simplificar o programa. Mudar de ramificações lógicas para evitar negação.
413 → 382
Atribua
d
agetchar()+1
para salvar um par de parênteses. Sob a suposição queb
é inicializada com zeros, reordene ascase
instruções, descartando todas asbreak
instruções.(a>b?c:0)
é maior que(a>b)*c
.(d+1)*g+e
é maior qued*g+e+g
.382 → 364
Loop melhorado, sem novas linhas na saída, rotinas de saída mais curtas.
364 → 336
Livre-se dessa
switch
afirmação. (Obrigado, Howard!), Acompanhe a diferença de pontos para dois personagens. Neguec
para um caractere. quatro caracteres na grande ou cláusula.336 → 323
Substituir
&
por%
permite a remoção de chaves para quatro caracteres. Fundiu a raiz quadrada com o loop de entrada para mais ou menos nove caracteres (sim!), Removeu umif
para um caractere.323 → 298
Introduziu a macro
H
para substituir a construção que geralmente ocorre e é volumosab[d*g+e]
.298 → 294
Altere
a&=~4
paraa&=3
como apenas todos observamos os três bytes mais baixos dea
. Também alterado para corpo do laço((a=I])<3)?a|=...
daI]<3?a=I]|...
que tem dois caracteres mais curto. Além disso, introduza, emh
vez de reutilizarc
, que é um caractere menor.294 → 292
Eliminar
h
variável. Se testamosc
com em!c--
vez de!c++
,c
é igual a 0 no final do ciclo de preenchimento e, portanto, pode ser usado para o propósito queh
foi usado antes (ou seja, manutenção de pontuação).292 → 290
Substitua a construção
d-46?f--:0
pelad-46&&f--
qual é mais curta por um caractere e combine as duas atribuiçõesa
no loop interno.fonte
{b[f]=d-80?d-89?d-46?f--:0:5:6;f++;}
salvar vários caracteres.J (
140136131129119117 117116 caracteres)Depois de aumentar minhas habilidades em J, posso finalmente fornecer uma finalização em J. É um pouco longo.
O algoritmo implementado por este envio é muito semelhante à implementação de referência, mas diferente na maneira como os campos ocupados são tratados.
Aqui está a solução dividida em mais partes para facilitar a compreensão. A solução para o golfe é um pouco diferente disso, mas a diferença não é muito grande.
fonte
GolfScript, 190 caracteres
O script ficou muito mais longo do que eu pensava no começo. Passe qualquer entrada em STDIN e a saída será impressa quando o programa terminar.
fonte
Rubi (314)
pode ser reduzido com mais tempo:
fonte