stack_sort.py

import random

def mix_data(d):
    new_arr = list()
    for item in d:
        for item2 in item:
            new_arr.append(item2)
    random.shuffle(new_arr)

    unsorted_arr = []
    tmp_arr = []
    for i, item in enumerate(new_arr):
        if i % (len(d[0])) == 0:
            unsorted_arr.append(tmp_arr)
            tmp_arr = list()
            tmp_arr.append(item)
        else:
            if item == "-":
                tmp_arr.insert(0, item)
            else:
                tmp_arr.append(item)
    else:
        unsorted_arr.append(tmp_arr)
    unsorted_arr.pop(0)
    return unsorted_arr

def random_piece(stack_s):
    opts = list(set(item for sub_stack in stack_s for item in sub_stack))
    opts.remove("-")
    piece = random.choice(opts)
    ind_1 = -1
    ind_2 = -1
    flag = True
    while flag:
        ind_1 = random.randint(0, len(stack_s)-1)
        ind_2 = random.randint(0, len(stack_s[0])-1)
        if stack_s[ind_1][ind_2] not in ["-", piece]:
            flag = False
    return piece, ind_1,  ind_2


def calculate_min_moves(stacks, stack_ind, piece_ind, piece):
    """
    Calculate the minimum number of moves to put the specified piece into the correct location

    Rules:

    1.  "-" represents an empty piece. "-" doesn't need to be moved, but when a piece is moved to another stack
        that piece will replace a "-" in that stack, and it's former location will now contain a "-"

    2.  No pieces below the piece_ind should ever be moved from the stack that the piece is being replaced in.

        I.E. if ["-", "P", "O"] needs a "O" where the "P" is, the "O" at index 2 cannot be used, and should never
        be moved. 
        
    3. It can be assumed that the stack with the piece replaced will be empty above the piece because once the piece
       is in it's correct location adding more pieces on top will only increase moves 

    :param stacks: An array of all the stacks with each sub-array representing a stack in top-down order
    :type stacks: list ( list ( int ) )
    :param stack_ind: The index of the stack that needs the piece
    :type stack_ind: int
    :param piece_ind: The index the piece should be placed in the stack
    :type piece_ind: int
    :param piece: The piece that should be placed in the stack
    :return: An array of the minimum moves required
    """
    num_removals = 0
    for item in stacks[stack_ind][:piece_ind + 1]:
        if item != "-":
            num_removals += 1

    min_to_unlock = 1000
    unlock_from = -1
    for i, stack in enumerate(stacks):
        if i != stack_ind:
            for k, j in enumerate(stack):
                if j == piece:
                    if k < min_to_unlock:
                        min_to_unlock = k
                        unlock_from = i

    num_free_spaces = 0
    free_space_map = {}

    for i, stack in enumerate(stacks):
        if i != stack_ind and i != unlock_from:
            c = stack.count("-")
            num_free_spaces += c
            free_space_map[i] = c

    if num_removals + min_to_unlock <= num_free_spaces:
        print("CASE 1, no shuffling needed")
    else:
        print("Case 2, shuffling needed")



data = [["-", "-", "-", "-"],
        ["P", "P", "P", "P"],
        ["O", "O", "O", "O"],
        ["Y", "Y", "Y", "Y"]
        # ["R", "R", "R", "R"],
        # ["G", "G", "G", "G"],
        # ["N", "N", "N", "N"],
        # ["I", "I", "I", "I"]
        ]

random.seed(1)
data = mix_data(data)
p, s_ind, p_ind = random_piece(data)

print("All Stacks: {}".format(data))
should_be = list(map(lambda x: "-" if x < p_ind else p if x == p_ind else data[s_ind][x], range(len(data[s_ind]))))
print("Stack {} is currently {}".format(s_ind, data[s_ind]))
print("Stack {} should be {}".format(s_ind, should_be))
calculate_min_moves(data, s_ind, p_ind, p)