Untitled
unknown
plain_text
a year ago
4.2 kB
2
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 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))