Забей на игру Kingdom Builder

16

Я хочу попробовать новую форму кода гольф здесь. Подобно бонусам, не все части задания должны быть выполнены, но каждый ответ должен реализовывать подмножество определенного размера (и есть ядро, которое должен реализовывать каждый ответ). Так что помимо игры в гольф эта задача также включает в себя выбор набора функций, которые хорошо сочетаются друг с другом.

Правила

Kingdom Builder - настольная игра, в которую играют на (остроконечной) гекс-сетке. Доска состоит из четырех (рандомизированных) квадрантов, каждый из которых имеет 10x10 шестнадцатеричных ячеек (таким образом, полная доска будет 20x20). Для целей этого задания каждая гекс-клетка содержит либо воду ( W), гору ( M) город ( T), замок ( C), либо пусто ( .). Таким образом, квадрант может выглядеть

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

Второй ряд всегда будет смещен вправо от первого ряда. Игроки 1в 4можно разместить до 40 пунктов по каждой из пустых клеток (после некоторых правил , которые мы будем игнорировать для этой задачи). Возможная доска в конце игры следующая:

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

Мы будем обозначать квадранты как

1 2
3 4

Ваша задача будет забить такую ​​доску. Существует один основной счет, который всегда используется, и 8 дополнительных очков, 3 из которых выбираются для каждой игры. Далее я опишу все 9 баллов и воспользуюсь приведенной выше настройкой в ​​качестве примера того, сколько очков наберет каждый игрок.

† В реальной игре 10 очков, но я пропущу два, потому что никто не хочет играть в них.

Основная оценка. Игрок получает 3 очка за каждый Cцентр, рядом с которым находится поселение. Пример оценки: 18, 0, 15, 12.

Необязательные оценки.

  1. Игрок получает 1 очко за каждый горизонтальный ряд, в котором у него есть хотя бы одно поселение.

    Пример оценки: 14, 20, 12, 16.

  2. Для каждого игрока найдите горизонтальный ряд, в котором он большую часть своих поселений (выберите любой в случае ничьей). Игрок получает 2 очка за каждое поселение в этом ряду.

    Пример оценки: 14 (строка 16), 8 (строка 4, 5 или 6), 28 (строка 11), 10 (строка 1).

  3. Игрок получает 1 очко за каждое поселение, которое строится рядом с WАтером.

    Пример оценки: 13, 21, 10, 5.

  4. Игрок получает 1 очко за каждое поселение рядом с Mфонтаном.

    Пример оценки: 4, 12, 8, 4.

  5. Подсчитайте поселения каждого игрока в каждом квадранте. За квадрант игроки с наибольшим количеством поселений получают по 12 очков , а игроки с вторым по величине поселением получают 6 очков .

    Пример оценки: 18 (6 + 0 + 6 + 6), 36 (12 + 12 + 0 + 12), 12 (0 + 0 + 12 + 0), 18 (12 + 6 + 0 + 0).

  6. Для каждого игрока определите квадрант, в котором он имеет наименьшее количество поселений. Игрок получает 3 очка за каждое поселение в этом квадранте.

    Примеры оценок: 18 (квадрант 2), 0 (квадрант 3), 15 (квадрант 1 или 2), 27 (квадрант 3).

  7. Игрок получает 1 очко за каждую подключенную группу населенных пунктов.

    Пример оценки: 7, 5, 6, 29.

  8. Игрок получает 1 очко за каждые 2 поселения в самой большой группе связанных поселений игрока.

    Пример оценки: 4, 10, 8, 2.

Соревнование

Как и в игре, вы выберете 3 из дополнительных очков и оцените заданную доску на основе основного счета и этих трех очков. Ваш код должен составить список из 4 баллов. Тем не менее, есть одно ограничение на выбор: я сгруппировал оценки в 3 группы, и вы должны реализовать одну из каждой группы:

  • Реализуйте один из 1 и 2 .
  • Реализуйте один из 3, 4, 5 и 6 .
  • Реализуйте один из 7 и 8 .

Вы можете написать программу или функцию, используя ввод через STDIN, аргумент командной строки, приглашение или параметр функции. Вы можете вернуть результат или распечатать его в STDOUT.

Вы можете выбрать любой удобный 1D или 2D список / формат строки для ввода. Вы не можете использовать граф с полной информацией о смежности. Вот хорошее чтение по шестигранным сеткам, если вам нужно вдохновение.

Ваш вывод также может быть в любом удобном, однозначном списке или строковом формате.

Это код гольф, поэтому самый короткий ответ (в байтах) выигрывает.

Дальнейшие предположения

Вы можете предположить, что ...

  • ... у каждого игрока есть как минимум 1 поселение, и у каждого игрока не более 40 поселений.
  • ... каждый квадрант содержит либо один город и два замка, либо два города и один замок.
  • ... города и замки достаточно далеко друг от друга, так что ни одно поселение не может быть соседним с двумя из них.

Тестовые случаи

Все еще используя вышеупомянутую доску, вот отдельные оценки для всех возможных вариантов механизмов подсчета очков:

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
Мартин Эндер
источник
Есть ли доска, на которой всегда побеждает один игрок, независимо от комбинации?
ThreeFx
@ThreeFx Поскольку нижняя граница количества поселений на игрока равна 1, это довольно просто настроить. ;) Но с одинаковым количеством поселений для каждого игрока я на самом деле не знаю.
Мартин Эндер

Ответы:

5

Python 2, 367 байт

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

Программа использует оценки 1, 3, 7. Ввод представляет собой список списков символов, представляющих каждую ячейку. Чтобы легко проверить пример платы, мы можем сделать:

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]

Обработка шестнадцатеричной сетки

Поскольку мы находимся на шестнадцатеричной сетке, мы должны иметь дело с соседями немного по-другому. Если мы используем традиционную двумерную сетку в качестве нашего представления, то у (1, 1)нас есть:

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

При ближайшем рассмотрении мы понимаем, что смещения зависят от четности строки, в которой вы находитесь. Приведенный выше пример для нечетных строк, но для четных строк смещения

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

Единственное, что изменилось, это то, что у 1-й, 2-й, 5-й и 6-й пары вторая координата была уменьшена на 1.

Лямбда-функция Nпринимает пару координат(row, col) и возвращает всех соседей ячейки в сетке. Внутреннее понимание генерирует вышеуказанные смещения, извлекая их из простого базового кодирования 3, увеличивая вторую координату, если строка нечетная, и добавляет смещения к рассматриваемой ячейке, чтобы получить соседей. Внешнее понимание затем фильтруется, оставляя только соседей, которые находятся в пределах сетки.

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
источник
Не может ли def Fбыть отдельная функция, а не внутренняя функция? Не может kбыть удален из def F:?
Джастин
@Quincunx F- это функция заливки и ей нужен доступ J, поэтому она позволяет сэкономить при передаче Jв качестве параметра (я немного поэкспериментирую, чтобы узнать, можно ли обойти глубокое копирование). kХотя вы правы , спасибо :) (однако новый код выглядит немного странно из-за короткого замыкания)
Sp3000
2

Программирование набора ответов, 629 байт

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 относится к семейству языков логического программирования, воплощенному здесь фреймворком Potassco , в частности Clingo (Grounder Gringo + solver Clasp). Из-за ограничения парадигмы, он не может принимать данную плату напрямую в качестве вывода, поэтому необходима предварительная обработка данных (здесь выполняется на python). Эта предварительная обработка не учитывается в общем значении байта.

Это мой первый гольф-код, и цель состоит в том, чтобы показать язык, который я люблю, которого я никогда не видел в гольфе, а не выиграть игру. Более того, я далеко не эксперт в ASP, поэтому многие оптимизации кода, безусловно, могут быть выполнены для получения результатов в меньшем количестве байтов.

представление знаний

Существует код Python, который преобразует плату в атомы:

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

Например, атомы b (для __b__oard), указанные для первой строки примерной доски, являются следующими:

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

Где b (0,0,3) - это атом, который описывает, что у игрока 3 есть расчет в координатах (0; 0).

ASP решение

Существует код ASP с множеством реализованных необязательных оценок:

% 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

Эту программу можно запустить с помощью команды:

clingo board.lp golf.lp 

И найдет только одно решение (это доказательство того, что есть только один способ распределить точки):

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)

Где s (7,3,6) говорит, что игрок 3 набирает 6 очков с дополнительным счетом 7, а s (t, 4,62) говорит, что игрок 4 набирает в общей сложности 62 очка (ядро + 1 + 3 + 7).

Легко разобрать, чтобы иметь модный стол!

aluriak
источник