[PS] Crane doll picker game

Programmers: Crane doll picker game

Conditions

• 'board' is given in an NxN matrix larger than 5x5 and smaller than 30x30.
• Zero means a blank space, each number from 1 to 100 means a different doll's shape. The same number means the same doll.
• The size of the 'moves' array is from 1 to 1000.
• The values of each element of 'moves' are from 1 to less than N.
• Assume the basket is big enough for all the dolls to fit in.
• When two dolls of the same shape pile up in a row in the basket, the two dolls burst and disappear from the basket.
• Nothing will happen if the crane is operated in the absence of a doll.

Strategy

• Use 'board' array to create 'top' array -> No need to check bins every time.
• Since the 'moves' array is given from 1, use bin_num-1 for access to the array.
• If top[bin_num] equals N, then there is no more doll in that bin. So nothing happens.
• If the basket is empty or if current doll and the last doll in the basket are in different shapes, put the current doll in the basket.
• If the basket's last doll is the same as the current doll, the two dolls are removed and add 2 to answer.

def solution(board, moves):
    answer = 0

    top = []
    for i in range(len(board)):
        for j in range(len(board)):
            if board[j][i] != 0:
                top.append(j)
                break

    basket = []
    for i in moves:
        bin_num = i-1

        if top[bin_num] == len(board):
            # if no dolls in the bin, do nothing
            continue

        doll = board[top[bin_num]][bin_num]

        # put the doll if the basket is empty
        if basket != [] and basket[-1] == doll:
            basket.pop() # remove
            board[top[bin_num]][bin_num] = 0
            top[bin_num] += 1
            answer += 2
        else:
            basket.append(doll)
            board[top[bin_num]][bin_num] = 0
            top[bin_num] += 1

    return answer

Remember

• This is a simple problem using stack.
• If you made 'top' array once, no need to find the top doll of the bin every timme.
• Be careful of the index since the 'moves' start at 1.