Алгоритм, чтобы найти улицы и такого же рода в руке

Question

Это на самом деле вопрос, основанный на основе Маджонга, но ромма на основе Romme или даже покера также может быть достаточна, чтобы понять.

В Mahjong 14 плиток (плитка похожи на карты в покере), расположены до 4 наборов и пары. Улица («123») всегда использует ровно 3 плитки, не более и не менее. Набор того же рода («111») состоит из ровно 3 плиток тоже. Это приводит к сумме 3 * 4 + 2 = 14 плиток.

Существуют различные исключения, такие как KAN или тринадцать детей, которые не актуальны здесь. Цвета и ценные диапазоны (1-9) также не важны для алгоритма.

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

Примеры:

11122233344455 - достаточно легко, 4 комплекта и пара.
12345555678999 - 123, 456, 789, 555, 99
11223378888999 - 123, 123, 789, 888, 99
11223344556789 - не действительная рука

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

Я считаю, что этот подход работает и будет также достаточно быстрым (производительность - «хороший бонус»), но я заинтересован в вашем мжении по этому поводу. Можете ли вы подумать об альтернативных решениях? Это или что-то подобное уже существует?

(Не домашнее задание, Я учусь играть в Маджонг.)

Answer 1

Сумма ценностей на улице и в наборе можно разделить на 3:

• n + n + n = 3n
• (N-1) + N + (N + 1) = 3n

Итак, если вы добавите все номера в решенной руке, вы получите ряд формы 3n + 2m, где M - значение плитки в паре. Остаток отдела тремя (total % 3) есть для каждого значения M:

total % 3 = 0  -> M = {3,6,9}
total % 3 = 1  -> M = {2,5,8}
total % 3 = 2  -> M = {1,4,7}

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

Как только у вас есть, начните с самого низкого значения. Если с этим значением меньше трех плиток, это означает, что они обязательно являются первым элементом улицы, поэтому удалите эту улицу (если вы не можете, потому что плитки N + 1 или N + 2 отсутствуют, это означает, что рука недействителен) и перейти к следующему наименьшее значение.

Если есть как минимум три плитки с самым низким значением, удалите их как набор (если вы спросите «Что, если они были частью улицы?» Считайте, что если бы они были, то есть три из плитки N + 1 и три плитки n + 2, которые также могут быть превращены в наборы) и продолжать.

Если вы достигнете пустой руки, рука действительна.

Например, для вашей неверной руки общее количество составляет 60, что означает M = {3,6,9}:

Remove the 3: 112244556789
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there is only one

Remove the 9: impossible, there is only one

С вашим вторым примером 12345555678999, Всего составляет 78, что означает M = {3,6,9}:

Remove the 3: impossible, there is only one

Remove the 6: impossible, there is only one

Remove the 9: 123455556789
 - Start with 1: there is only one, so remove a street
   -> 455556789
 - Start with 4: there is only one, so remove a street
   -> 555789
 - Start with 5: there are three, so remove a set
   -> 789
 - Start with 7: there is only one, so remove a street
   -> empty : hand is valid, removals were [99] [123] [456] [555] [789]

Ваш третий пример 11223378888999 также имеет в общей сложности 78, что вызывает возврат:

Remove the 3: 11227888899
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there are none

Remove the 9: 112233788889
 - Start with 1: there are less than three, so remove streets
   -> 788889
 - Start with 7: there is only one, so remove a street
   -> 888
 - Start with 8: there are three, so remove a set
   -> empty, hand is valid, removals were : [99] [123] [123] [789] [888]

Answer 2

Существует особый случай, который вам нужно сделать повторную работу, чтобы получить его правильно. Это происходит, когда есть три-три и пара с одинаковым значением (но в другом костюме).

Пусть B отказывает бамбук, C пожертвовать персонажа, а D пожертвовать точку, попробуйте эту руку:

b2,b3,b4,b5,b6,b7,c4,c4,c4,d4,d4,d6,d7,d8

d4,d4 should serve as the pair, and c4,c4,c4 should serve as the run-of-3 set.

Но из-за того, что плитки 3 «C4» появляются перед TiLess 2 D4, первые 2 C4 плитки будут подняты в качестве пары, оставляя сирорт C4 и 2 D4S, и эти 3 плитки не сформируют действительный набор.

В этом случае вам необходимо «вернуть» 2 C4 плитки обратно в руку (и держать руку отсортированную) и найдите следующую плитку, которая соответствует критериям (значение == 4). Для этого вам нужно будет сделать код «запомнить», что он пробовал C4, так что в следующем итерации он должен пропустить C4 и ищет другие плитки со значением == 4. Код будет немного грязным, но выполнимым.

Answer 3

Я сломал это на 2 шага.

1. Выяснить возможные комбинации. Я думаю, что исчерпывающая проверка возможна с этими числами. Результатом этого шага представляет собой список комбинаций, где каждая комбинация имеет тип (набор, улица или пару) и шаблон с использованием карточек (может быть растровым изображением).
2. С предыдущей информацией определяют возможные коллекции комбинаций. Это где растровое изображение пригодится. Используя битовые операторы, вы можете увидеть перекрытие в использовании одной и той же плитки для разных комбинаторов.

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