Skor game Kingdom Builder

16

Saya ingin mencoba bentuk kode golf baru di sini. Mirip dengan bonus, tidak semua bagian dari tantangan harus diselesaikan, tetapi setiap jawaban harus mengimplementasikan subset dengan ukuran tertentu (dan ada inti yang harus diterapkan oleh setiap jawaban). Jadi selain bermain golf, tantangan ini juga melibatkan pemilihan serangkaian fitur yang cocok bersama.

Aturan

Kingdom Builder adalah permainan papan, dimainkan di kisi hex (pointy-top). Papan terdiri dari empat kuadran (acak), yang masing-masing memiliki 10x10 sel heks (sehingga papan penuh akan menjadi 20x20). Untuk keperluan tantangan ini, setiap sel hex berisi air ( W), gunung ( M) kota ( T), kastil ( C) atau kosong ( .). Jadi kuadran bisa terlihat seperti

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

Baris kedua akan selalu diimbangi ke kanan dari baris pertama. Pemain 1untuk 4dapat menempatkan hingga 40 permukiman masing-masing pada sel kosong (mengikuti beberapa aturan yang akan kita mengabaikan untuk tantangan ini). Papan yang mungkin ada di akhir permainan adalah sebagai berikut:

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

Kami akan memberi label kuadran suka

1 2
3 4

Tugas Anda adalah untuk mencetak papan seperti itu. Ada satu skor inti yang selalu digunakan, dan 8 skor opsional, 3 di antaranya dipilih untuk setiap game. Berikut ini, saya akan menggambarkan semua 9 skor dan menggunakan pengaturan di atas sebagai contoh untuk berapa banyak poin yang akan didapat setiap pemain.

† Ada 10 skor dalam permainan yang sebenarnya, tetapi saya akan meninggalkan dua karena tidak ada yang mau bermain golf.

Skor inti. Seorang pemain mendapat 3 poin untuk setiap Castle yang ada penyelesaiannya di sebelahnya. Skor contoh: 18, 0, 15, 12.

Skor opsional.

  1. Seorang pemain mendapat 1 poin untuk setiap baris horizontal di mana mereka memiliki setidaknya satu penyelesaian.

    Skor contoh: 14, 20, 12, 16.

  2. Untuk masing-masing pemain, temukan baris horizontal tempat sebagian besar penyelesaian mereka (pilih salah satu jika ada seri). Seorang pemain mendapat 2 poin untuk setiap penyelesaian di baris itu.

    Skor contoh: 14 (baris 16), 8 (baris 4, 5 atau 6), 28 (baris 11), 10 (baris 1).

  3. Seorang pemain mendapat 1 poin untuk setiap penyelesaian yang dibangun di sebelah Water.

    Skor contoh: 13, 21, 10, 5.

  4. Seorang pemain mendapat 1 poin untuk setiap penyelesaian di sebelah Mountain.

    Skor contoh: 4, 12, 8, 4.

  5. Hitung penyelesaian setiap pemain di setiap kuadran. Per kuadran, pemain dengan jumlah permukiman terbesar mendapat masing-masing 12 poin , pemain dengan jumlah permukiman terbesar kedua mendapat masing-masing 6 poin .

    Skor contoh: 18 (6 + 0 + 6 + 6), 36 (12 + 12 + 0 + 12), 12 (0 + 0 + 12 + 0), 18 (12 + 6 + 0 + 0).

  6. Untuk setiap pemain menentukan kuadran di mana mereka memiliki jumlah pemukiman paling sedikit. Seorang pemain mendapat 3 poin untuk setiap penyelesaian di kuadran itu.

    Skor contoh: 18 (Kuadran 2), 0 (Kuadran 3), 15 (Kuadran 1 atau 2), 27 (Kuadran 3).

  7. Seorang pemain mendapat 1 poin untuk setiap kelompok pemukiman yang terhubung.

    Skor contoh: 7, 5, 6, 29.

  8. Seorang pemain mendapat 1 poin untuk setiap 2 pemukiman di kelompok pemukiman terhubung terbesar pemain.

    Skor contoh: 4, 10, 8, 2.

Tantangan

Seperti dalam permainan, Anda akan memilih 3 dari skor opsional, dan skor papan yang diberikan berdasarkan skor inti dan tiga skor tersebut. Kode Anda harus menghasilkan daftar 4 skor. Namun ada satu batasan pada pilihan: Saya telah mengelompokkan skor menjadi 3 kelompok, dan Anda harus menerapkan salah satu dari masing-masing kelompok:

  • Terapkan salah satu dari 1 dan 2 .
  • Terapkan salah satu dari 3, 4, 5 dan 6 .
  • Terapkan salah satu dari 7 dan 8 .

Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN, argumen baris perintah, prompt atau parameter fungsi. Anda dapat mengembalikan hasilnya atau mencetaknya ke STDOUT.

Anda dapat memilih format daftar / string 1D atau 2D yang nyaman untuk input. Anda tidak boleh menggunakan grafik dengan informasi kedekatan penuh. Berikut ini adalah bacaan yang bagus di hex grid jika Anda membutuhkan inspirasi.

Output Anda juga mungkin dalam format string atau daftar yang mudah, tidak ambigu.

Ini kode golf, jadi jawaban tersingkat (dalam byte) menang.

Asumsi Lebih Lanjut

Anda boleh berasumsi bahwa ...

  • ... setiap pemain memiliki setidaknya 1 penyelesaian dan tidak ada lebih dari 40 penyelesaian dari setiap pemain.
  • ... setiap kuadran berisi satu kota dan dua kastil, atau dua kota dan satu kastil.
  • ... kota dan kastil cukup berjauhan, sehingga tidak ada pemukiman yang berdekatan dengan keduanya.

Uji Kasus

Masih menggunakan papan di atas, berikut adalah skor individu untuk semua pilihan kemungkinan mekanisme penilaian:

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
sumber
Apakah ada papan di mana satu pemain selalu menang, terlepas dari kombinasinya?
ThreeFx
@ThreeFx Karena batas bawah pada jumlah penyelesaian per pemain adalah 1, itu cukup mudah untuk diatur. ;) Tetapi dengan jumlah penyelesaian yang sama untuk setiap pemain, saya sebenarnya tidak tahu.
Martin Ender

Jawaban:

5

Python 2, 367 byte

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 ini menggunakan skor 1, 3, 7. Input adalah daftar daftar karakter yang mewakili setiap sel. Untuk menguji papan contoh dengan mudah, kita dapat melakukan:

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]

Menangani hex grid

Karena kita berada di hex grid, kita harus berurusan dengan tetangga sedikit berbeda. Jika kita menggunakan kisi 2D tradisional sebagai representasi kita, maka (1, 1)kita memiliki:

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

Pada pemeriksaan lebih dekat, kami menyadari bahwa offset tergantung pada paritas baris Anda. Contoh di atas adalah untuk baris ganjil, tetapi pada baris genap pun

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

Satu-satunya hal yang telah berubah adalah bahwa pasangan ke-1, ke-2, ke-5 dan ke-6 mengalami penurunan koordinat kedua sebesar 1.

Fungsi lambda Nmengambil pasangan koordinat(row, col) dan mengembalikan semua tetangga sel dalam grid. Pemahaman bagian dalam menghasilkan offset di atas dengan mengekstraksi mereka dari pengkodean basis 3 sederhana, menambah koordinat kedua jika barisnya ganjil dan menambahkan offset ke sel yang bersangkutan untuk diberikan kepada tetangga. Pemahaman luar kemudian menyaring, hanya menyisakan tetangga yang berada dalam batas-batas grid.

Tidak disatukan

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
sumber
Tidak bisakah def Ffungsi yang terpisah dan bukan fungsi internal? Tidak kdapat dihapus dari def F:?
Justin
@ Quincunx Fadalah fungsi pengisian banjir dan perlu akses J, jadi ada di bagian dalam untuk menghemat lewat Jsebagai parameter (saya akan bereksperimen sedikit untuk melihat apakah saya bisa menyelesaikan penyalinan yang dalam). Anda benar tentang kmeskipun, terima kasih :) (kode baru terlihat sedikit funky namun, karena mengandalkan hubungan arus pendek)
Sp3000
2

Answer Set Programming, 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 milik keluarga bahasa pemrograman logika, di sini diinkarnasi oleh kerangka kerja Potassco , khususnya Clingo (grounder Gringo + solver Clasp). Karena keterbatasan paradigma, itu tidak dapat menerima papan yang diberikan secara langsung sebagai output, sehingga diperlukan preprocessing data (di sini dilakukan dengan python). Preprocessing ini tidak dihitung dalam skor total byte.

Ini golf kode pertama saya, dan tujuannya lebih untuk menunjukkan bahasa yang saya sukai yang belum pernah saya lihat sebelumnya di golf, daripada benar-benar memenangkan permainan. Selain itu, saya jauh dari seorang ahli dalam ASP, begitu banyak optimisasi kode yang pasti dapat dilakukan untuk hasil dalam lebih sedikit byte.

representasi pengetahuan

Ada kode python yang mengubah papan dalam atom:

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

Misalnya, atom b (untuk __b__oard) yang diberikan untuk baris pertama papan contoh adalah sebagai berikut:

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

Di mana b (0,0,3) adalah atom yang menggambarkan bahwa pemain 3 memiliki penyelesaian pada koordinat (0; 0).

Pemecahan ASP

Ada kode ASP, dengan banyak skor opsional diterapkan:

% 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

Program ini dapat diluncurkan dengan perintah:

clingo board.lp golf.lp 

Dan hanya akan menemukan satu solusi (ini merupakan bukti bahwa hanya ada satu cara untuk mendistribusikan poin):

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)

Di mana s (7,3,6) mengatakan bahwa pemain 3 memperoleh 6 poin dengan skor opsional 7, dan s (t, 4,62) mengatakan bahwa pemain 4 mendapatkan total 62 poin (inti + 1 + 3 + 7).

Mudah diurai untuk memiliki meja mewah!

aluriak
sumber