Ein Go- Spiel zu erzielen, ist keine leichte Aufgabe. In der Vergangenheit gab es mehrere Debatten darüber, wie Regeln entworfen werden sollen, um alle seltsamen Eckfälle abzudecken, die auftreten können. Glücklicherweise müssen Sie bei dieser Aufgabe keine komplizierten Dinge wie Leben und Tod oder die Erkennung von Seki erledigen. In dieser Aufgabe müssen Sie ein Programm implementieren, das ein Spiel nach den Tromp-Taylor-Regeln ohne Komi bewertet.
Das Bewertungsverfahren ist ziemlich einfach:
Man sagt, ein Punkt P, der nicht C gefärbt ist, erreicht C, wenn es einen Pfad (vertikal oder horizontal) benachbarter Punkte der Farbe P von P zu einem Punkt der Farbe C gibt. Die Punktzahl einer Spielerin ist die Anzahl der Punkte ihrer Farbe plus die Anzahl der leeren Punkte, die nur ihre Farbe erreichen.
Betrachten Sie zum Beispiel die folgende Tafel. X, OUnd -bezeichnet schwarz, weiß und ungefärbt Kreuzungen:
- - - 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 - - -
Das Anwenden der Bewertungsregel ergibt das folgende Ergebnis. x, oUnd -repräsentieren ungefärbten Kreuzungen , die als schwarz gezählt, weiß und Punkte niemanden.
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 - - -
Nach dem Diagramm hat Schwarz 23 Punkte, Weiß 29 Territorialpunkte. Daher sollte Ihr Programm W+6für diese Karte gedruckt werden .
Ich hoffe es ist so klar genug.
Ein- und Ausgabe
Die Eingabe ist eine Zeichenfolge, die genau enthält n² der Zeichen X, O, -wobei n nicht zum Zeitpunkt der Kompilierung bekannt. Ihr Programm sollte alle anderen Zeichen im Eingabestream ignorieren. Das Verhalten ist undefiniert, wenn es keine ganze Zahl n gibt , sodass die Anzahl der XO-Zeichen gleich n² ist . Sie können annehmen, dass n in [0, 255] ist .
Die Zeichenfolge ist als Sprungbrett aus n Zeilen und Spalten zu interpretieren . Die Ausgabe ist der absolute Wert der Differenz der Gesamtanzahl der Punkte von Weiß und Schwarz in Dezimaldarstellung. Wenn Weiß mehr Punkte hat, wird ihm das Präfix vorangestellt W+, wenn Schwarz mehr Punkte hat, wird ihm das Präfix vorangestellt B+. In dem Fall, dass beide Spieler die gleiche Anzahl von Punkten haben, ist die Ausgabe Jigo.
Die Eingabe ist implementierungsspezifisch auszulesen. Die Eingabe ist möglicherweise nicht Teil des Quellcodes.
Gewinnbedingungen
Das ist Code-Golf. Es gelten die üblichen Code-Golf-Konventionen. Die Einsendung mit der geringsten Anzahl von Zeichen in der Quelle gewinnt. Nur Programme, die die Spezifikation vollständig implementieren, können gewinnen.
Testfälle
Eingang:
- - - 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 - - -
Ausgabe: W+6
Eingang:
Xavier is insane -- says Oliver
Ausgabe: Jigo
Eingang:
Code-Golf
Ausgabe: Jigo
Eingang:
-XXXXXXX-XOOOOOOOXXO-OXXXOXXXOX--XOXXOOX
-
XOOXXOX--XOXXXOXXXO-OXXOOOOOOOX-XXXXXXX-
Ausgabe: B+21
Eingang:
- - 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 - -
Ausgabe: B+6
Weitere Testfälle folgen in Kürze.
Referenzimplementierung
Ich habe eine in ANSI C geschriebene Referenzimplementierung erstellt . Diese Implementierung liest die Eingabe von der Standardeingabe und schreibt die Ausgabe in die Standardausgabe.
/* 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");
}
quelle
W+7?S+ein Tippfehler war (weil Sie früher mögliche Ausgabe entweder als aufgelistetW+,B+oderJigo) und ich schaute auf meine Tastatur und sah dieSin der Nähe istW... Oder nutzen Sie Dvorak?Antworten:
GolfScript (105 Bytes)
Online-Demo .
Flood-Fill aus dieser früheren Antwort von mir angepasst .
Die Lösung füllt eine Kopie der ursprünglichen Tafel mit X und eine andere mit O. Somit werden leere Zellen, die von beiden Farben erreicht werden können, für beide gewertet, aber bei der Subtraktion gestrichen.
quelle
C (
438434413382364336322298294292290 Zeichen)Alle Zeilenumbrüche mit Ausnahme des ersten, die zur besseren Lesbarkeit eingefügt wurden. Eine kommentierte und etwas besser lesbare Version finden Sie hier .
Diese Antwort ist im Wesentlichen die Referenzlösung, aber mit all den nutzlosen Dingen (wie Typen [wer braucht etwas anderes als
intsowieso?] Und Standardkonformität [Rückgabewert von main? Bitte!])Korrekturen und Verbesserungen
438 → 434
Die explizite Initialisierung von Variablen wurde gelöscht, nachdem ich mich davon überzeugt hatte, dass sie automatisch
0gemäß Standard initialisiert werden.434 → 413
Entfernte case-Anweisung: Wenn eine ungefärbte Kreuzung sowohl von Schwarz als auch von Weiß aus erreichbar ist, können wir sie als einen Punkt für beide zählen, um das Programm zu vereinfachen. Umschalten der logischen Zweige, um eine Negation zu vermeiden.
413 → 382
Weisen Sie
dzugetchar()+1, um ein Paar Klammern zu speichern.bOrdnen Sie diecaseAnweisungen unter der Annahme, dass sie mit Nullen initialisiert sind, neu an und verwerfen Sie allebreakAnweisungen.(a>b?c:0)ist länger als(a>b)*c.(d+1)*g+eist länger alsd*g+e+g.382 → 364
Verbessertes Looping, keine Zeilenumbrüche in der Ausgabe, kürzere Ausgaberoutinen.
364 → 336
Habe diese
switchAussage losgeworden . (Danke Howard!) Verfolge die Punktedifferenz für zwei Charaktere. Negierecfür ein Zeichen. vier Zeichen in der großen oder der Klausel.336 → 323
Durch Ersetzen
&durch%können Klammern für vier Zeichen entfernt werden. Die Quadratwurzel wurde mit der Eingabeschleife für ungefähr neun Zeichen (yeah!) Verschmolzen und ein Zeicheniffür ein Zeichen entfernt .323 → 298
Das Makro wurde eingeführt
H, um das häufig vorkommende und sperrigeb[d*g+e]Konstrukt zu ersetzen .298 → 294
Ändern Sie
a&=~4zu,a&=3da wir nur die niedrigsten drei Bytes von beobachtena. Auch geändert , um Schleifenkörper aus((a=I])<3)?a|=...zuI]<3?a=I]|...denen zwei Zeichen kürzer. Stellen Sie außerdemhanstelle der Wiederverwendung einc, was ein Zeichen kürzer ist.294 → 292
hVariable eliminieren . Wenn wir testencmit!c--statt!c++,cgleich 0 ist am Ende der Flut-fill Schleife und damit verwendet werden kann , für den Zweck ,hbevor sie verwendet wurde (dh mitzählen).292 → 290
Ersetzen des Konstrukts
d-46?f--:0mitd-46&&f--dem kürzeren durch ein Zeichen ist , und verbinden die beiden Zuordnungenain der inneren Schleife.quelle
{b[f]=d-80?d-89?d-46?f--:0:5:6;f++;}das Speichern mehrerer Zeichen ersetzen .J (
140136131129119117116 Zeichen)Nachdem ich meine J-Skills verbessert habe, kann ich endlich einen Beitrag in J einreichen. Es ist allerdings ein bisschen lang.
Der von dieser Übermittlung implementierte Algorithmus ist der Referenzimplementierung sehr ähnlich, unterscheidet sich jedoch in der Art und Weise, wie belegte Felder behandelt werden.
Hier ist die Lösung zur leichteren Verständlichkeit in mehrere Teile aufgeteilt. Die Golf-Lösung unterscheidet sich geringfügig davon, aber der Unterschied ist nicht sehr groß.
quelle
GolfScript, 190 Zeichen
Das Drehbuch wurde viel länger als ich anfangs dachte. Übergeben Sie eine Eingabe an STDIN. Die Ausgabe wird dann gedruckt, wenn das Programm beendet wird.
quelle
Rubin (314)
könnte mit etwas mehr Zeit kürzer gemacht werden:
quelle