Gagnez une partie de Go

23

Marquer un jeu de Go est une tâche qui n'est pas trop facile. Dans le passé, il y a eu plusieurs débats sur la façon de concevoir des règles pour couvrir tous les cas étranges qui peuvent se produire. Heureusement, dans cette tâche, vous n'avez pas à faire des choses compliquées comme la vie et la mort ou la détection de seki. Dans cette tâche, vous devez implémenter un programme qui marque un jeu selon les règles de Tromp-Taylor sans Komi.
La procédure de notation est assez simple:

un point P, non coloré C, est censé atteindre C, s'il existe un chemin (verticalement ou horizontalement) de points adjacents de couleur P de P à un point de couleur C.
Le score d'un joueur est le nombre de points de sa couleur , plus le nombre de points vides qui n'atteignent que sa couleur.

Par exemple, considérez le tableau suivant. X, OEt -représentent des intersections noir, blanc et non colorés:

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

L'application de la règle de notation donne le résultat suivant. x, oEt -représentent les intersections décolorées qui sont comptées comme noir, blanc et points de personne.

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

Selon le diagramme, le noir a 23 points, le blanc a 29 points de territoire. Ainsi, votre programme devrait imprimer W+6pour ce forum.

J'espère que c'est assez clair de cette façon.

Entrée et sortie

L'entrée est une chaîne qui contient exactement des personnages X, O, -n est pas connu au moment de la compilation. Votre programme doit ignorer tous les autres caractères du flux d'entrée. Le comportement n'est pas défini s'il n'y a pas d'entier n tel que le nombre de XO-caractères soit égal à . Vous pouvez supposer que n est dans [0, 255] .

La séquence de caractères doit être interprétée comme un Go-board de n lignes et colonnes. La sortie est la valeur absolue de la différence de la quantité totale de points de blanc et de noir en représentation décimale. Si le blanc a plus de points, il est préfixé par W+, si le noir a plus de points, il est préfixé par B+. Dans le cas où les deux joueurs ont un nombre égal de points, la sortie est Jigo.

L'entrée doit être lue d'une manière définie par l'implémentation. L'entrée peut ne pas faire partie du code source.

Conditions gagnantes

C'est du code-golf. Les conventions de code-golf habituelles s'appliquent. La soumission avec le moins de caractères dans sa source gagne. Seuls les programmes qui implémentent pleinement la spécification peuvent gagner.

Cas de test

Contribution:

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

Sortie: W+6

Contribution:

Xavier is insane -- says Oliver

Sortie: Jigo

Entrée:

Code-Golf

Sortie: Jigo

Contribution:

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

Sortie: B+21

Contribution:

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

Sortie: B+6

D'autres tests seront bientôt disponibles.

implémentation de référence

J'ai créé une implémentation de référence écrite en ANSI C. Cette implémentation lit l'entrée depuis l'entrée standard et écrit la sortie vers la sortie standard.

/* 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
la source
Vraisemblablement, vous voulez dire la dernière sortie à être W+7?
dmckee
Non ... Comment en êtes-vous arrivé à cette conclusion?
FUZxxl
Euh ... Je suppose que S+était une faute de frappe (parce que vous avez précédemment énuméré sortie possible soit W+, B+ou Jigo) et je regardais mon clavier et vu l' Sest près W... Ou utilisez-vous Dvorak?
dmckee
@dmckee Je suppose que le "S" vient de l'allemand "Schwarz" au lieu de "Black".
Howard
Oh ... tu as raison. Désolé pour cela
FUZxxl

Réponses:

2

GolfScript (105 octets)

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

Démo en ligne .

Remplissage d'inondation adapté de ma réponse précédente .

La solution remplit une copie de la carte d'origine avec X et une autre avec O. Ainsi, les cellules vides qui sont accessibles par les deux couleurs sont notées pour les deux, mais annulent dans la soustraction.

Peter Taylor
la source
C'est suffisant. Vous pourriez gagner ce tour.
FUZxxl
6

C ( 438 434 413 382 364 336 322 298 294 292 290 caractères)

#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));}

Toutes les nouvelles lignes sauf la première insérée pour une meilleure lisibilité. Une version commentée et légèrement plus lisible peut être trouvée ici .

Cette réponse est essentiellement la solution de référence mais avec toutes ces choses inutiles (telles que les types [qui a besoin de quelque chose de différent de inttoute façon?] Et la conformité aux normes [valeur de retour du principal? S'il vous plaît!]))

Corrections et améliorations

438 → 434

Suppression de l'initialisation explicite des variables après que je me sois convaincu qu'elles sont automatiquement initialisées 0conformément à la norme.

434 → 413

Suppression de la déclaration de cas: si une intersection non colorée est accessible à la fois en noir et en blanc, nous pouvons la compter comme un point pour les deux afin de simplifier le programme. Commutateur de branches logiques pour éviter la négation.

413 → 382

Attribuez dà getchar()+1pour enregistrer une paire de parenthèses. Dans l'hypothèse qui best initialisée à zéro, réorganisez les caseinstructions, en rejetant toutes les breakinstructions. (a>b?c:0)est plus long que (a>b)*c. (d+1)*g+eest plus long que d*g+e+g.

382 → 364

Amélioration du bouclage, pas de nouvelles lignes dans la sortie, des routines de sortie plus courtes.

364 → 336

Je me suis débarrassé de cette switchdéclaration. (Merci, Howard!), Suivez la différence de points pour deux personnages. Niez cpour un caractère. quatre caractères dans le grand ou la clause.

336 → 323

Le remplacement &par %permet la suppression des accolades pour quatre caractères. Fusionné la racine carrée avec la boucle d'entrée pour environ neuf caractères (ouais!), Supprimé un ifpour un caractère.

323 → 298

Introduction de la macro Hpour remplacer la construction souvent volumineuse et volumineuse b[d*g+e].

298 → 294

Changez a&=~4en a&=3car nous observons uniquement les trois octets les plus bas de a. Aussi changé au corps de la boucle de ((a=I])<3)?a|=...à I]<3?a=I]|...qui est deux caractères plus courts. Introduisez également hau lieu de réutiliser c, qui est un caractère plus court.

294 → 292

Élimine la hvariable. Si nous testons cavec !c--au lieu de !c++, cest égal à 0 à la fin de la boucle de remplissage et peut donc être utilisé dans le but hutilisé auparavant (c.-à-d. Maintien du score).

292 → 290

Remplacez la construction d-46?f--:0par d-46&&f--laquelle est plus courte par un caractère et combinez les deux affectations à adans la boucle interne.

FUZxxl
la source
1
Vous pouvez remplacer l'instruction switch par quelque chose comme {b[f]=d-80?d-89?d-46?f--:0:5:6;f++;}pour enregistrer plusieurs caractères.
Howard
@Howard: Ouais. Cela fonctionnait vraiment bien! Merci
FUZxxl
"Pour une meilleure lisibilité" - comme si.
tomsmeding
@tomsmeding Eh bien, faire défiler une ligne est beaucoup moins lisible. En outre, une version commentée est liée à.
FUZxxl
@FUZxxl Cela voulait dire en plaisantant. :) De plus, vous avez raison de dire que c'est mieux que sur 1 ligne.
tomsmeding
6

J ( 140 136 131 129 119 117 116 caractères)

Après avoir augmenté mes compétences en J, je peux enfin fournir une soumission en J. C'est un peu long cependant.

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

L'algorithme implémenté par cette soumission est très similaire à l'implémentation de référence mais différent dans la façon dont les champs occupés sont traités.

Voici la solution divisée en plusieurs parties pour une meilleure compréhension. La solution golfée est légèrement différente de cela, mais la différence n'est pas très 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
la source
5

GolfScript, 190 caractères

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

Le script est devenu beaucoup plus long que je ne le pensais au début. Passez n'importe quelle entrée sur STDIN et la sortie sera ensuite imprimée à la fin du programme.

Howard
la source
2

Rubis (314)

pourrait être raccourci avec un peu plus de temps:

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