Marque um jogo de Go

23

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, OE -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, oE -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+6para este quadro.

Espero que seja claro o suficiente dessa maneira.

Entrada e saída

A entrada é uma cadeia que contém exatamente 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 . 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");
}
FUZxxl
fonte
Presumivelmente, você quer dizer a última saída W+7?
dmckee
Não ... Como você chega a essa conclusão?
FUZxxl
Er ... eu assumi que S+era um erro de digitação (por causa possível saída que você listadas anteriormente como quer W+, B+ou Jigo) e eu olhei para o meu teclado e viu o Sestá perto W... Ou você usar Dvorak?
dmckee
@dmckee Suponho que o "S" vem do alemão "Schwarz" em vez de "Black".
21712 Howard
Oh ... você está certa. Desculpe por isso
FUZxxl

Respostas:

2

GolfScript (105 bytes)

{'-XO'?}/]-1-.{2*3%}%{.,:N),{.*N=}?/{{[{.2$+1={+.}*}*]}%zip}N*[]*.1--,\}2*-.{.0>'W+B+'2/=\abs}{;'Jigo'}if

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.

Peter Taylor
fonte
Justo. Você pode ganhar esta rodada.
FUZxxl
6

C ( 438 434 413 382 364 336 322 298 294 292 290 caracteres)

#define I b[d*g+e
a;b[65536];c;d;e;f;g;main(){for(;d=getchar()+1;f++)b[f]=d-80?d-89?d-46&&
f--:5:6,g+=g*g<f;while(!c--)for(d=g;d--;)for(e=g;e--;)I]<3?a=3&(I]|!!d*I
-g]|!!e*I-1]|(d<g-1)*I+g]|(e<g-1)*I+1]),c&=I]==a,I]=a:0;while(f--)c+=b[f
]%2-b[f]/2%2;printf(c?"%c+%i":"Jigo",c>0?66:87,abs(c));}

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 intqualquer 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 0acordo 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 da getchar()+1para salvar um par de parênteses. Sob a suposição que bé inicializada com zeros, reordene as caseinstruções, descartando todas as breakinstruções. (a>b?c:0)é maior que (a>b)*c. (d+1)*g+eé maior que d*g+e+g.

382 → 364

Loop melhorado, sem novas linhas na saída, rotinas de saída mais curtas.

364 → 336

Livre-se dessa switchafirmação. (Obrigado, Howard!), Acompanhe a diferença de pontos para dois personagens. Negue cpara 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 um ifpara um caractere.

323 → 298

Introduziu a macro Hpara substituir a construção que geralmente ocorre e é volumosa b[d*g+e].

298 → 294

Altere a&=~4para a&=3como apenas todos observamos os três bytes mais baixos de a. Também alterado para corpo do laço ((a=I])<3)?a|=...da I]<3?a=I]|...que tem dois caracteres mais curto. Além disso, introduza, em hvez de reutilizar c, que é um caractere menor.

294 → 292

Eliminar hvariável. Se testamos ccom em !c--vez de !c++, cé igual a 0 no final do ciclo de preenchimento e, portanto, pode ser usado para o propósito que hfoi usado antes (ou seja, manutenção de pontuação).

292 → 290

Substitua a construção d-46?f--:0pela d-46&&f--qual é mais curta por um caractere e combine as duas atribuições ano loop interno.

FUZxxl
fonte
1
Você pode substituir a instrução switch por algo como {b[f]=d-80?d-89?d-46?f--:0:5:6;f++;}salvar vários caracteres.
267 Howard
@ Howard: Sim. Isso funcionou muito bem! Obrigado
FUZxxl
"Para maior legibilidade" - como se.
tomsmeding 22/09/14
@tomsmeding Bem, rolar uma linha é muito menos legível. Além disso, uma versão comentada está vinculada.
FUZxxl 22/09
@FUZxxl Isso foi feito de brincadeira. :) Além disso, você está certo ao dizer que é melhor do que em uma linha.
tomsmeding
6

J ( 140 136 131 129 119 117 117 116 caracteres)

Depois de aumentar minhas habilidades em J, posso finalmente fornecer uma finalização em J. É um pouco longo.

exit echo>(*{'Jigo';('B+',":);'W+',":@|)+/,-/1 2=/(]OR(0=[)*[:OR((,.|.)0,i:1)|.!.0])^:_~($~,~@%:@#)3-.~'-XO'i:1!:1]3

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.

input =. 3 -.~ '-XO' i: 1!:1 ] 3
board =. ($~ ,~@%:@#) input
NB. shift up, down, left, right
rotm =. (,. |.) 0 , i: 1
fill =. ] OR (0 = [) * [: OR rotm |.!.0 ]
filledboard =. fill^:_~ board
score =. +/ , -/ 1 2 =/ filledboard
echo > (* { 'Jigo' ; ('B+' , ":) ; ('W+', ":@|)) score
exit 0
FUZxxl
fonte
5

GolfScript, 190 caracteres

{"XO-"?)},:v,.),\{\.*=}+,~:s.*:`0\,{s%!\2*+}/:r;88{0v@{=\2*+}+/}:%~79%1${{:<.r|r^2*|<2/r|r^|<2s?:h/|<h*|1$|1$^2`?(&}`*}:a~@@a\;.2$|2${^2*)2base{+}*}:m~@2$|@m-.{"BW"1/1$0>="+"@abs}{;"Jigo"}if

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.

Howard
fonte
2

Rubi (314)

pode ser reduzido com mais tempo:

q={?-=>0,?X=>5,?O=>6};b=[];$<.chars{|c|(t=q[c])&&b<<t}
z=Math.sqrt b.size
loop{c=b.each_with_index.map{|h,i|
next h if h>2
x=i%z
y=i/z
u=y<1?0:b[i-z]
l=x<1?0:b[i-1]
d=y>z-2?0:b[i+z]
r=x>z-2?0:b[i+1]
~4&(h|u|d|l|r)}
break if c==b
b=c}
b.map!{|h|h&~4}
s=b.count(1)-b.count(2)
puts s==0?"Jigo":s>0?"B+#{s}":"W+#{-s}"
jsvnm
fonte