Solution

solution.py

import copy
import time


class Stack:
    __slots__ = ['size', 'values']

    def __init__(self, values, size=4):
        self.values = list(filter(lambda item: item != '-', values))
        self.size = size

    @property
    def is_full(self):
        return len(self.values) == self.size

    @property
    def is_empty(self):
        return len(self.values) == 0

    @property
    def top(self):
        return self.values[-1] if len(self.values) else None

    def pop(self):
        return self.values.pop()

    def push(self, value):
        self.values.append(value)

    def move_to_top_stack(self, stack):
        assert not self.is_empty
        assert not stack.is_full

        stack.push(self.pop())

    def __str__(self):
        parts = self.values + ['-'] * (self.size - len(self.values))
        return ", ".join(parts)

    def __repr__(self):
        return str(self)

    def __len__(self):
        return len(self.values)

    def __getitem__(self, key):
        return self.values[key]


class Stacks:
    __slots__ = ['stacks']

    def __init__(self, stacks):
        self.stacks = stacks

    def do_move(self, move):
        source, target = move
        self.stacks[source].move_to_top_stack(self.stacks[target])

    def __str__(self):
        parts = []
        for stack in self.stacks:
            parts.append(str(stack))
        parts.append('-' * 10)
        return "\n".join(parts)

    def __getitem__(self, key):
        return self.stacks[key]

    def __len__(self):
        return len(self.stacks)


class Solution:

    def __init__(self, stacks):
        self.stacks = stacks
        self.shortest_moves = []
        self.result = None

    def element_on_correct_place(self, stacks, stack_num, height, symbol):
        return self.stacks[stack_num][height] == symbol

    def can_do_last_move(self, stacks, stack_num, height, symbol):
        symbol_is_free = False
        move = None
        for i in range(len(stacks)):
            if stacks[i].top == symbol:
                move = (i, stack_num)
                symbol_is_free = True
                break

        place_is_free = len(stacks[stack_num]) == height
        return symbol_is_free and place_is_free, move

    def save_moves(self, moves, stacks):
        if not len(self.shortest_moves) or len(moves) < len(self.shortest_moves):
            self.shortest_moves = moves
            self.result = stacks

    def _find(self, stacks, stack_num, height, symbol, moves=None):
        if not moves:
            moves = []

        if len(moves) > 100:
            return

        if self.shortest_moves and len(self.shortest_moves) <= len(moves):
            return

        if self.element_on_correct_place(stacks, stack_num, height, symbol):
            self.save_moves(moves, stacks)
            return

        is_available, move = self.can_do_last_move(stacks, stack_num, height, symbol)
        if is_available:
            copy_stacks = copy.deepcopy(stacks)
            copy_stacks.do_move(move)

            copy_moves = copy.copy(moves)
            copy_moves.append(move)
            self.save_moves(copy_moves, copy_stacks)
            return

        for i, stack in enumerate(stacks):
            if i != stack_num and symbol not in stack:
                continue

            if stack.is_empty:
                continue

            for j, stack2 in enumerate(stacks):
                if i == j:
                    continue

                if stack2.is_full:
                    continue

                move = (i, j)
                reverse_move = (j, i)
                if reverse_move in moves:
                    continue

                copy_moves = copy.copy(moves)
                copy_moves.append(move)

                copy_stacks = copy.deepcopy(stacks)
                copy_stacks.do_move(move)

                self._find(copy_stacks, stack_num, height, symbol, copy_moves)

    def find(self, stack_num, height, symbol):
        now = time.time()

        self.shortest_moves = []
        self.result = None

        self._find(self.stacks, stack_num, height, symbol)

        print(self.shortest_moves)
        print(self.result)

        print(f'Took {time.time() - now}')


stacks = Stacks([
    Stack(['R', 'R', 'R', 'R']),
    Stack(['Y', 'Y', 'Y', 'Y']),
    Stack(['G', 'G', 'G', 'G']),
    Stack(['B', '-', '-', '-']),
    Stack(['B', 'B', 'B', '-']),
])
solution = Solution(stacks)
solution.find(4, 2, 'G')


solution.find(0, 0, 'B')