CODEWITHSUNDEEP
pythonstack
trainreq
trainreq

Reputation: 381

How do I find the shortest sequence of stack moves to get the goal stack?

My task is to write some code that finds the shortest sequence of moves that takes a given starting stack to a given goal stack. I am given an original list of books, portraying how the stack starts out, and a goal list of books, showing the goal order I need them in. The problem lies in that standard sorting algorithms won't work, as the ordering of the books is based off of a person's preference, not of any particular logic.

The system that the question wants you to use is as follows: pull a book out from anywhere in the stack, one at a time, and put it on top of the stack. So if you had books X, Y and Z, you could choose to pull out Y, making the order Y, X, Z.

Initial:

'1984 - George Orwell'
'Moby Dick - Herman Melville'
'To Kill A Mockingbird - Harper Lee'
'Atlas Shrugged - Ayn Rand'
'The Black Cat - Edgar Allen Poe'

Goal:

'Atlas Shrugged - Ayn Rand'
'To Kill A Mockingbird - Harper Lee'
'1984 - George Orwell'
'Moby Dick - Herman Melville'
'The Black Cat - Edgar Allen Poe'

This is homework. However, I am not looking for people to do it for me, as that would defeat the purpose of the assignment. I'm just looking for some ideas or tips to get started, as I don't know where to begin.

Note: I was going to tag this as homework however the tag explicitly says not to, so I haven't. If this is wrong, please correct me.

Upvotes: 4

Views: 172

Answers (2)

Tim
Tim

Reputation: 12174

A really simple algorithm is to just loop through the stack, each time finding and pulling out the next book that belongs on the bottom. A linear search would be sufficient for a small stack.

In your example, you would pull out 'The Black Cat - Edgar Allen Poe' on the first iteration, 'Moby Dick - Herman Melville' on the second, '1984 - George Orwell' on the third etc.

This is a O(n^2) algorithm.

Upvotes: 0

TheConstructor
TheConstructor

Reputation: 4465

Ok, the main problem is that you can only put onto the top, but you can choose any book. You wanted hints, not the method, so here are some:

  1. As you can only put on top always start looking at the bottom as its hardest do reach
  2. You obviously never need to pull any book already in the right place
  3. You need to pull all books which now are under a book that is above the book in the correct order
  4. If you stack books onto the top you should put them there in the correct order
  5. To transform A B G F C E D to alphabetical order you would optimally pull E, then F, then G if you always attach to the end.

I hope this got you started and I have not been to explicit.

Upvotes: 4

Related Questions