Strzel grę Go

23

Zdobywanie punktów w Go to zadanie, które nie jest wcale takie łatwe. W przeszłości odbyło się kilka debat na temat projektowania reguł obejmujących wszystkie dziwne przypadki narożne, które mogą się zdarzyć. Na szczęście w tym zadaniu nie musisz robić skomplikowanych czynności, takich jak życie i śmierć czy wykrywanie seki. W tym zadaniu musisz wdrożyć program oceniający grę zgodnie z zasadami Tromp-Taylor bez Komi.
Procedura punktacji jest dość prosta:

punkt P, niebędący kolorem C, mówi się, że osiąga C, jeśli istnieje ścieżka (w pionie lub w poziomie) sąsiadujących punktów koloru P od P do punktu koloru C.
Wynik gracza to liczba punktów jego koloru , plus liczba pustych punktów, które osiągają tylko jej kolor.

Na przykład rozważmy następującą tablicę. X, OI -oznaczają czarny, biały i bezbarwnego krzyżakowe

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

Zastosowanie reguły punktacji daje następujący wynik. x, oi -reprezentują bezbarwne skrzyżowania, które są liczone jako czarne, białe i niczyje.

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

Zgodnie ze schematem czarny ma 23 punkty, biały ma 29 punktów terytorium. Dlatego twój program powinien wydrukować W+6dla tej płyty.

Mam nadzieję, że w ten sposób będzie wystarczająco jasne.

Wejście i wyjście

Wejście jest ciąg znaków, który zawiera dokładnie n² znaków X, O, -gdzie n nie jest znany w czasie kompilacji. Twój program powinien zignorować wszystkie inne znaki w strumieniu wejściowym. Zachowanie jest niezdefiniowane, jeśli nie ma liczby całkowitej n takiej, że liczba XO-znaków jest równa n² . Możesz założyć, że n jest w [0, 255] .

Sekwencję znaków należy interpretować jako tablicę składającą się z n rzędów i kolumn. Wynik jest wartością bezwzględną różnicy całkowitej liczby punktów bieli i czerni w ujęciu dziesiętnym. Jeśli biały ma więcej punktów, jest poprzedzony przez W+, jeśli czarny ma więcej punktów, jest poprzedzony przez B+. W przypadku, gdy obaj gracze mają taką samą liczbę punktów, wynik jest Jigo.

Dane wejściowe należy czytać w sposób zdefiniowany w implementacji. Dane wejściowe mogą nie być częścią kodu źródłowego.

Warunki wygranej

To jest golf golfowy. Obowiązują zwykłe konwencje gry w golfa. Zgłoszenie z najmniejszą liczbą znaków w źródle wygrywa. Tylko programy, które w pełni implementują specyfikację, mogą wygrać.

Przypadki testowe

Wkład:

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

Wydajność: W+6

Wkład:

Xavier is insane -- says Oliver

Wydajność: Jigo

Inpout:

Code-Golf

Wydajność: Jigo

Wkład:

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

Wydajność: B+21

Wkład:

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

Wydajność: B+6

Więcej przypadków testowych już wkrótce.

wdrożenie referencyjne

Utworzyłem implementację referencyjną napisaną w ANSI C. Ta implementacja odczytuje dane wejściowe ze standardowego wejścia i zapisuje dane wyjściowe na standardowe dane wyjściowe.

/* 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");
}
code-golf game graph-theory board-game go FUZxxl
źródło
Prawdopodobnie masz na myśli ostatni wynik W+7?
dmckee,
Nie ... Jak dojść do tego wniosku?
FUZxxl
Er ... założyłem, że S+to literówka (ponieważ wcześniej wymieniłeś możliwe wyjście jako albo W+, B+albo Jigo) i spojrzałem na klawiaturę i zobaczyłem, że Sjest blisko W... A może używasz Dvoraka?
dmckee,
@dmckee Przypuszczam, że „S” pochodzi od niemieckiego „Schwarz” zamiast „Black”.
Howard
Och ... Masz rację. Przepraszamy za to
FUZxxl,

Odpowiedzi:

2

GolfScript (105 bajtów)

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

Demo online .

Wypełnienie zalane na podstawie mojej wcześniejszej odpowiedzi .

Rozwiązanie wypełnia jedną kopię oryginalnej płyty X, a drugą O. W ten sposób puste komórki, które są osiągalne za pomocą obu kolorów, są oceniane dla obu, ale anulują odejmowanie.

Peter Taylor
źródło
Słusznie. Możesz wygrać tę rundę.
FUZxxl,
6

C ( 438 434 413 382 364 336 322 298 294 292 290 znaków)

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

Wszystkie nowe wiersze oprócz pierwszego wstawiono w celu zwiększenia czytelności. Skomentowana i nieco bardziej czytelna wersja znajduje się tutaj .

Ta odpowiedź jest zasadniczo rozwiązaniem referencyjnym, ale zawiera wszystkie te bezużyteczne rzeczy (takie jak typy [kto i tak potrzebuje czegoś innego int?] I zgodność ze standardami [wartość zwracana z głównego? Proszę!])

Poprawki i ulepszenia

438 → 434

Porzuciłem jawną inicjalizację zmiennych po tym, jak przekonałem się, że są one automatycznie inicjowane 0zgodnie ze standardem.

434 → 413

Usunięto instrukcję case: Jeśli do bezbarwnego skrzyżowania jest osiągalne zarówno z czerni, jak i bieli, możemy je policzyć jako jeden punkt dla obu, aby uprościć program. Przełączanie gałęzi logicznych, aby uniknąć negacji.

413 → 382

Przypisz, daby getchar()+1zapisać jedną parę nawiasów. Przy założeniu, że bjest on inicjowany na zera, zmień kolejność caseinstrukcji, odrzucając wszystkie breakinstrukcje. (a>b?c:0)jest dłuższy niż (a>b)*c. (d+1)*g+ejest dłuższy niż d*g+e+g.

382 → 364

Ulepszone zapętlanie, brak nowych linii na wyjściu, krótsze procedury wyjściowe.

364 → 336

Pozbyłem się tego switchoświadczenia. (Dzięki, Howard!), Śledź różnicę punktów dla dwóch postaci. Neguj cdla jednej postaci. cztery znaki w dużej lub klauzuli.

336 → 323

Zastąpienie &przez %umożliwia usunięcie nawiasów klamrowych dla czterech znaków. Połączyłem pierwiastek kwadratowy z pętlą wejściową dla około dziewięciu znaków (tak!), Usunąłem ifjeden znak.

323 → 298

Wprowadzono makro, Haby zastąpić często występujący i nieporęczny b[d*g+e]konstrukt.

298 → 294

Zmień a&=~4na, a&=3ponieważ tylko każdy z nas obserwuje trzy najniższe bajty a. Zmienił również do ciała pętli od ((a=I])<3)?a|=...celu I]<3?a=I]|..., który jest dwa znaki krótszy. Wprowadź hzamiast ponownego użycia c, który jest krótszy o jedną postać.

294 → 292

Wyeliminuj hzmienną. Jeśli testujemy cz !c--zamiast !c++, crówna się 0 na końcu pętli zalewania i dlatego może być użyty do tego celu, w którym hbył używany wcześniej (tj. Utrzymywanie wyniku).

292 → 290

Zastąpić konstrukcję d-46?f--:0z d-46&&f--, który jest krótszy od charakteru i połączyć dwa zadania do aw pętli wewnętrznej.

FUZxxl
źródło
1
Możesz zamienić instrukcję switch na coś w rodzaju {b[f]=d-80?d-89?d-46?f--:0:5:6;f++;}zapisania kilku znaków.
Howard
@Howard: Tak. To działało naprawdę dobrze! Dziękuję
FUZxxl,
„Dla lepszej czytelności” - jak gdyby.
tomsmeding
@tomsmeding Cóż, przewijanie jednej linii jest znacznie mniej czytelne. Skomentowana wersja jest również połączona z.
FUZxxl,
@FUZxxl To było żartobliwie. :) Masz również rację mówiąc, że jest to lepsze niż na 1 linii.
tomsmeding
6

J ( 140 136 131 129 119 117 116 znaków)

Po zwiększeniu moich umiejętności J, mogę w końcu złożyć podanie w J. To jednak trochę za długo.

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

Algorytm zaimplementowany w tym zgłoszeniu jest bardzo podobny do implementacji referencyjnej, ale różni się sposobem obsługi zajętych pól.

Oto rozwiązanie podzielone na więcej części dla łatwiejszego zrozumienia. Gra w golfa różni się nieco od tego, ale różnica nie jest bardzo duża.

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
źródło
5

GolfScript, 190 znaków

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

Skrypt stał się znacznie dłuższy niż myślałem na początku. Przekaż dowolne wejście na STDIN, a wyjście zostanie wydrukowane po zakończeniu programu.

Howard
źródło
2

Rubin (314)

może być krótszy z pewnym czasem:

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
źródło