Pontue um jogo do Kingdom Builder

16

Quero experimentar uma nova forma de código de golfe aqui. Semelhante aos bônus, nem todas as partes do desafio precisam ser concluídas, mas cada resposta precisa implementar um subconjunto de determinado tamanho (e há um núcleo que toda resposta precisa implementar). Portanto, além do golfe, esse desafio também envolve a escolha de um conjunto de recursos que combinam bem.

As regras

Kingdom Builder é um jogo de tabuleiro, jogado em uma grade hexagonal (pontuda). A placa é composta de quatro quadrantes (randomizados), cada um com 10x10 células hexadecimais (portanto, uma placa completa terá 20x20). Para os propósitos deste desafio, cada célula hexadecimal contém água ( W), montanha ( M) uma cidade ( T), um castelo ( C) ou está vazia ( .). Portanto, um quadrante pode parecer

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

A segunda linha será sempre deslocada para a direita a partir da primeira linha. Jogadores 1para 4pode colocar até 40 assentamentos cada um em células vazias (seguindo algumas regras que iremos ignorar para este desafio). Um possível tabuleiro no final do jogo é o seguinte:

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

Vamos rotular os quadrantes como

1 2
3 4

Sua tarefa será pontuar esse quadro. Há uma pontuação principal que é sempre usada e 8 pontuações opcionais, 3 das quais são escolhidas para cada jogo. A seguir, descreverei todas as 9 pontuações e usarei a configuração acima como exemplo para quantos pontos cada jogador obteria.

† Existem 10 pontuações no jogo atual, mas deixarei de fora duas, porque ninguém quer jogar golfe.

A pontuação do núcleo. Um jogador recebe 3 pontos para cada Castle ao lado de um acordo. Pontuações de exemplo: 18, 0, 15, 12.

As pontuações opcionais.

  1. Um jogador ganha 1 ponto por cada linha horizontal em que possui pelo menos um assentamento.

    Pontuações de exemplo: 14, 20, 12, 16.

  2. Para cada jogador, encontre a linha horizontal em que a maioria de seus assentamentos (escolha qualquer em caso de empate). Um jogador ganha 2 pontos por cada assentamento naquela linha.

    Pontuações de exemplo: 14 (linha 16), 8 (linha 4, 5 ou 6), 28 (linha 11), 10 (linha 1).

  3. Um jogador ganha 1 ponto por cada assentamento que é construído próximo a Water.

    Pontuações de exemplo: 13, 21, 10, 5.

  4. Um jogador ganha 1 ponto por cada assentamento próximo a uma Monça.

    Pontuações de exemplo: 4, 12, 8, 4.

  5. Conte os assentamentos de cada jogador em cada quadrante. Por quadrante, os jogadores com o maior número de assentamentos recebem 12 pontos cada, enquanto os jogadores com o segundo maior número de assentamentos recebem 6 pontos cada.

    Pontuações de exemplo: 18 (6 + 0 + 6 + 6), 36 (12 + 12 + 0 + 12), 12 (0 + 0 + 12 + 0), 18 (12 + 6 + 0 + 0).

  6. Para cada jogador, determine o quadrante em que eles têm o menor número de assentamentos. Um jogador ganha 3 pontos por cada assentamento naquele quadrante.

    Pontuações de exemplo: 18 (quadrante 2), 0 (quadrante 3), 15 (quadrante 1 ou 2), 27 (quadrante 3).

  7. Um jogador ganha 1 ponto para cada grupo conectado de assentamentos.

    Pontuações de exemplo: 7, 5, 6, 29.

  8. Um jogador ganha 1 ponto para cada 2 assentamentos no maior grupo de assentamentos conectados do jogador.

    Pontuações de exemplo: 4, 10, 8, 2.

O desafio

Como no jogo, você escolherá 3 das pontuações opcionais e pontuará um determinado tabuleiro com base na pontuação principal e nessas três pontuações. Seu código deve produzir uma lista de 4 pontuações. Há uma restrição à escolha: agrupei as pontuações em 3 grupos e você deve implementar uma de cada grupo:

  • Implemente um de 1 e 2 .
  • Implemente um dos 3, 4, 5 e 6 .
  • Implemente um dos 7 e 8 .

Você pode escrever um programa ou função, recebendo entradas via STDIN, argumento de linha de comando, prompt ou parâmetro de função. Você pode retornar o resultado ou imprimi-lo em STDOUT.

Você pode escolher qualquer formato conveniente de lista / sequência 1D ou 2D para a entrada. Você não pode usar um gráfico com informações completas sobre adjacência. Aqui está uma boa leitura sobre grades hexagonais, se você precisar de inspiração.

Sua saída também pode estar em qualquer formato conveniente, inequívoco de lista ou string.

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Suposições adicionais

Você pode assumir que ...

  • ... cada jogador tem pelo menos 1 assentamento e não há mais de 40 assentamentos de cada jogador.
  • ... cada quadrante contém uma cidade e dois castelos, ou duas cidades e um castelo.
  • ... cidades e castelos estão suficientemente distantes, de modo que nenhum assentamento possa ser adjacente a dois deles.

Casos de teste

Ainda usando o quadro acima, eis as pontuações individuais para todas as opções possíveis de mecanismos de pontuação:

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
fonte
Existe um quadro em que um jogador sempre vence, independentemente da combinação?
ThreeFx
@ThreeFx Como o limite inferior do número de acordos por jogador é 1, é bastante simples de configurar. ;) Mas com o mesmo número de acordos para cada jogador, eu realmente não sei.
Martin Ender

Respostas:

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

O programa usa as pontuações 1, 3, 7. Input é uma lista de listas de caracteres que representam cada célula. Para testar o quadro de exemplo facilmente, podemos fazer:

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]

Manuseando a grade hexadecimal

Como estamos em uma grade hexagonal, temos que lidar com os vizinhos de maneira um pouco diferente. Se usarmos uma grade 2D tradicional como nossa representação, então (1, 1)temos:

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

Em uma inspeção mais detalhada, percebemos que as compensações dependem da paridade da linha em que você está. O exemplo acima é para linhas ímpares, mas nas linhas pares as compensações são

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

A única coisa que mudou foi que os pares 1, 2, 5 e 6 tiveram sua segunda coordenada decrementada em 1.

A função lambda Nrecebe um par de coordenadas(row, col) e retorna todos os vizinhos da célula dentro da grade. A compreensão interna gera as compensações acima, extraindo-as de uma codificação simples da base 3, incrementando a segunda coordenada se a linha for ímpar e adicionando as compensações à célula em questão para fornecer aos vizinhos. A compreensão externa é filtrada, deixando apenas os vizinhos que estão dentro dos limites da grade.

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
fonte
Não pode def Fser uma função separada e não uma função interna? Não pode kser removido de def F:?
Justin
O @Quincunx Fé a função de preenchimento de inundação e precisa ser acessada J; portanto, é por dentro para economizar a passagem Jcomo parâmetro (vou experimentar um pouco para ver se consigo contornar a cópia profunda). Você está certo sobre kembora, graças :) (o novo código parece um pouco descolada no entanto, devido a depender de curto-circuito)
SP3000
2

Conjunto de respostas Programação, 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.

O ASP pertence à família da linguagem de programação lógica, aqui encarnada pela estrutura Potassco , em particular o Clingo (Gringo + solver Clasp). Devido à limitação do paradigma, ele não pode receber diretamente a placa fornecida como saída, portanto, é necessário um pré-processamento dos dados (aqui realizado em python). Esse pré-processamento não conta na pontuação total de bytes.

É o meu primeiro código de golfe, e o objetivo é mais mostrar uma linguagem que eu amo que nunca vi no golfe, do que realmente ganhar o jogo. Além disso, estou longe de ser um especialista em ASP, e muitas otimizações do código certamente podem ser realizadas para obter resultados em menos bytes.

representação do conhecimento

Existe o código python que converte a placa em á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 exemplo, os átomos b (para __b__oard) dados para a primeira linha do quadro de exemplo são os seguintes:

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

Onde b (0,0,3) é um átomo que descreve que o jogador 3 tem um assentamento nas coordenadas (0; 0).

Resolução ASP

Existe o código ASP, com muitas pontuações opcionais implementadas:

% 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 pode ser iniciado com o comando:

clingo board.lp golf.lp 

E encontrará apenas uma solução (é uma prova de que há apenas uma maneira de distribuir os pontos):

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)

Onde s (7,3,6) diz que o jogador 3 ganha 6 pontos com pontuação opcional 7 es (t, 4,62) diz que o jogador 4 ganha 62 pontos no total (núcleo + 1 + 3 + 7).

Fácil de analisar para ter uma mesa elegante!

aluriak
fonte