# Untitled unknown
plain_text
16 days ago
4.2 kB
1
Indexable
Never
```'''
You've decided to make an advanced version of a variant of the game Mahjong, incorporating runs.

Players have a number of tiles, each marked 0-9. The tiles can be grouped into pairs or triples of the same tile or runs.

A run is a series of three consecutive tiles, like 123, 678, or 456. 0 counts as the lowest tile, so 012 is a valid run, but 890 is not.

A complete hand consists of exactly one pair, and any number (including zero) of triples and/or three-tile runs. Each tile is used in exactly one triple, pair, or run.

Write a function that returns true or false depending on whether or not the collection represents a complete hand under these rules.

hand_1 = "12131"           # True. 11 123. Tiles are not necessarily sorted.
hand_2 = "11123455"        # True. 111 234 55 (triple, run, pair)
hand_3 = "11122334"        # True. 11 123 234 (pair, run, run)
hand_4 = "11234"           # True. 11 234
hand_5 = "123456"          # False. Needs a pair
hand_6 = "11133355577"     # True. 111 333 555 77
hand_7 = "11223344556677"  # True. 11 234 234 567 567 among others
hand_8 = "12233444556677"  # True. 123 234 44 567 567
hand_9 = "11234567899"     # False.
hand_10 = "00123457"       # False.
hand_11 = "0012345"        # False. A run is only three tiles
hand_12 = "11890"          # False. 890 is not a valid run
hand_13 = "99"             # True.
hand_14 = "111223344"      # False.
hand_15 = "00000099"       # True. 000 000 99
hand_16 = "12233344566"    # True. 123 234 345 66

All Test Cases

Complexity Variable
N - Number of tiles in the input string
'''

from copy import deepcopy
from collections import Counter

hand_1 = "12131"
hand_2 = "11123455"
hand_3 = "11122334"
hand_4 = "11234"
hand_5 = "123456"
hand_6 = "11133355577"
hand_7 = "11223344556677"
hand_8 = "12233444556677"
hand_9 = "11234567899"
hand_10 = "00123457"
hand_11 = "0012345"
hand_12 = "11890"
hand_13 = "99"
hand_14 = "111223344"
hand_15 = "00000099"
hand_16 = "12233344566"

def is_pair(hand: str, i: int):
return 1 if int(hand[i]) == int(hand[i-1]) else 0

def is_run(hand: str, i: int):
return 1 if int(hand[i]) == int(hand[i-1]) + 1 == int(hand[i-2]) + 2 else 0

def is_triple(hand: str, i: int):
return 1 if int(hand[i]) == int(hand[i-1]) == int(hand[i-2]) else 0

def check(dp, i):
# check any number of triples / runs / pairs (including 0 but not all 0)
# dp = [[x, y, z], ... , ]
return dp[i] + dp[i] + dp[i] >= 1

# TODO: this only accounts for 不跳著找 的hand, 不會像hand16那麼雞掰 :)
# TODO: if hand16, we need a list in dp[i] to account for every scenario

def main(hand: str):

#
hand = sorted(hand)
hand = ''.join(hand)
print(hand)

# pair, run, triple
dp = [[0, 0, 0] for _ in range(len(hand))]

# base case 最多會往前看 i-3 個 -> 所以basecase 至少要include 0->2 所以 index 不會爆掉
dp = [0, 0, 0]
dp = [is_pair(hand, 1), 0, 0]
dp = [0, is_run(hand, 2), is_triple(hand, 2)]

print(0, dp)
print(1, dp)
print(2, dp)

# loop til n-1
for i in range(3, len(hand)):
# i-3 離我最近的三個是不是triple/run
if is_run(hand, i):
if check(dp, i-3):
dp[i] = [dp[i-3], dp[i-3]+1, dp[i-3]]

elif is_triple(hand, i):
if check(dp, i-3):
dp[i] = [dp[i-3], dp[i-3], dp[i-3]+1]
# i-2
elif is_pair(hand, i):
if check(dp, i-2):
dp[i] = [dp[i-2]+1, dp[i-2], dp[i-2]]

print(i, dp[i])

return check(dp, len(hand)-1)

if __name__ == "__main__":

print(main(hand_16))
```