CODEWITHSUNDEEP
algorithmsortingstack
Alan Forsyth
Alan Forsyth

Reputation: 2517

Algorithm for multiple stack sorting according to pattern

In my (little) spare time, I've come up with a small personal project as motivation to practice using new technologies (for me!), such as Python 3 & Node JS.

I want to try to create a solution routine for a puzzle, similar to Towers of Hanoi in construction, as shown in the following image:

Stack Puzzle - sample start and finish

Puzzle Rules

  1. 8 coloured blocks are randomly positioned on 3 stacks (S1-S3), which have capacity 5, 3, 3 respectively.
  2. A fourth stack (S4) of size 3 is empty, but is used as transient storage for movements between the other stacks; e.g. to move blue next to purple in S2: Move red [S2 -> S4], move green [S2 -> S4], move blue [S3 -> S4], move blue [S4 -> S2], etc.
  3. A target pattern of 5 blocks is randomly generated, and the blocks must be moved between stacks one by one (via S4) until the correct ordered blocks are present in S1, at which point S4 must again be empty (the final state of S2, S3 is not important).
  4. Note that my illustration is not perfect, and that random scenario is actually more challenging! However, imagine that all stacks are accessed at their base, so first accessible block on S1 (left) is the black one, etc.
  5. There are some tips for solutions that could eventually be coded into the algorithm, e.g. focus on last block first, in this case purple.

Algorithms:

I've been searching for a while for a best-fit multi-stack 'sorting' algorithm based on a pattern, to avoid re-inventing the wheel, but can't find anything that seems relevant, although I may be looking in the wrong place. Towers of Hanoi classic recursion appears too basic, while algorithms like Shunting Yard and Travelling Salesman (and standard Bubblesort, Quicksort, etc.) don't seem a good fit (please correct me if I'm wrong!).

My question:

Can anyone suggest or recommend a suitable base algorithm that I could build on or adapt for solving this puzzle? It will probably need to be recursive, to find the correct paths, but I'm sure this type of multi-stack or pattern-based sorting has been done before somewhere? I eventually want to attain the best efficiency thru minimum number of steps required, but that comes later.

As I mentioned, it's most likely that I'll use Python or JS to implement this in the end, but any ideas or snippets are appreciated at this stage - I expect to do the dev work myself later on.

Thanks in advance!

Alan

Upvotes: 0

Views: 546

Answers (1)

rcgldr
rcgldr

Reputation: 28921

One method would be to first move the 3 unused blocks to S4. Setup the distribution so it's S1 = 3 blocks, S2 = 3 blocks, S3 = 2 blocks. If S3 has 1 or 2 unused blocks, it takes 1 or 2 moves to move the unused block(s) to S4. Repeat for S2, taking 1 to 3 moves to move 1 to 3 unused blocks. Unused blocks are removed from S1 last.

Now you have 5 blocks and 3 stacks. Say S1 has 3 blocks and S2 has 2 blocks. The block that belongs at the top of S1 could take the most number of moves to end up where that is the only block S1 has. For example, the block that belongs at the top of S1 is at the top of S2. So move 2 blocks from S2 to (now empty) S3, so the key block is at the bottom of S3. Then move all 3 blocks from S1 to S2, then the key block to S1. After that, the problem becomes 4 blocks and 3 stacks of size 4, 3, 3, which shouldn't be too difficult. Once this is done, then the 3 blocks in S4 can be moved to S2 or S3.

As for a 3 stack sort, a polyphase merge sort is fastest, but all 3 stacks need to be the same size, so that doesn't apply here.

Upvotes: 1

Related Questions