Граф Миллс в Девяти Мужских Моррисе

21

Вступление

Nine Mens's Morris (также называемый Mills) - настольная игра для двух игроков, в которую играют на следующей доске (изображение взято со связанной страницы Википедии):

Мельничная доска

У каждого игрока есть 9 человек, окрашенных в черно-белый цвет. Конкретные правила не важны для этой задачи, но проверьте страницу Википедии, если вы заинтересованы.

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

Задав в качестве входных данных сетку, представляющую определенное состояние платы, выведите общее количество фрез mс 0<=m<=8.
Три человека одного цвета образуют мельницу, когда они находятся в прямом ряду соединенных точек. b2чтобы f2не мельница , так как люди разного цвета. Кроме того, d2чтобы d5не образовывать мельницу , так как три точки должны быть подключены.
Доска на изображении выше содержит две мельницы, например. Один от f2до f6и один от e3до e5.

вход

Плата представлена ​​в виде двумерной сетки с 24 точками, которые соединены, как показано на рисунке выше. В примере используются буквы from a-gдля столбцов и цифры from 1-7для строк, но вы можете выбрать любой разумный формат ввода, если он отображает 24 уникальные координаты в одно из следующих состояний:

  • пустой
  • Взятый черным
  • Взято белым

Конкретное представление зависит от вас, вы не ограничены "b" или "w" для цветов.

Кроме того, ваш вклад может не содержать никакой дополнительной информации.

Дополнительные замечания

  • Вам не нужно отображать точки по каким-либо значениям. Если вы хотите принять входные данные в виде двумерного массива, это тоже хорошо. Но имейте в виду, что не все точки там используются, и что вы должны учитывать связи между ними.
  • Вход может быть пустым, в этом случае вы должны вывести ноль (пустая доска -> без фрез).
  • Поскольку у каждого игрока по 9 человек, входные данные никогда не будут содержать более 18 взятых очков.
  • Вы можете не указывать emtpy точки на входе и, следовательно, только те входные точки, которые взяты.
  • Ввод можно заказать любым способом. Вы не можете полагаться на конкретный заказ.
  • Вы можете предположить, что ввод всегда будет действительным. Это означает, что не будет более 9 человек каждого цвета, и что каждая точка будет уникальной.

правила

  • Уточните, какой формат ввода вы используете в своем решении. Предоставление примера запуска вашей программы приветствуется.
  • Функция или полная программа разрешены.
  • Правила по умолчанию для ввода / вывода.
  • Применяются стандартные лазейки .
  • Это , поэтому выигрывает меньшее количество байт. Tiebreaker является более ранним представлением.

Контрольные примеры

Формат ввода здесь представляет собой список кортежей с координатами, как в примере выше, в качестве первого элемента и состоянием точки второго элемента. Точка, выбранная белым цветом, помечена как «w», а точка, обозначенная черным, как «b». Все остальные точки опущены и пусты.

[( "А4", "ш"), ( "b2", "б"), ( "b4", "б"), ( "с4", "б"), ( "d1", "ш") , ( "d2", "ш"), ( "е3", "ш"), ( "е4", "ш"), ( "е5", "ш"), ( "F2", "б") , ("f4", "b"), ("f6", "b"), ("g4", "w")] -> 2
[( "A1", "б"), ( "а4", "б"), ( "а7", "б"), ( "b4", "б"), ( "с4", "б") , ("d3", "w"), ("d2", "w"), ("d1", "w")] -> 3
[] -> 0
[("b4", "b"), ("a4", b "), (" c4 ", w")] -> 0
[("b4", "b"), ("a4", b "), (" c4 ", b")] -> 1
[("a1", "b"), ("a4", "b"), ("a7", "b"), ("b2", "b"), ("b4", "b") , ("b6", "b"), ("c3", "b"), ("c4", "b"), ("c5", "b"), ("e3", "w") , ("e4", "w"), ("e5", "w"), ("f2", "w"), ("f4", "w"), ("f6", "w") , ("g1", "w"), ("g4", "w"), ("g7", "w")] -> 8

Удачного кодирования!

Denker
источник
Родственных - мало.
insertusername здесь
Я предполагаю, что цвета должны быть смежными и выровненными, но это немного неясно. Например, d2, d3, d5 одного цвета образуют мельницу?
Роберт Бенсон
@RobertBenson Нет, это не так, потому что d3и d5не связаны. Правила говорят: Three men of the same color form a mill when they are in a straight row of connected points.. Я добавил несколько примеров в этот раздел, чтобы прояснить ситуацию, спасибо за комментарий!
Денкер

Ответы:

4

APL (Dyalog Classic) , 26 25 байт

-1 спасибо FrownyFrog

≢{|∊(+/⍵⍪↓⍵),⊢/4 2⍴+⌿⍵}∩≢

Попробуйте онлайн!

Аргументом является массив 3x3x3 1(черный), ¯1(белый) и 0(пустой). Первое измерение находится вдоль глубины вложенности концентрических квадратов. Два других измерения расположены вдоль вертикальной и горизонтальной оси.

000---------001---------002
 |           |           |
 |  100-----101-----102  |
 |   |       |       |   |
 |   |  200-201-202  |   |
 |   |   |       |   |   |
010-110-210     212-112-012
 |   |   |       |   |   |
 |   |  220-221-222  |   |
 |   |       |       |   |
 |  120-----121-----122  |
 |           |           |
020---------021---------022

У нас есть мельница всякий раз, когда суммирование по любой оси дает 3или или ¯3, за исключением того, что мы должны отбросить четыре угла при суммировании по первой оси.

{} это функция с неявным аргументом

↓⍵является раскол - в нашем случае это превращает 3x3x3 куб в виде матрицы 3х3 вложенных длины 3 векторов

⍵⍪↓⍵ берет исходный куб и склеивает 3х3 матрицу из 3 векторов под ним, поэтому мы получаем смешанный массив скаляров и векторов 4х3х3

+/суммы по последней оси; это объединяет эффект суммирования исходного куба по последней оси ( +/⍵) и суммирования его по средней оси из-за того, что мы делим ( +/↓⍵)

Теперь мы должны позаботиться о специальном случае для первой оси.

+⌿⍵ суммы по первой оси, возвращающие матрицу 3х3

4 2⍴ но мы не должны подсчитывать углы, поэтому мы изменим форму матрицы 4x2 следующим образом:

ABC      AB
DEF  ->  CD
GHI      EF
         GH  ("I" disappears)

теперь нас интересует только последний столбец ( BDFH), поэтому мы используем идиому⊢/

,объединяется BDFHс матрицей, которую мы получили ранее для 2-й и 3-й оси ( BDFHи матрица, как оказалось, имеет начальный размер 4)

сглаживает все, что мы получили до сих пор, в один вектор

| принимает абсолютные значения

{ }∩≢ фильтрует только тройки - длина (≢) входа всегда равна 3

считает их

СПП
источник
Хех, я как раз собирался это предложить.
Адам
Можете ли вы присоединиться к chat.stackexchange.com/rooms/52405/apl на мгновение?
Адам
≢{|∊(+/⍵⍪↓⍵),⊢/4 2⍴+⌿⍵}∩≢короче :)
FrownyFrog
@FrownyFrog спасибо! Отредактировано в
нгн
4

JavaScript (ES6), 276 228 125 117 105 байт

a=>btoa`i·yø!9%z)ª»-ºü1j;ÝÈ%¥·¡ªÜ"·ç¹Ê1`.replace(/.../g,b=>(a[b[0]]+a[b[1]]+a[b[2]])/3&1||'').length

(приведенный выше содержит некоторые непечатаемые символы ascii, которые здесь не отображаются, так что вот версия без той, btoaкоторую можно скопировать и запустить)

a=>'abcdefghijklmnopqrstuvwxajvdksglpbehqtwimrfnucox'.replace(/.../g,b=>(a[b[0]]+a[b[1]]+a[b[2]])/3&1||'').length

Разбивает справочную строку на буквенные триплеты, совпадающие с ключами группы мельниц. Ввод осуществляется в форме объекта, где клавиши - это буквы a-x, начиная с левого нижнего края и заканчивая правым верхним, сначала перемещаясь слева направо. Значения 1для белого, -1черного и 0пустого.

пример

{b:1,d:-1,e:1,f:-1,i:1,k:-1,l:-1,m:1,n:-1,r:1,u:-1} => 2
{j:1,d:-1,k:-1,l:-1,b:1,e:1,i:1,m:1,r:1,f:-1,n:-1,u:-1,o:1} => 2
{a:-1,j:-1,v:-1,k:-1,l:-1,h:1,e:1,b:1} => 3
{} => 0
{k:-1,j:-1,l:1} => 0
{k:-1,j:-1,l:1} => 1
{a:-1,j:-1,v:-1,d:-1,k:-1,s:-1,g:-1,l:-1,p:-1,i:1,m:1,r:1,f:1,n:1,u:1,c:1,o:1,x:1} => 8

Эти примеры взяты из примеров OP, преобразованы в объект буквы-ключа и числа-значения. Первый из примера изображения, в то время как другие из примера набора.

Mwr247
источник
1
Хорошая работа! Вы можете сжать большую строку с atob.
ETHproductions
@ETHproductions Спасибо! Кажется, что он использует непечатаемые символы ascii, поэтому я добавлю и символы без них btoa. Также обнаружены некоторые другие улучшения, которые снижают его еще больше.
Mwr247 25.02.16
2

Mathematica, 217 131 байт

Хотя я уверен, что это не особенно конкурентоспособно, вот запись для вас.

Count[Total/@{{a1,d1,g1},{b2,d2,f2},{c3,d3,e3},{a4,b4,c4},{e4,f4,g4},{c5,d5,e5},{b6,d6,f6},{a7,d7,g7},{a1,a4,a7},{b2,b4,b6},{c3,c4,c5},{d1,d2,d3},{d5,d6,d7},{e3,e4,e5},{f2,f4,f6},{g1,g4,g7}}/.#/.{"w"->1,"b"->2},3|6]&

Пример ввода:

{a4 -> "w", b2 -> "b", b4 -> "b", c4 -> "b", d1 -> "w", d2 -> "w", e3 -> "w", e4 -> "w", e5 -> "w", f2 -> "b", f4 -> "b", f6 -> "b", g4 -> "w"}

Разрешение односимвольных имен координат тривиально удаляет 51 символ, делая это 166-байтовое решение. Называя игроков 1 и 2, а не «w» и «b», вычеркивает 17 других персонажей.

Итак, мы получаем

Count[Total/@{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,a,j,v,d,k,s,g,l,p,b,e,h,q,t,w,r,i,m,f,u,n,c,o,x}~Partition~3,3|6]/.#&
Симмонс
источник
Если я правильно понимаю правила форматирования ввода, вы сможете принять их как 1и 2. использовался пример wи b, но я вполне уверен, что мы не ограничены этим.
Mwr247 22.02.16
@ Mwr247 Вы правы. Вы можете использовать любой формат, который хотите, если он не добавляет дополнительную информацию. Я уточню это, когда я дома.
Денкер
1

APL (Dyalog Unicode) , 50 байтов

«Решение объектов»

Хотя он длиннее (29 символов), чем решение @ ngn , он использует совершенно другой подход: вход имеет ту же общую структуру, что и это решение, но все слоты представлены как объекты. Пустые слоты (включая несуществующий центральный столбец) должны быть пустыми объектами. в то время как все черные люди должны быть ссылками на объект «черный человек», а все белые люди должны быть ссылками на объект «белый человек». Все объекты могут необязательно иметь хороший D жаемого F ОРМ с для удобства чтения, и , следовательно, центральный столбец может быть необязательно сделан невидимым.

+/1=(≢¨(,∪/,∪⌿⍤2),(⊢/4 2⍴∪⌿))

Попробуйте онлайн!

+/ сумма

1=(... ) те, в

≢¨(... ) подсчет

  , сглаженный (сплющенный)

  ∪/ уникальные наборы по

  , соединенный с

  ∪⌿⍤2 уникальные сеты

,(... соединены ) с

  ⊢/ самый правый столбец

  4 2⍴ , преобразованный в четыре строки и два столбца,

  ∪⌿ уникальные столбчатые множества

На вершину оператора, прилагаемый с AGL ( ä), был бы довести длину до 27 символов .

Адам
источник