Erziele eine Partie Kingdom Builder

16

Ich möchte hier eine neue Form des Codegolfs ausprobieren. Ähnlich wie bei Boni müssen nicht alle Teile der Herausforderung abgeschlossen sein, sondern jede Antwort muss eine Teilmenge einer bestimmten Größe implementieren (und es gibt einen Kern, den jede Antwort implementieren muss). Neben dem Golfspielen umfasst diese Herausforderung auch die Auswahl einer Reihe von Funktionen, die gut zusammenpassen.

Die Regeln

Kingdom Builder ist ein Brettspiel, das auf einem (spitzen) Hex-Gitter gespielt wird. Das Board besteht aus vier (randomisierten) Quadranten, von denen jeder 10x10 Hex-Zellen hat (ein Vollboard ist also 20x20). Für diese Herausforderung enthält jede Hex-Zelle entweder Wasser ( W), einen Berg ( M), eine Stadt ( T), eine Burg ( C) oder ist leer ( .). So könnte ein Quadrant aussehen

. . W . . . . . . .
 . M W W . . . . . .
. M . . W . . . T .
 M M . W . . . . . .
. . M . W W . . . .
 . . . . . W W W W W
. T . . . . . . . .
 . . W . . C . . . .
. . W W . . . . M . 
 . . . . . . . M M .

Die zweite Reihe ist immer von der ersten Reihe nach rechts versetzt. Spieler 1auf 4bis zu 40 Siedlungen jeweils auf leere Zellen (nach einigen Regeln , die wir für diese Herausforderung ignorieren) platzieren. Ein möglicher Spielplan am Ende des Spiels ist der folgende:

3 3 W . . . 4 . 4 . . 2 W . 4 . . 4 . 4
 3 M W W . 1 1 . . 4 2 W . 3 C 4 4 . . 4
3 M 2 2 W 1 1 1 T 3 2 W 4 3 . 1 4 . 4 .
 M M . W 2 2 . . . 2 2 W 3 . 1 1 1 . . .
. 4 M . W W 2 2 2 2 W W 3 . 1 4 . T . .
 . . . . . W W W W W . 3 C 1 . . 2 2 2 2
. T 1 1 1 1 . . 2 . . 4 . . . 2 2 M M M
 4 . W 4 . C 4 4 . . . . . . 2 M M M M M
. 4 W W . . . 4 M . . W . W . 2 2 2 M M
 . . . . . . . M M . . W W . . . . 2 M .
. . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 . 1
 M 3 3 . . . . . . . . 4 . T 2 . 2 4 1 .
M M . C . 4 . 4 . . . . . 1 2 4 2 1 1 .
 M . . 1 . 4 . . . . M M 1 2 . . 2 1 . .
. . . W 1 1 4 1 1 . . . 1 2 . . 2 W W W
 . . 1 1 W 1 T . 1 1 1 1 T . . 2 W . 4 .
. 1 1 W . 3 3 . . . . . . . . 2 W 4 C 3
 C 1 3 3 3 . 3 . 4 . 4 . 4 . . 2 W 1 1 M
4 3 3 4 . M 4 3 . . . . . . . 2 W . . .
 . . . 4 . M M 3 . . 4 4 . 4 . 2 W W . .

Wir werden die Quadranten wie beschriften

1 2
3 4

Ihre Aufgabe wird es sein, ein solches Brett zu punkten. Es gibt eine Kernbewertung, die immer verwendet wird, und 8 optionale Bewertungen, von denen 3 für jedes Spiel ausgewählt werden. Im Folgenden beschreibe ich alle 9 Punkte und verwende das obige Setup als Beispiel dafür, wie viele Punkte jeder Spieler erhalten würde.

† Es gibt 10 Punkte im eigentlichen Spiel, aber ich lasse zwei weg, weil niemand Golf spielen möchte.

Die Kernbewertung. Ein Spieler erhält 3 Punkte für jeden CAstle, neben dem er eine Siedlung hat. Beispielnoten: 18, 0, 15, 12.

Die optionalen Punkte.

  1. Ein Spieler erhält 1 Punkt für jede horizontale Reihe, in der er mindestens eine Siedlung hat.

    Beispielnoten: 14, 20, 12, 16.

  2. Finden Sie für jeden Spieler die horizontale Reihe, in der sich die meisten seiner Siedlungen befinden (wählen Sie im Falle eines Gleichstands eine aus). Ein Spieler erhält 2 Punkte für jede Siedlung in dieser Reihe.

    Beispielergebnisse: 14 (Zeile 16), 8 (Zeile 4, 5 oder 6), 28 (Zeile 11), 10 (Zeile 1).

  3. Ein Spieler erhält 1 Punkt für jede Siedlung, die neben Water gebaut wird.

    Beispielnoten: 13, 21, 10, 5.

  4. Ein Spieler erhält 1 Punkt für jede Siedlung neben einem MBrunnen.

    Beispielnoten: 4, 12, 8, 4.

  5. Zähle die Siedlungen jedes Spielers in jedem Quadranten. Pro Quadrant erhalten die Spieler mit der größten Anzahl von Siedlungen jeweils 12 Punkte , die Spieler mit der zweitgrößten Anzahl von Siedlungen jeweils 6 Punkte .

    Beispielergebnisse: 18 (6 + 0 + 6 + 6), 36 (12 + 12 + 0 + 12), 12 (0 + 0 + 12 + 0), 18 (12 + 6 + 0 + 0).

  6. Bestimmen Sie für jeden Spieler den Quadranten, in dem er die geringste Anzahl von Siedlungen hat. Ein Spieler erhält 3 Punkte für jede Siedlung in diesem Quadranten.

    Beispielbewertungen: 18 (Quadrant 2), 0 (Quadrant 3), 15 (Quadrant 1 oder 2), 27 (Quadrant 3).

  7. Ein Spieler erhält 1 Punkt für jede verbundene Siedlungsgruppe.

    Beispielnoten: 7, 5, 6, 29.

  8. Ein Spieler erhält 1 Punkt für jeweils 2 Siedlungen in der größten Gruppe zusammenhängender Siedlungen des Spielers.

    Beispielnoten: 4, 10, 8, 2.

Die Herausforderung

Wie im Spiel werden Sie 3 der optionalen Punkte auswählen und ein bestimmtes Brett basierend auf dem Kernpunktestand und diesen drei Punkten bewerten. Ihr Code sollte eine Liste mit 4 Ergebnissen erstellen. Es gibt jedoch eine Einschränkung bei der Auswahl: Ich habe die Ergebnisse in drei Gruppen eingeteilt, und Sie müssen für jede Gruppe eine implementieren:

  • Implementieren Sie eine von 1 und 2 .
  • Implementiere eines von 3, 4, 5 und 6 .
  • Implementieren Sie eine der 7 und 8 .

Sie können ein Programm oder eine Funktion schreiben und Eingaben über STDIN, ein Befehlszeilenargument, eine Eingabeaufforderung oder einen Funktionsparameter vornehmen. Sie können das Ergebnis zurückgeben oder an STDOUT drucken.

Sie können ein beliebiges praktisches 1D- oder 2D-Listen- / Zeichenfolgeformat für die Eingabe auswählen. Möglicherweise verwenden Sie kein Diagramm mit vollständigen Informationen zur Nachbarschaft. Hier finden Sie einige gute Informationen zu Hex-Gittern, wenn Sie Inspiration benötigen.

Ihre Ausgabe kann auch in einem beliebigen praktischen, eindeutigen Listen- oder Zeichenfolgenformat erfolgen.

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Weitere Annahmen

Sie können davon ausgehen, dass ...

  • ... jeder Spieler hat mindestens 1 Siedlung und es gibt nicht mehr als 40 Siedlungen von jedem Spieler.
  • ... jeder Quadrant enthält entweder eine Stadt und zwei Burgen oder zwei Städte und eine Burg.
  • ... Städte und Burgen sind weit genug voneinander entfernt, so dass keine Siedlung neben zwei von ihnen liegen kann.

Testfälle

Unter Verwendung der obigen Tabelle sind hier die Einzelbewertungen für alle möglichen Auswahlen von Bewertungsmechanismen:

Chosen Scores      Total Player Scores
1 3 7              52 46 43 62
1 3 8              49 51 45 35
1 4 7              43 37 41 61
1 4 8              40 42 43 34
1 5 7              57 61 45 75
1 5 8              54 66 47 48
1 6 7              57 25 48 84
1 6 8              54 30 50 57
2 3 7              52 34 59 56
2 3 8              49 39 61 29
2 4 7              43 25 57 55
2 4 8              40 30 59 28
2 5 7              57 49 61 69
2 5 8              54 54 63 42
2 6 7              57 13 64 78
2 6 8              54 18 66 51
Martin Ender
quelle
Gibt es ein Brett, auf dem immer ein Spieler gewinnt, unabhängig von der Kombination?
ThreeFx
@ThreeFx Da die Untergrenze für die Anzahl der Siedlungen pro Spieler 1 beträgt, ist das ziemlich einfach einzurichten. ;) Aber mit der gleichen Anzahl von Siedlungen für jeden Spieler weiß ich es nicht wirklich.
Martin Ender

Antworten:

5

Python 2, 367 Bytes

T=range(20)
N=lambda r,c:{(a,b)for a,b in{(r+x/3-1,c+x%3-1+(x/3!=1)*r%2)for x in[0,1,3,5,6,7]}if-1<b<20>a>-1}
def S(B):
 def F(r,c):j=J[r][c]!=i;J[r][c]*=j;j or map(F,*zip(*N(r,c)));return j
 J=map(list,B);X=lambda r,c,x,y:x+y in{B[r][c]+B[a][b]for a,b in N(r,c)};return[sum((i in B[r])+20*(3*X(r,c,"C",i)-~X(r,c,i,"W")-F(r,c))for r in T for c in T)/20for i in"1234"]

Das Programm verwendet die Punkte 1, 3 und 7. Die Eingabe ist eine Liste von Zeichenlisten, die jede Zelle darstellen. Um das Beispielboard einfach zu testen, können wir Folgendes tun:

board = """
3 3 W . . . 4 . 4 . . 2 W . 4 . . 4 . 4
 3 M W W . 1 1 . . 4 2 W . 3 C 4 4 . . 4
3 M 2 2 W 1 1 1 T 3 2 W 4 3 . 1 4 . 4 .
 M M . W 2 2 . . . 2 2 W 3 . 1 1 1 . . .
. 4 M . W W 2 2 2 2 W W 3 . 1 4 . T . .
 . . . . . W W W W W . 3 C 1 . . 2 2 2 2
. T 1 1 1 1 . . 2 . . 4 . . . 2 2 M M M
 4 . W 4 . C 4 4 . . . . . . 2 M M M M M
. 4 W W . . . 4 M . . W . W . 2 2 2 M M
 . . . . . . . M M . . W W . . . . 2 M .
. . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 . 1
 M 3 3 . . . . . . . . 4 . T 2 . 2 4 1 .
M M . C . 4 . 4 . . . . . 1 2 4 2 1 1 .
 M . . 1 . 4 . . . . M M 1 2 . . 2 1 . .
. . . W 1 1 4 1 1 . . . 1 2 . . 2 W W W
 . . 1 1 W 1 T . 1 1 1 1 T . . 2 W . 4 .
. 1 1 W . 3 3 . . . . . . . . 2 W 4 C 3
 C 1 3 3 3 . 3 . 4 . 4 . 4 . . 2 W 1 1 M
4 3 3 4 . M 4 3 . . . . . . . 2 W . . .
 . . . 4 . M M 3 . . 4 4 . 4 . 2 W W . .
"""

board = [row.split() for row in board.strip().split("\n")]
print S(board)

# [52, 46, 43, 62]

Umgang mit dem Hex-Gitter

Da wir uns in einem Hex-Raster befinden, müssen wir etwas anders mit den Nachbarn umgehen. Wenn wir ein traditionelles 2D-Gitter als Repräsentation verwenden, dann (1, 1)haben wir:

. N N . .       . N N . .                (0, 1), (0, 2)            (-1, 0), (-1, 1)
 N X N . .  ->  N X N . .  -> Neighbours (1, 0), (1, 2) -> Offsets (0, -1), (0, 1)
. N N . .       . N N . .                (2, 1), (2, 2)            (1, 0), (1, 1)

Bei näherer Betrachtung stellen wir fest, dass die Offsets von der Parität der Zeile abhängen, in der Sie sich befinden. Das obige Beispiel gilt für ungerade Zeilen, aber in geraden Zeilen sind die Offsets

(-1, -1), (-1, 0), (0, -1), (0, 1), (1, -1), (1, 0)

Das einzige, was sich geändert hat, ist, dass die zweite Koordinate des 1., 2., 5. und 6. Paares um 1 verringert wurde.

Die Lambda-Funktion Nnimmt ein Koordinatenpaar (row, col)und gibt alle Nachbarn der Zelle innerhalb des Gitters zurück. Das innere Verständnis erzeugt die obigen Offsets, indem es sie aus einer einfachen Basis-3-Codierung extrahiert, die zweite Koordinate inkrementiert, wenn die Zeile ungerade ist, und die Offsets der fraglichen Zelle hinzufügt, um die Nachbarn zu erhalten. Das äußere Verständnis filtert dann und lässt nur die Nachbarn übrig, die sich innerhalb der Grenzen des Gitters befinden.

Ungolfed

def neighbours(row, col):
    neighbour_set = set()

    for dr, dc in {(-1,-1), (-1,0), (0,-1), (0,1), (1,-1), (1,0)}:
        neighbour_set.add((row + dr, col + dc + (1 if dr != 0 and row%2 == 1 else 0)))

    return {(r,c) for r,c in neighbour_set if 20>r>-1 and 20>c>-1}

def solve(board):
    def flood_fill(char, row, col):
        # Logic negated in golfed code to save a few bytes
        is_char = (dummy[row][col] == char)
        dummy[row][col] = "" if is_char else dummy[row][col]

        if is_char:
            for neighbour in neighbours(row, col):
                flood_fill(char, *neighbour)

        return is_char

    def neighbour_check(row, col, char1, char2):
        return board[row][col] == char1 and char2 in {board[r][c] for r,c in neighbours(row, col)}

    dummy = [row[:] for row in board] # Need to deep copy for the flood fill
    scores = [0]*4

    for i,char in enumerate("1234"):
        for row in range(20):
            for col in range(20):
                scores[i] += (char in board[row])                        # Score 1
                scores[i] += 20 * 3*neighbour_check(row, col, "C", char) # Core score
                scores[i] += 20 * neighbour_check(row, col, char, "W")   # Score 3
                scores[i] += 20 * flood_fill(char, row, col)             # Score 7

        # Overcounted everything 20 times, divide out
        scores[i] /= 20

    return scores
Sp3000
quelle
Kann das def Fnicht eine separate Funktion sein, sondern eine interne Funktion? Kann nicht kentfernt werden def F:?
Justin
@Quincunx Fist die Funktion zum Füllen von Fluten und muss aufgerufen werden J, damit die Übergabe Jals Parameter gespeichert werden kann. Du hast aber recht k, danke :) (der neue Code sieht jedoch etwas funky aus, da er auf Kurzschlüsse angewiesen ist)
Sp3000
2

Antwortsatzprogrammierung, 629 Bytes

d(X,Y):-b(X,Y,_).p(1;2;3;4).n(X,Y,(((X-2;X+2),Y);((X-1;X+1),(Y-1;Y+1)))):-d(X,Y).n(X,Y,I,J):-n(X,Y,(I,J));d(I,J).t(X,Y,P):-n(X,Y,I,J);b(I,J,P).s(c,P,S*3):-S={t(X,Y,P):b(X,Y,"C")};p(P).s(1,P,S*1):-S=#count{r(Y):b(_,Y,P)};p(P).s(3,P,S):-S={b(X,Y,P):t(X,Y,"W")};p(P).o(X,Y,Y+X*100):-d(X,Y).h(P,X,Y,I,J):-o(X,Y,O);o(I,J,Q);O<Q;n(X,Y,I,J);b(X,Y,P);b(I,J,P);p(P).h(P,X,Y,I,J):-o(X,Y,O);o(I,J,Q);O<Q;h(P,X,Y,K,L);n(K,L,I,J);b(I,J,P);p(P).c(P,X,Y):-h(P,X,Y,_,_);not h(P,_,_,X,Y).c(P,X,Y):-{h(P,X,Y,_,_);h(P,_,_,X,Y)}0;b(X,Y,P);p(P).s(7,P,S):-S=#count{c(P,X,Y):c(P,X,Y)};p(P).s(t,P,C+S+T+U):-s(c,P,C);s(1,P,S);s(3,P,T);s(7,P,U).#shows/3.

ASP gehört zur Familie der logischen Programmiersprachen, die hier vom Potassco-Framework verkörpert werden , insbesondere Clingo (Grounder Gringo + Solver Clasp). Aufgrund der Paradigmenbeschränkung kann ein gegebenes Board nicht direkt als Ausgabe verwendet werden, sodass eine Vorverarbeitung der Daten erforderlich ist (hier in Python ausgeführt). Diese Vorverarbeitung wird in der Gesamtbytebewertung nicht mitgezählt.

Es ist mein erster Code Golf, und das Ziel ist mehr, eine Sprache zu zeigen, die ich liebe, die ich noch nie zuvor im Golf gesehen habe, als das Spiel wirklich zu gewinnen. Außerdem bin ich kein ASP-Experte, daher können viele Code-Optimierungen mit Sicherheit durchgeführt werden, um Ergebnisse in weniger Bytes zu erzielen.

Wissensrepräsentation

Es gibt den Python-Code, der Board in Atome umwandelt:

def asp_str(v):
    return ('"' + str(v) + '"') if v not in '1234' else str(v)

with open('board.txt') as fd, open('board.lp', 'w') as fo:
        [fo.write('b('+ str(x) +','+ str(y) +','+ asp_str(v) +').\n')
         for y, line in enumerate(fd)
         for x, v in enumerate(line) if v not in ' .\n'
        ]

Zum Beispiel sind die Atome b (für __b__board) für die erste Zeile des Beispielboards wie folgt:

b(0,0,3).
b(2,0,3).
b(4,0,"W").
b(12,0,4).
b(16,0,4).
b(22,0,2).
b(24,0,"W").
b(28,0,4).
b(34,0,4).
b(38,0,4).

Wobei b (0,0,3) ein Atom ist, das beschreibt, dass Spieler 3 eine Siedlung bei Koordinaten (0; 0) hat.

ASP-Lösung

Es gibt den ASP-Code mit vielen optionalen Punkten:

% input : b(X,Y,V) with X,Y the coordinates of the V value

domain(X,Y):- b(X,Y,_).
player("1";"2";"3";"4").

% neighbors of X,Y
neighbors(X,Y,((X-2,Y);(X+2,Y);((X-1;X+1),(Y-1;Y+1)))) :- domain(X,Y).
neighbors(X,Y,I,J):- neighbors(X,Y,(I,J)) ; domain(I,J).

% Player is next to X,Y iff has a settlement next to.
next(X,Y,P):- neighbors(X,Y,I,J) ; b(I,J,P).


% SCORES

% Core score : 3 point for each Castle "C" with at least one settlement next to.
score(core,P,S*3):- S={next(X,Y,P): b(X,Y,"C")} ; player(P).

% opt1: 1 point per settled row
score(opt1,P,S*1):- S=#count{row(Y): b(_,Y,P)} ; player(P).

% opt2: 2 point per settlement on the most self-populated row
% first, defines how many settlements have a player on each row
rowcount(P,Y,H):- H=#count{col(X): b(X,Y,P)} ; domain(_,Y) ; player(P).
score(opt2,P,S*2):- S=#max{T: rowcount(P,Y,T)} ; player(P).

% opt3: 1 point for each settlements next to a Water "W".
score(opt3,P,S):- S={b(X,Y,P): next(X,Y,"W")} ; player(P).

% opt4: 1 point for each settlements next to a Mountain "M".
score(opt4,P,S):- S={b(X,Y,P): next(X,Y,"M")} ; player(P).

% opt5:
%later…

% opt6:
%later…

% opt7: 1 point for each connected component of settlement
% first we need each coord X,Y to be orderable.
% then is defined path/5, that is true iff exists a connected component of settlement of player P
%   that links X,Y to I,J
% then is defined the connected component atom that give the smaller coords in each connected component
% then computing the score.
order(X,Y,Y+X*100):- domain(X,Y).
path(P,X,Y,I,J):- order(X,Y,O1) ; order(I,J,O2) ; O1<O2 ; % order
                  neighbors(X,Y,I,J) ; b(X,Y,P) ; b(I,J,P) ; player(P). % path iff next to
path(P,X,Y,I,J):- order(X,Y,O1) ; order(I,J,O2) ; O1<O2 ; % order
                  path(P,X,Y,K,L) ; neighbors(K,L,I,J) ; % path if path to next to
                  b(I,J,P) ; player(P).
concomp(P,X,Y):- path(P,X,Y,_,_) ; not path(P,_,_,X,Y). % at least two settlements in the connected component
concomp(P,X,Y):- 0 { path(P,X,Y,_,_) ; path(P,_,_,X,Y) } 0 ; board(X,Y,P) ; player(P). % concomp of only one settlements
score(opt7,P,S):- S=#count{concomp(P,X,Y): concomp(P,X,Y)} ; player(P).

% opt8: 0.5 point for each settlement in the bigger connected component
%later…


% total score:
score(total,P,C+S1+S2+S3):- score(core,P,C) ; score(opt1,P,S1) ; score(opt3,P,S2) ; score(opt7,P,S3).

#show. # show nothing but the others show statements
#show total_score(P,S): score(total,P,S).
%#show score/3. % scores details

Dieses Programm kann mit dem folgenden Befehl gestartet werden:

clingo board.lp golf.lp 

Und wird nur eine Lösung finden (es ist ein Beweis, dass es nur einen Weg gibt, die Punkte zu verteilen):

s(c,1,18) s(c,2,0) s(c,3,15) s(c,4,12) s(1,1,14) s(1,2,20) s(1,3,12) s(1,4,16) s(3,1,13) s(3,2,21) s(3,3,10) s(3,4,5) s(7,1,7) s(7,2,5) s(7,3,6) s(7,4,29) s(t,1,52) s(t,2,46) s(t,3,43) s(t,4,62)

Wobei s (7,3,6) besagt, dass Spieler 3 mit der optionalen Punktzahl 7 6 Punkte gewinnt, und s (t, 4,62) besagt, dass Spieler 4 insgesamt 62 Punkte gewinnt (Kern + 1 + 3 + 7).

Einfach zu analysieren, um einen schicken Tisch zu haben!

Aluriak
quelle