Anota un juego de Kingdom Builder

16

Quiero probar una nueva forma de código de golf aquí. Al igual que las bonificaciones, no todas las partes del desafío deben completarse, pero cada respuesta debe implementar un subconjunto de cierto tamaño (y hay un núcleo que cada respuesta debe implementar). Por lo tanto, además del golf, este desafío también implica elegir un conjunto de características que combinen bien.

Las normas

Kingdom Builder es un juego de mesa que se juega en una cuadrícula hexadecimal (punta puntiaguda). El tablero está formado por cuatro cuadrantes (aleatorios), cada uno de los cuales tiene 10x10 celdas hexadecimales (por lo que un tablero completo será 20x20). Para los propósitos de este desafío, cada celda hexagonal contiene agua ( W), montaña ( M), una ciudad ( T), un castillo ( C) o está vacía ( .). Entonces un cuadrante podría verse como

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

La segunda fila siempre estará desplazada a la derecha de la primera fila. Los jugadores 1a 4pueden colocar hasta 40 asentamientos cada uno en las celdas vacías (siguiendo algunas reglas que vamos a pasar por alto para este desafío). Un posible tablero al final del juego es el siguiente:

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

Etiquetaremos los cuadrantes como

1 2
3 4

Su tarea será anotar dicho tablero. Hay un puntaje central que siempre se usa y 8 puntajes opcionales, 3 de los cuales se eligen para cada juego. A continuación, describiré los 9 puntajes y usaré la configuración anterior como ejemplo de cuántos puntos obtendría cada jugador.

† Hay 10 puntajes en el juego real, pero dejaré de lado dos porque nadie quiere jugar golf.

El puntaje central. Un jugador obtiene 3 puntos por cada Castle al que tiene un acuerdo al lado. Puntajes de ejemplo: 18, 0, 15, 12.

Los puntajes opcionales.

  1. Un jugador obtiene 1 punto por cada fila horizontal en la que tiene al menos un acuerdo.

    Puntajes de ejemplo: 14, 20, 12, 16.

  2. Para cada jugador, encuentre la fila horizontal en la que se encuentran la mayoría de sus asentamientos (elija cualquiera en caso de empate). Un jugador obtiene 2 puntos por cada liquidación en esa fila.

    Puntajes de ejemplo: 14 (fila 16), 8 (fila 4, 5 o 6), 28 (fila 11), 10 (fila 1).

  3. Un jugador obtiene 1 punto por cada asentamiento que se construya al lado de Wdespués.

    Puntajes de ejemplo: 13, 21, 10, 5.

  4. Un jugador obtiene 1 punto por cada asentamiento al lado de una Mmontaña.

    Puntajes de ejemplo: 4, 12, 8, 4.

  5. Cuente los asentamientos de cada jugador en cada cuadrante. Por cuadrante, los jugadores con el mayor número de acuerdos obtienen 12 puntos cada uno, los jugadores con el segundo mayor número de acuerdos obtienen 6 puntos cada uno.

    Puntajes de ejemplo: 18 (6 + 0 + 6 + 6), 36 (12 + 12 + 0 + 12), 12 (0 + 0 + 12 + 0), 18 (12 + 6 + 0 + 0).

  6. Para cada jugador, determine el cuadrante en el que tienen el menor número de asentamientos. Un jugador obtiene 3 puntos por cada asentamiento en ese cuadrante.

    Puntajes de ejemplo: 18 (Cuadrante 2), 0 (Cuadrante 3), 15 (Cuadrante 1 o 2), 27 (Cuadrante 3).

  7. Un jugador obtiene 1 punto por cada grupo conectado de asentamientos.

    Puntajes de ejemplo: 7, 5, 6, 29.

  8. Un jugador obtiene 1 punto por cada 2 asentamientos en el grupo más grande de asentamientos conectados del jugador.

    Puntajes de ejemplo: 4, 10, 8, 2.

El reto

Al igual que en el juego que se elija 3 de las puntuaciones opcionales, y la puntuación de una tabla determinada en base a la puntuación de núcleo y las tres puntuaciones. Su código debe producir una lista de 4 puntajes. Sin embargo, hay una restricción en la elección: he agrupado los puntajes en 3 grupos y usted debe implementar uno de cada grupo:

  • Implementar uno de 1 y 2 .
  • Implementar uno de 3, 4, 5 y 6 .
  • Implementar uno de 7 y 8 .

Puede escribir un programa o función, tomando datos a través de STDIN, argumento de línea de comando, indicador o parámetro de función. Puede devolver el resultado o imprimirlo en STDOUT.

Puede elegir cualquier formato conveniente de lista / cadena 1D o 2D para la entrada. Es posible que no utilice un gráfico con la información de adyacencia completa. Aquí hay una buena lectura sobre cuadrículas hexagonales si necesita inspiración.

Su salida también puede estar en cualquier formato de cadena o lista conveniente y no ambigua.

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Supuestos adicionales

Puedes suponer que ...

  • ... cada jugador tiene al menos 1 acuerdo y no hay más de 40 acuerdos de cada jugador.
  • ... cada cuadrante contiene una ciudad y dos castillos, o dos ciudades y un castillo.
  • ... las ciudades y los castillos están lo suficientemente separados, de modo que ningún asentamiento puede ser adyacente a dos de ellos.

Casos de prueba

Aún usando la tabla anterior, aquí están los puntajes individuales para todas las opciones posibles de mecanismos de puntuación:

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
fuente
¿Hay un tablero en el que un jugador siempre gana, independientemente de la combinación?
ThreeFx
@ThreeFx Dado que el límite inferior en el número de asentamientos por jugador es 1, es bastante sencillo de configurar. ;) Pero con el mismo número de acuerdos para cada jugador, en realidad no lo sé.
Martin Ender

Respuestas:

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

El programa utiliza puntajes 1, 3, 7. La entrada es una lista de listas de caracteres que representan cada celda. Para probar el tablero de ejemplo fácilmente, podemos hacer:

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]

Manejo de la cuadrícula hexadecimal

Como estamos en una cuadrícula hexadecimal, tenemos que tratar con los vecinos de manera un poco diferente. Si utilizamos una cuadrícula 2D tradicional como nuestra representación, entonces (1, 1)tenemos:

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

En una inspección más cercana, nos damos cuenta de que las compensaciones dependen de la paridad de la fila en la que se encuentra. El ejemplo anterior es para filas impares, pero en filas pares los desplazamientos son

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

Lo único que ha cambiado es que los pares primero, segundo, quinto y sexto han tenido su segunda coordenada disminuida en 1.

La función lambda Ntoma un par de coordenadas (row, col)y devuelve todos los vecinos de la celda dentro de la cuadrícula. La comprensión interna genera los desplazamientos anteriores extrayéndolos de una codificación simple de base 3, incrementando la segunda coordenada si la fila es impar y agrega los desplazamientos a la celda en cuestión para dar a los vecinos. La comprensión externa luego se filtra, dejando solo a los vecinos que están dentro de los límites de la cuadrícula.

Sin golf

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
fuente
¿No puede def Fser una función separada en lugar de una función interna? No se kpuede eliminar de def F:?
Justin
@Quincunx Fes la función de relleno de inundación y necesita acceso J, por lo que está en el interior para ahorrar en pasar Jcomo parámetro (experimentaré un poco para ver si puedo evitar la copia profunda). Sin kembargo, tienes razón , gracias :) (sin embargo, el nuevo código parece un poco raro, debido a que depende del cortocircuito)
Sp3000
2

Programación de conjunto de respuestas, 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 pertenece a la familia de lenguajes de programación lógica, aquí encarnada por el framework Potassco , en particular Clingo (Grounder Gringo + Solver Clasp). Debido a la limitación del paradigma, no puede tomar una placa dada directamente como salida, por lo que es necesario un preprocesamiento de los datos (aquí realizado en python). Este preprocesamiento no se cuenta en la puntuación total de bytes.

Es mi primer código de golf, y el objetivo es más mostrar un lenguaje que amo que nunca antes había visto en el golf, que ganar el juego. Además, estoy lejos de ser un experto en ASP, por lo que muchas optimizaciones del código se pueden realizar para obtener resultados en menos bytes.

representación del conocimiento

Existe el código de Python que convierte la placa en átomos:

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

Por ejemplo, los átomos b (para __b__oard) dados para la primera línea del tablero de ejemplo son los siguientes:

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

Donde b (0,0,3) es un átomo que describe que el jugador 3 tiene un asentamiento en las coordenadas (0; 0).

Resolución ASP

Existe el código ASP, con muchos puntajes opcionales implementados:

% 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

Este programa se puede iniciar con el comando:

clingo board.lp golf.lp 

Y encontrará solo una solución (es una prueba de que solo hay una forma de distribuir los puntos):

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)

Donde s (7,3,6) dice que el jugador 3 gana 6 puntos con la puntuación opcional 7, y s (t, 4,62) dice que el jugador 4 gana 62 puntos en total (núcleo + 1 + 3 + 7).

¡Fácil de analizar para tener una mesa elegante!

aluriak
fuente