Score a game of Kingdom Builder
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"]
The program uses scores 1, 3, 7. Input is a list of lists of chars representing each cell. To test the example board easily, we can do:
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]
Handling the hex grid
Since we are on a hex grid, we have to deal with neighbours a little differently. If we use a traditional 2D grid as our representation, then for (1, 1) we have:
. 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)
On closer inspection, we realise that the offsets depend on the parity of the row you're on. The above example is for odd rows, but on even rows the offsets are
(-1, -1), (-1, 0), (0, -1), (0, 1), (1, -1), (1, 0)
The only thing that has changed is that the 1st, 2nd, 5th and 6th pairs have had their second coordinate decremented by 1.
The lambda function N takes a coordinate pair (row, col) and returns all neighbours of the cell within the grid. The inner comprehension generates the above offsets by extracting them from a simple base 3 encoding, incrementing the second coordinate if the row is odd and adds the offsets to the cell in question to give the neighbours. The outer comprehension then filters, leaving just the neighbours that are within the bounds of the grid.
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
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 belongs to the logic programming language family, here incarnated by the Potassco framework, in particular Clingo(grounder Gringo + solver Clasp). Because of the paradigm limitation, it can't take given board directly as an output, so a preprocessing of the data is necessary (here performed in python). This preprocessing in not counted in the total byte score.
Its my first code golf, and the objective is more to show a language i love that i never seen before in golf, than really win the game. Moreover, i'm far from an expert in ASP, so many optimizations of the code can certainly be perform for results in less bytes.
knowledge representation
There is the python code that convert board in atoms :
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'
]
For example, atoms b (for __b__oard) given for the first line of example board are the followings :
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).
Where b(0,0,3) is an atom that describes that player 3 has a settlement at coordinates (0;0).
ASP solving
There is the ASP code, with many optional scores implemented :
% 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
This program can be launched with the command:
clingo board.lp golf.lp
And will find only one solution (its a proof that there is only one way to distribute the points):
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)
Where s(7,3,6) says that player 3 gains 6 points with optional score 7, and s(t,4,62) says that player 4 gains 62 points in total (core + 1 + 3 + 7).
Easy to parse to have a fancy table !