Алгоритм поиска улиц и того же вида в руке

Ответ 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]

Ответ 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" появляются перед 2 безжалостностью d4, первые две c4-плитки будут подбираться как пара, оставив сироту c4 и 2 d4s, и эти 3 плитки не будут формировать действительный набор.

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

Ответ 3

Я разбил бы его на 2 шага.

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

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