Untitled

mail@pastecode.io avatar
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))