Zdobądź punkty w grze Kingdom Builder

16

Chcę tutaj wypróbować nową formę golfa kodowego. Podobnie jak w przypadku bonusów, nie wszystkie części wyzwania muszą zostać ukończone, ale każda odpowiedź musi implementować podzbiór o określonej wielkości (i istnieje rdzeń, który każda odpowiedź musi wdrożyć). Tak więc oprócz gry w golfa wyzwanie polega również na wybraniu zestawu funkcji, które dobrze do siebie pasują.

Zasady

Kingdom Builder to gra planszowa, rozgrywana na siatce heksów (spiczastych). Plansza składa się z czterech (losowych) ćwiartek, z których każda ma 10x10 komórek heksadecymalnych (więc pełna plansza będzie miała wymiary 20 x 20). Na potrzeby tego wyzwania każda komórka heksadecymalna zawiera albo wodę ( W), albo górę ( M) miasto (T ), zamek ( C) lub jest pusta ( .). Tak mógłby wyglądać kwadrant

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

Drugi rząd będzie zawsze przesunięty w prawo od pierwszego rzędu. Gracze1 do 4można umieścić do 40 osiedli każdy na pustych komórek (po pewnych zasad, które będziemy ignorować do tego wyzwania). Możliwa plansza na końcu gry jest następująca:

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

Będziemy nazywać ćwiartki jak

1 2
3 4

Twoim zadaniem będzie zdobycie takiej tablicy. Jest jeden wynik podstawowy, który jest zawsze używany, i 8 wyników opcjonalnych, z których 3 są wybierane dla każdej gry. Poniżej opiszę wszystkie 9 wyników i wykorzystam powyższą konfigurację jako przykład, ile punktów zdobędzie każdy gracz.

† W tej grze jest 10 punktów, ale pominę dwa, ponieważ nikt nie chce grać w golfa.

Podstawowy wynik. Gracz otrzymuje 3 punkty za każdy Castle, obok którego znajduje się osada.Przykładowe wyniki: 18, 0, 15, 12.

Opcjonalne wyniki.

  1. Gracz otrzymuje 1 punkt za każdy poziomy rząd, w którym ma co najmniej jedną osadę.

    Przykładowe wyniki: 14, 20, 12, 16.

  2. Dla każdego gracza znajdź poziomy rząd, w którym znajduje się większość jego osiedli (wybierz dowolny w przypadku remisu). Gracz otrzymuje 2 punkty za każdą osadę w tym rzędzie.

    Przykładowe wyniki: 14 (wiersz 16), 8 (wiersz 4, 5 lub 6), 28 (wiersz 11), 10 (wiersz 1).

  3. Gracz otrzymuje 1 punkt za każdą osadę budowaną obokW .

    Przykładowe wyniki: 13, 21, 10, 5.

  4. Gracz otrzymuje 1 punkt za każdą osadę obokM góry.

    Przykładowe wyniki: 4, 12, 8, 4.

  5. Policz osadę każdego gracza w każdej ćwiartce. Na kwadrant gracze z największą liczbą osad otrzymują po 12 punktów , gracze z drugą co do wielkości liczbą osad otrzymują po 6 punktów .

    Przykładowe wyniki: 18 (6 + 0 + 6 + 6), 36 (12 + 12 + 0 + 12), 12 (0 + 0 + 12 + 0), 18 (12 + 6 + 0 + 0).

  6. Dla każdego gracza określ kwadrant, w którym mają najmniejszą liczbę osad. Gracz otrzymuje 3 punkty za każdą osadę w tej ćwiartce.

    Przykładowe wyniki: 18 (kwadrant 2), 0 (kwadrant 3), 15 (kwadrant 1 lub 2), 27 (kwadrant 3).

  7. Gracz otrzymuje 1 punkt za każdą połączoną grupę osad.

    Przykładowe wyniki: 7, 5, 6, 29.

  8. Gracz otrzymuje 1 punkt za każde 2 osady w największej grupie połączonych osad.

    Przykładowe wyniki: 4, 10, 8, 2.

Wyzwanie

Podobnie jak w grze , wybierzesz 3 opcjonalne wyniki i zdobędziesz planszę na podstawie wyniku podstawowego i tych trzech wyników. Twój kod powinien wygenerować listę 4 wyników. Istnieje jedno ograniczenie wyboru: pogrupowałem wyniki na 3 grupy, a ty musisz wdrożyć po jednej z każdej grupy:

  • Zaimplementuj jeden z 1 i 2 .
  • Zaimplementuj jeden z 3, 4, 5 i 6 .
  • Zaimplementuj jeden z 7 i 8 .

Możesz napisać program lub funkcję, przyjmując dane wejściowe przez STDIN, argument wiersza poleceń, monit lub parametr funkcji. Możesz zwrócić wynik lub wydrukować go do STDOUT.

Możesz wybrać dowolny dogodny format listy / łańcucha 1D lub 2D dla danych wejściowych. Być może nie używać wykres z pełną informacją przylegania. Oto kilka dobrych lektur na siatkach heksadecymalnych, jeśli potrzebujesz inspiracji.

Dane wyjściowe mogą być również w dowolnym wygodnym, jednoznacznym formacie listy lub ciągu.

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Dalsze założenia

Możesz założyć, że ...

  • ... każdy gracz ma co najmniej 1 osadę i nie ma więcej niż 40 osad każdego gracza.
  • ... każdy kwadrant zawiera albo jedno miasto i dwa zamki, albo dwa miasta i jeden zamek.
  • ... miasta i zamki są wystarczająco daleko od siebie, tak że żadna osada nie może przylegać do dwóch z nich.

Przypadki testowe

Nadal korzystając z powyższej planszy, oto poszczególne wyniki dla wszystkich możliwych wyborów mechanizmów oceniania:

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
źródło
Czy istnieje plansza, w której jeden gracz zawsze wygrywa, niezależnie od kombinacji?
ThreeFx
@ThreeFx Ponieważ dolna granica liczby rozliczeń na gracza wynosi 1, konfiguracja jest dość prosta. ;) Ale przy takiej samej liczbie rozliczeń dla każdego gracza, tak naprawdę nie wiem.
Martin Ender

Odpowiedzi:

5

Python 2, 367 bajtów

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

Program wykorzystuje wyniki 1, 3, 7. Dane wejściowe to lista list znaków reprezentujących każdą komórkę. Aby łatwo przetestować przykładową tablicę, możemy:

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]

Obsługa siatki heksadecymalnej

Ponieważ znajdujemy się na siatce heksadecymalnej, musimy nieco inaczej traktować sąsiadów. Jeśli użyjemy tradycyjnej siatki 2D jako naszej reprezentacji, wówczas (1, 1)mamy:

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

Przy bliższej inspekcji zdajemy sobie sprawę, że przesunięcia zależą od parzystości wiersza, w którym jesteś. Powyższy przykład dotyczy wierszy nieparzystych, ale w wierszach parzystych przesunięcia są

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

Jedyne, co się zmieniło, to to, że pierwsza, druga, piąta i szósta para miały drugą współrzędną zmniejszoną o 1.

Funkcja lambda N przyjmuje parę współrzędnych (row, col)i zwraca wszystkich sąsiadów komórki w siatce. Wewnętrzne zrozumienie generuje powyższe przesunięcia, wyodrębniając je z prostego kodowania podstawowego 3, zwiększając drugą współrzędną, jeśli rząd jest nieparzysty, i dodaje przesunięcia do danej komórki, aby dać sąsiadom. Zewnętrzne zrozumienie następnie filtruje, pozostawiając tylko sąsiadów, którzy znajdują się w granicach siatki.

Nie golfił

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
źródło
Czy nie może def Fbyć funkcją oddzielną, a nie wewnętrzną? Nie można kgo usunąć def F:?
Justin
@Quincunx Fjest funkcją wypełniania zalania i potrzebuje dostępu J, więc jest w środku, aby zaoszczędzić na przekazywaniu Jjako parametrze (eksperymentuję trochę, aby sprawdzić, czy uda mi się obejść głębokie kopiowanie). kAle masz rację , dziękuję :) (nowy kod wygląda jednak nieco funky, z powodu polegającego na zwarciu)
Sp3000,
2

Programowanie zestawu odpowiedzi, 629 bajtów

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 należy do rodziny logicznych języków programowania, tutaj wcielonej przez framework Potassco , w szczególności Clingo (grounder Gringo + solver Clasp). Ze względu na ograniczenie paradygmatu nie może brać podanej płyty bezpośrednio jako wyjścia, dlatego konieczne jest wstępne przetwarzanie danych (tutaj wykonywane w pythonie). To przetwarzanie wstępne nie jest liczone w całkowitej liczbie bajtów.

To mój pierwszy golf golfowy, a celem jest raczej pokazanie języka, którego kocham, którego nigdy wcześniej nie widziałem w golfie, niż wygrywanie gry. Co więcej, nie jestem ekspertem od ASP, więc z pewnością można przeprowadzić wiele optymalizacji kodu, aby uzyskać wyniki w mniejszej liczbie bajtów.

Reprezentacja wiedzy

Istnieje kod python, który przekształca płytkę w atomy:

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

Na przykład atomy b (dla __b__oard) podane w pierwszym wierszu przykładowej planszy są następujące:

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

Gdzie b (0,0,3) jest atomem, który opisuje, że gracz 3 ma osadę na współrzędnych (0; 0).

Rozwiązywanie ASP

Istnieje kod ASP z zaimplementowanymi wieloma opcjonalnymi wynikami:

% 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

Ten program można uruchomić za pomocą polecenia:

clingo board.lp golf.lp 

I znajdzie tylko jedno rozwiązanie (jest to dowód, że istnieje tylko jeden sposób na rozłożenie punktów):

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)

Gdzie s (7,3,6) mówi, że gracz 3 zyskuje 6 punktów z opcjonalnym wynikiem 7, a s (t, 4,62) mówi, że gracz 4 zyskuje w sumie 62 punkty (rdzeń + 1 + 3 + 7).

Łatwo parsować, aby mieć fantazyjny stół!

aluriak
źródło