Anota un juego de Go

23

Marcar un juego Go es una tarea que no es demasiado fácil. En el pasado ha habido varios debates sobre cómo diseñar reglas para cubrir todos los casos extraños que pueden ocurrir. Afortunadamente, en esta tarea no tienes que hacer cosas complicadas como la vida o la muerte o la detección de seki. En esta tarea, debes implementar un programa que califique un juego de acuerdo con las reglas de Tromp-Taylor sin Komi.
El procedimiento de puntuación es bastante simple:

se dice que un punto P, que no tiene color C, llega a C, si hay un camino de puntos adyacentes (vertical u horizontalmente) del color de P desde P hasta un punto de color C.
La puntuación de un jugador es el número de puntos de su color , más el número de puntos vacíos que solo alcanzan su color.

Por ejemplo, considere la siguiente tabla. X, Oy -denotan intersecciones negras, blancas y sin color:

- - - 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 - - -

La aplicación de la regla de puntuación produce el siguiente resultado. x, oy -representan intersecciones sin color que se cuentan como puntos negros, blancos y de nadie.

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 - - -

Según el diagrama, el negro tiene 23 puntos, el blanco tiene 29 puntos de territorio. Por lo tanto, su programa debería imprimir W+6para este tablero.

Espero que sea lo suficientemente claro de esta manera.

Entrada y salida

La entrada es una cadena que contiene exactamente de los personajes X, O, -donde n no se conoce en tiempo de compilación. Su programa debe ignorar todos los demás caracteres en la secuencia de entrada. El comportamiento es indefinido si no hay un número entero n tal que la cantidad de XO-caracteres sea igual a . Puede suponer que n está en [0, 255] .

La secuencia de caracteres debe interpretarse como un tablero de n filas y columnas. La salida es el valor absoluto de la diferencia de la cantidad total de puntos de blanco y negro en representación decimal. Si el blanco tiene más puntos, tiene el prefijo W+, si el negro tiene más puntos, tiene el prefijo B+. En el caso de que ambos jugadores tengan la misma cantidad de puntos, la salida es Jigo.

La entrada debe leerse de una manera definida por la implementación. La entrada puede no ser parte del código fuente.

Condiciones ganadoras

Este es el código de golf. Se aplican convenciones de código de golf habituales. La presentación con la menor cantidad de caracteres en su fuente gana. Solo los programas que implementan completamente la especificación pueden ganar.

Casos de prueba

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 - - -

Salida: W+6

Entrada:

Xavier is insane -- says Oliver

Salida: Jigo

Entrada:

Code-Golf

Salida: Jigo

Entrada:

-XXXXXXX-XOOOOOOOXXO-OXXXOXXXOX--XOXXOOX
-
XOOXXOX--XOXXXOXXXO-OXXOOOOOOOX-XXXXXXX-

Salida: 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 - -

Salida: B+6

Más casos de prueba vendrán pronto.

Implementación de referencia

He creado una implementación de referencia escrita en ANSI C. Esta implementación lee la entrada de la entrada estándar y escribe la salida en la salida estándar.

/* 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
fuente
Presumiblemente, ¿te refieres a la última salida W+7?
dmckee el
No ... ¿Cómo llegas a esta conclusión?
FUZxxl
Er ... Supuse que S+era un error tipográfico (ya que anteriormente enumerado posible salida como sea W+, B+o Jigo) y yo miraba a mi teclado y vi la Sestá cerca W... O ¿Utiliza Dvorak?
dmckee
@dmckee Supongo que la "S" proviene del alemán "Schwarz" en lugar de "Black".
Howard
Oh ... tienes razon. Lo siento
FUZxxl

Respuestas:

2

GolfScript (105 bytes)

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

Demo en línea .

Relleno de inundación adaptado de esta respuesta mía anterior .

La solución llena una copia de la placa original con X y otra con O. Por lo tanto, las celdas vacías a las que se puede acceder con ambos colores se puntúan para ambas, pero se cancelan en la resta.

Peter Taylor
fuente
Lo suficientemente justo. Podrías ganar esta ronda.
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 las líneas nuevas excepto la primera insertada para una mejor legibilidad. Una versión comentada y ligeramente más legible se puede encontrar aquí .

Esta respuesta es esencialmente la solución de referencia, pero con todas esas cosas inútiles (como los tipos [¿quién necesita algo diferente de inttodos modos?] Y el cumplimiento de las normas [valor de retorno de main? ¡Por favor!])

Correcciones y mejoras.

438 → 434

Se eliminó la inicialización explícita de las variables después de convencerme de que se inicializan automáticamente 0según el estándar.

434 → 413

Declaración de caso eliminada: si se puede acceder a una intersección sin color desde blanco y negro, podemos contarla como un punto para que ambos simplifiquen el programa. Cambio de ramas lógicas para evitar la negación.

413 → 382

Asignar da getchar()+1para guardar un par de paréntesis. Bajo el supuesto que bse inicializa a ceros, reordene las casedeclaraciones, descartando todas las breakdeclaraciones. (a>b?c:0)es más largo que (a>b)*c. (d+1)*g+ees más largo que d*g+e+g.

382 → 364

Bucle mejorado, sin nuevas líneas en la salida, rutinas de salida más cortas.

364 → 336

Se deshizo de esa switchdeclaración. (¡Gracias, Howard!), Rastrea la diferencia de puntos para dos personajes. Negar cpara un personaje. cuatro caracteres en la letra grande o cláusula

336 → 323

Reemplazar &por %permite la eliminación de llaves para cuatro caracteres. Fusionó la raíz cuadrada con el bucle de entrada para nueve caracteres más o menos (¡sí!), Eliminó un ifpara un carácter.

323 → 298

Introdujo la macro Hpara reemplazar la b[d*g+e]construcción voluminosa y que ocurre a menudo .

298 → 294

Cambie a&=~4a a&=3ya que solo observamos los tres bytes más bajos de a. También cambiado a cuerpo del bucle de ((a=I])<3)?a|=...a I]<3?a=I]|...que es de dos caracteres más corto. Además, introduzca en hlugar de reutilizar c, que es un carácter más corto.

294 → 292

Eliminar hvariable. Si probamos ccon en !c--lugar de !c++, ces igual a 0 al final del ciclo de llenado de inundación y, por lo tanto, puede usarse para el propósito que hse usó antes (es decir, el mantenimiento de la puntuación).

292 → 290

Reemplace la construcción d-46?f--:0con la d-46&&f--cual es más corta por un carácter y combine las dos asignaciones aen el bucle interno.

FUZxxl
fuente
1
Puede reemplazar la declaración de cambio con algo como {b[f]=d-80?d-89?d-46?f--:0:5:6;f++;}guardar varios caracteres.
Howard
@Howard: Sí. Eso funcionó muy bien! Gracias
FUZxxl
"Para una mejor legibilidad", como si.
tomsmeding
@tomsmeding Bueno, desplazarse una línea es mucho menos legible. Además, una versión comentada está vinculada a.
FUZxxl
@FUZxxl Eso fue en broma. :) Además, tienes razón al decir que es mejor que en 1 línea.
tomsmeding
6

J ( 140 136 131 129 119 117 116 caracteres)

Después de aumentar mis habilidades en J, finalmente puedo proporcionar una presentación en J. Sin embargo, es un poco largo.

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

El algoritmo implementado por este envío es muy similar a la implementación de referencia, pero diferente en la forma en que se manejan los campos ocupados.

Aquí está la solución dividida en más partes para facilitar la comprensión. La solución de golf es ligeramente diferente de eso, pero la diferencia no es muy 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
fuente
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

El guión se hizo mucho más largo de lo que pensaba al principio. Pase cualquier entrada en STDIN y la salida se imprimirá cuando finalice el programa.

Howard
fuente
2

Rubí (314)

podría acortarse con algo más de tiempo:

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
fuente