'''
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
advanced(hand_1) => True
advanced(hand_2) => True
advanced(hand_3) => True
advanced(hand_4) => True
advanced(hand_5) => False
advanced(hand_6) => True
advanced(hand_7) => True
advanced(hand_8) => True
advanced(hand_9) => False
advanced(hand_10) => False
advanced(hand_11) => False
advanced(hand_12) => False
advanced(hand_13) => True
advanced(hand_14) => False
advanced(hand_15) => True
advanced(hand_16) => True
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][0] + dp[i][1] + dp[i][2] >= 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, 0]
dp[1] = [is_pair(hand, 1), 0, 0]
dp[2] = [0, is_run(hand, 2), is_triple(hand, 2)]
print(0, dp[0])
print(1, dp[1])
print(2, dp[2])
# 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][0], dp[i-3][1]+1, dp[i-3][2]]
elif is_triple(hand, i):
if check(dp, i-3):
dp[i] = [dp[i-3][0], dp[i-3][1], dp[i-3][2]+1]
# i-2
elif is_pair(hand, i):
if check(dp, i-2):
dp[i] = [dp[i-2][0]+1, dp[i-2][1], dp[i-2][2]]
print(i, dp[i])
return check(dp, len(hand)-1)
if __name__ == "__main__":
print(main(hand_16))