12

Stacks

Given a set of NXP stacks with N being the number of stacks, and P being the stacks capacity, how can I calculate the minimum number of swaps needed to move from some node in location A to some arbitrary location B? I'm designing a game, and the end goal is to sort all of the stacks so that they are all the same color.

# Let "-" represent blank spaces, and assume the stacks are
stacks = [
           ['R', 'R', 'R', 'R'], 
           ['Y', 'Y', 'Y', 'Y'], 
           ['G', 'G', 'G', 'G'], 
           ['-', '-', '-', 'B'], 
           ['-', 'B', 'B', 'B']
         ]

If I want to insert a "B" at stacks[1][1] such that stacks[1] = ["-", "B", "Y", "Y"]. How can I determine the minimum number of moves required to do so?

I've been looking at multiple approaches, I've tried genetic algorithms that generate all possible moves from a state, score them, and then continue down the best scoring paths, I've also attempted to run Djikstra's algorithm for pathfinding on the problem. It seems frustratingly simple, yet I can't figure out a way to get it to run in anything other than exponential time. Is there an algorithm I'm missing that is applicable here?

Edit

I've written this function to calculate the minimum number of moves required: stacks: List of List of Characters representing the pieces in the stack, stacks[0][0] is the top of stack[0] stack_ind: The index of the stack that the piece will be added to needs_piece: The piece that should be added to the stack needs_index: The index where the piece should be located

def calculate_min_moves(stacks, stack_ind, needs_piece, needs_index):
    # Minimum moves needed to empty the stack that will receive the piece so that it can hold the piece
    num_removals = 0
    for s in stacks[stack_ind][:needs_index+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, piece in enumerate(stack):
                if piece == needs_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("No shuffling needed, there's enough free space to move all the extra nodes out of the way")
    else:
        # HERE
        print("case 2, things need shuffled")

Edit: Test Cases on stacks:

stacks = [
           ['R', 'R', 'R', 'R'], 
           ['Y', 'Y', 'Y', 'Y'], 
           ['G', 'G', 'G', 'G'], 
           ['-', '-', '-', 'B'], 
           ['-', 'B', 'B', 'B']
         ]

Case 1: stacks[4][1] should be 'G'
Move 'B' from stacks[4][1] to stacks[3][2]
Move 'G' from stacks[2][0] to stacks[4][1]
num_removals = 0 # 'G' is directly accessible as the top of stack 2
min_to_unlock = 1 # stack 4 has 1 piece that needs removed
free_spaces = 3 # stack 3 has free spaces and no pieces need moved to or from it
moves = [[4, 3], [2, 4]]
min_moves = 2
# This is easy to calculate
Case 2: stacks[0][3] should be 'B'
Move 'B' from stacks[3][3] to stack[4][0]
Move 'R' from stacks[0][0] to stacks[3][3]
Move 'R' from stacks[0][1] to stacks[3][2]
Move 'R' from stacks[0][2] to stacks[3][1]
Move 'R' from stacks[0][3] to stacks[3][0]
Move 'B' from stacks[4][0] to stacks[0][3]
num_removals = 0 # 'B' is directly accessible 
min_to_unlock = 4 # stack 0 has 4 pieces that need removed
free_spaces = 3 # If stack 3 and 4 were switched this would be 1
moves = [[3, 4], [0, 3], [0, 3], [0, 3], [0, 3], [4, 0]]
min_moves = 6
#This is hard to calculate

The actual code implementation isn't the part that is difficult, it's determining an how to implement an algorithm that solves the problem that I'm struggling with.

As per @YonIif's request I've created a gist for the problem.

When it runs, it generates a random array of the stacks, and chooses a random piece that needs to be inserted into a random stack at a random location.

Running it prints something of this format to the console.

All Stacks: [['-', '-', 'O', 'Y'], ['-', 'P', 'P', 'O'], ['-', 'P', 'O', 'Y'], ['Y', 'Y', 'O', 'P']]
Stack 0 is currently ['-', '-', 'O', 'Y']
Stack 0 should be ['-', '-', '-', 'P']

Status update

I'm very determined to solve this problem somehow.

Keep in mind that there are way's to minimize the number of cases, such as the ones @Hans Olsson mentioned in the comments. My most recent approach to this problem, has been to develop a set of rules similar to those mentioned, and employ them in a generational algorithm.

Rules such as:

Don't ever reverse a move. Go from 1->0 then 0->1 (Makes no sense)

Don't ever move a piece twice in a row. Never Move from 0 -> 1 then 1 -> 3

Given some move from stacks[X] to stacks[Y], then some number of moves, then a move from stacks[Y] to stacks[Z], if stacks[Z] is in the same state as it was when the move from stacks[X] to stacks[Y] occurred, a move could've been eliminated by moving from stacks[X] directly to stacks[Z]

Currently, I am approaching this problem with an attempt to create enough rules, that it minimizes the number of "valid" moves, enough so that an answer can be calculated using a generational algorithm. If anyone can think of additional rules, I'd be interested in hearing them in the comments.

Update

Thanks to the answer by @RootTwo I've had a bit of a breakthrough, which I will outline here.

Onto the breakthrough

Define the goal height as the depth the goal piece must be placed in the destination stack.

Whenever some goal piece is placed at index <= stack_height - goal height, there will always be a shortest path to victory via the clear_path() method.

Let S represent some solid Piece.

I.E.

Stacks = [ [R, R, G], [G, G, R], [-, -, -] ]
Goal = Stacks[0][2] = R
Goal Height = 2.
Stack Height - Goal Height = 0

Given some stack such that stack[0] = R, the game is won.

                       GOAL
[ [ (S | -), (S | -), (S | -) ], [R, S, S], [(S | - ), (S | -), (S | -)] ]

Since it is known that their are always at least stack_height blank spaces available, the worst possible case would be:

 [ [ S, S, !Goal ], [R, S, S], [-, -, -]

Since we know the goal piece cannot be in the goal destination or the game is won. In which case the minimum number of moves required would be the moves:

(0, 2), (0, 2), (0, 2), (1, 0)

Stacks = [ [R, G, G], [-, R, R], [-, -, G] ]
Goal = Stack[0][1] = R
Stack Height - Goal Height = 1

Given some stack such that stack[1] = R, the game is won.

              GOAL
[ [ (S | -), (S | -), S], [ (S | -), R, S], [(S | -), (S | -), (S | -)]

We know there are at least 3 blank spaces available, so the worst possible case would be:

[ [ S, !Goal, S], [S, R, S], [ -, -, - ]

In this case the minimum number of moves would be the moves:

(1, 2), (0, 2), (0, 2), (1, 0)

This will hold for all cases.

Thus, the problem has been reduced to a problem of finding the minimum number of moves required to place the goal piece at or above at the goal height.

This splits the problem into a series of sub-problems:

  1. When the destination stack has its accessible piece != goal piece, determining if there is a valid location for that piece, or if the piece should stay there while another piece is swapped.

  2. When the destination stack has its accessible piece == goal piece, determining if it can be removed and placed at the required goal height, or if the piece should stay while another is swapped.

  3. When the above two cases require another piece to be swapped, determining which pieces to swap in order to increase to make it possible for the goal piece to reach the goal height.

The destination stack should always have its cases evaluated first.

I.E.

stacks = [ [-, R, G], [-, R, G], [-, R, G] ]

Goal = stacks[0][1] = G

Checking the Goal Stack first leads to:

(0, 1), (0, 2), (1, 0), (2, 0) = 4 Moves

Ignoring the Goal Stack:

(1, 0), (1, 2), (0, 1), (0, 1), (2, 0) = 5 Moves
18
  • 2
    Have you tried A*? It's fairly similar to Dijkstra's algorithm but sometimes it is considerably faster.
    – Yonlif
    Mar 24, 2020 at 11:49
  • 1
    Can you please share a github repo link? I would like to experiment myself if it is okay. @Tristen
    – Yonlif
    Mar 24, 2020 at 20:07
  • 1
    After a first look, this problem seems NP-hard. It is probably not within NP (not NP-complete), because even if I give you an optimal solution, you cannot even verify it easily. This is notorious for optimization problems on permutations. I'd suggest to cross-post the problem at CS. Look into approxmiation algorithms for this issue. This is a pretty hard problem but a decent approximation should exist. This is similar: Arbitrary Towers of Hanoi
    – DarioHett
    Mar 28, 2020 at 20:09
  • 1
    @DarioHett That was what I was worried about! I had my fingers crossed that it wouldn't end up being an NP-Hard problem, but I also had a gut feeling it might be one. I have been having better luck with a genetic algorithm, and also some specialized scoring functions that score the moves. I'll take a look at the Arbitrary Towers of Hanoi! Thanks for the suggestion.
    – Tristen
    Mar 30, 2020 at 13:58
  • 1
    If you try to generate the puzzle randomly - remember to remove obviously redundant moves (moving something back after a forward move or doing a move in two steps when one would suffice; and also in combination with possibly unrelated moves mixed in). Apr 2, 2020 at 12:11

3 Answers 3

1

I came up with two options, but none of them are able to solve case 2 in a timely manner. The first option is using A* with a string distance measure as your h(n), second option is IDA*. I tested many string similarity measures, i used smith-waterman on my approach. I have changed your notation to treat the problem faster. I have added numbers to the end of each digit to check if a piece was moved twice.

Here are the cases I have tested on:

start = [
 ['R1', 'R2', 'R3', 'R4'], 
 ['Y1', 'Y2', 'Y3', 'Y4'], 
 ['G1', 'G2', 'G3', 'G4'], 
 ['B1'], 
 ['B2', 'B3', 'B4']
]

case_easy = [
 ['R', 'R', 'R', 'R'], 
 ['Y', 'Y', 'Y', 'Y'], 
 ['G', 'G', 'G'], 
 ['B', 'B'], 
 ['B', 'B', 'G']
]


case_medium = [
 ['R', 'R', 'R', 'R'], 
 ['Y', 'Y', 'Y', 'B'], 
 ['G', 'G', 'G'], 
 ['B'],
 ['B', 'B', 'G', 'Y']
]

case_medium2 = [
 ['R', 'R', 'R' ], 
 ['Y', 'Y', 'Y', 'B'], 
 ['G', 'G' ], 
 ['B', 'R', 'G'],
 ['B', 'B', 'G', 'Y']
]

case_hard = [
 ['B'], 
 ['Y', 'Y', 'Y', 'Y'], 
 ['G', 'G', 'G', 'G'], 
 ['R','R','R', 'R'], 
 ['B','B', 'B']
]

Here's the A* code:

from copy import deepcopy
from heapq import *
import time, sys
import textdistance
import os

def a_star(b, goal, h):
    print("A*")
    start_time = time.time()
    heap = [(-1, b)]
    bib = {}
    bib[b.stringify()] = b

    while len(heap) > 0:
        node = heappop(heap)[1]
        if node == goal:
            print("Number of explored states: {}".format(len(bib)))
            elapsed_time = time.time() - start_time
            print("Execution time {}".format(elapsed_time))
            return rebuild_path(node)

        valid_moves = node.get_valid_moves()
        children = node.get_children(valid_moves)
        for m in children:
          key = m.stringify()
          if key not in bib.keys():
            h_n = h(key, goal.stringify())
            heappush(heap, (m.g + h_n, m)) 
            bib[key] = m

    elapsed_time = time.time() - start_time
    print("Execution time {}".format(elapsed_time))
    print('No Solution')

Here's the IDA* Code:

#shows the moves done to solve the puzzle
def rebuild_path(state):
    path = []
    while state.parent != None:
        path.insert(0, state)
        state = state.parent
    path.insert(0, state)
    print("Number of steps to solve: {}".format(len(path) - 1))
    print('Solution')

def ida_star(root, goal, h):
    print("IDA*")
    start_time = time.time()
    bound = h(root.stringify(), goal.stringify())
    path = [root]
    solved = False
    while not solved:
        t = search(path, 0, bound, goal, h)
        if type(t) == Board:
            solved = True
            elapsed_time = time.time() - start_time
            print("Execution time {}".format(elapsed_time))
            rebuild_path(t)
            return t
        bound = t

def search(path, g, bound, goal, h):

    node = path[-1]
    time.sleep(0.005)
    f = g + h(node.stringify(), goal.stringify())

    if f > bound: return f
    if node == goal:
        return node

    min_cost = float('inf')
    heap = []
    valid_moves = node.get_valid_moves()
    children = node.get_children(valid_moves)
    for m in children:
      if m not in path:
        heappush(heap, (m.g + h(m.stringify(), goal.stringify()), m)) 

    while len(heap) > 0:
        path.append(heappop(heap)[1])
        t = search(path, g + 1, bound, goal, h)
        if type(t) == Board: return t
        elif t < min_cost: min_cost = t
        path.pop()
    return min_cost

class Board:
  def __init__(self, board, parent=None, g=0, last_moved_piece=''):
    self.board = board
    self.capacity = len(board[0])
    self.g = g
    self.parent = parent
    self.piece = last_moved_piece

  def __lt__(self, b):
    return self.g < b.g

  def __call__(self):
    return self.stringify()

  def __eq__(self, b):
    if self is None or b is None: return False
    return self.stringify() == b.stringify()

  def __repr__(self):
    return '\n'.join([' '.join([j[0] for j in i]) for i in self.board])+'\n\n'

  def stringify(self):
    b=''
    for i in self.board:
      a = ''.join([j[0] for j in i])
      b += a + '-' * (self.capacity-len(a))

    return b

  def get_valid_moves(self):
    pos = []
    for i in range(len(self.board)):
      if len(self.board[i]) < self.capacity:
        pos.append(i)
    return pos

  def get_children(self, moves):
    children = []
    for i in range(len(self.board)):
      for j in moves:
        if i != j and self.board[i][-1] != self.piece:
          a = deepcopy(self.board)
          piece = a[i].pop()
          a[j].append(piece)
          children.append(Board(a, self, self.g+1, piece))
    return children

Usage:

initial = Board(start)
final1 = Board(case_easy)
final2 = Board(case_medium)
final2a = Board(case_medium2)
final3 = Board(case_hard)

x = textdistance.gotoh.distance

a_star(initial, final1, x)
a_star(initial, final2, x)
a_star(initial, final2a, x)

ida_star(initial, final1, x)
ida_star(initial, final2, x)
ida_star(initial, final2a, x)
0
+50

In the comments you said there are N stacks with capacity P, and there are always P empty spaces. If that is the case, it seems this algorithm will work in the else clause in your code (i.e. when num_removals + min_to_unlock > num_free_spaces):

  1. Find the desired piece that is closest to the top of a stack.
  2. Move all the pieces from above the desired piece in such a way that there is one stack (not the destination stack) that has an empty space on top. If needed, move pieces from the destination stack or another stack. If the only open space is the top of the destination stack, move a piece there to open the top of another stack. This is always possible, because there are P open spaces and at most P-1 pieces to move from above the desired piece.
  3. Move the desired piece to the empty spot on top of a stack.
  4. Move pieces from the destination stack until the destination is open.
  5. Move the desired piece to the destination.
1
  • I've spent the past couple hours digging into this answer, and I think there might be something there. If possible, could you provide a bit more information as to how you'd go about moving the pieces that are above the desired piece? How do you determine which stacks to move them to? Perhaps a bit of psuedocode/code. This is definitely the closest I've felt to the solving this so far.
    – Tristen
    Apr 3, 2020 at 4:51
0

Although I haven’t found the time to prove this mathematically, I decided to post this anyway; hope it helps. The approach is to define a parameter p that decreases with good moves and reaches zero exactly when the game has finished. In the program only considers good moves or neutral moves (that leave p unchanged) and forget about bad moves (that increase p).

So what is p? For every column define p as the number of blocks that still have to be removed before all colors in that column are the desired color. So suppose we want the red blocks to end up in the leftmost column (I’ll come back to that later), and suppose there is one red block at the bottom, then a yellow on top of that, one more block on top of that, and then an empty space. Then p=2 for this column (two blocks to remove before all are red). Calculate p for all columns. For the column that should end up empty, p is equal to the number of blocks that is in it (all of them should go). P for the current state is the sum of all p’s for all columns.

When p=0, all columns have the same color and one column is empty, so the game has finished.

By choosing moves that decrease p (or at least not increase p) we’re moving in the right direction, this is in my opinion the crucial difference with shortest path algorithms: Dijkstra had no idea whether he was moving in the right direction with every vertex he was investigating.

So how do we determine where each color should end up? Basically by determining p for every possibility. So e.g. start with red / yellow / green / empty, calculate p, then go to red / yellow / empty / green, calculate p, etc. Take the starting position with the lowest p. This takes n! calculations. For n=8 this is 40320, which is doable. The bad news is that you’ll have to examine all starting positions with equal lowest p. The good news is that you can forget the rest.

There are two mathematical uncertainties here. One: is it possible that there is a shorter path that uses a bad move? Seems unlikely, I haven’t found a counterexample , but I haven’t found a proof either. Two: is it possible that when starting with a non-optimal starting position (I.e. not the lowest p) there would be a shorter path than with all optimal starting positions. Again: no counterexample but no proof either.

Some implementation suggestions. Keeping track of p during execution for each column is not difficult but should of course be done. Another parameter that should be kept for each column is the number of open spots. If 0, then this columns can momentarily not accept any blocks, so can be left out of the loop. When p=0 for a column, it is not eligible for a pop. For every possible pop, examine if there is a good move, I.e. one which decreases the overall p. If there are multiple, examine all. If there is none, consider all neutral moves.

All of this should greatly reduce your computation time.

2
  • 1
    I think you misunderstood the question! Although this is the motivation behind the question. The question is to find the minimum number of moves to move a single piece, to a single location. The question was not to find the minimum number of moves to sort the stacks, although that is the motivation behind the question. However, with that scoring of P, you would be incorrect. There are many instances where there are "bad moves" that end up increasing P at first, and then later decrease it at a faster rate. With that said, perhaps re-read the question as your answer has no relevance.
    – Tristen
    Apr 3, 2020 at 4:44
  • 1
    My apologies Tristen, I did indeed not read the question carefully. I was fascinated by the mathematical aspect of it and, being late to the party, too quick to answer. I'll be more careful next time. Hopefully you do find an answer.
    – Paul Rene
    Apr 3, 2020 at 22:54

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.