Objects-classes kind of question

[Leela]

I have started studying classes and objects in Python, and here where things got extremely confusing. If anyone knows a way to explain those things to a newbie, please help me! I have read so much about it, and it still like a sea of mysteries!
A more particular question:
I am doing this assignment where I'm supposed to reconstruct a stack of items after it has been broken into pieces. Here is the exact quote:

''Your rich and eccentric uncle has left you alone in his mansion for the evening. He has told you that you have free-reign of the house, with the exception of the library. As your uncle explains, the library is unlike other libraries in that books are not kept on shelves. Instead, they are kept in stacks on the floor. The books have been stacked in a very particular order, and your uncle will easily be able to tell whether or not any books are out of place.

Since you love books and you've never been one to follow rules, you head to the library as soon as your uncle leaves. Despite the fact that you aren't following the rules, you want to be safe and make sure that in case you have an accident that you can put the books into their original order. So before perusing through the books in any of the stacks, you take note of the exact order that the books are in and record this information using a portable computer that you've brought. Unfortunately, after recording the order of the books in one of the stacks, you have an accident, causing the books to become strewn over the floor. Luckily some of the books have stayed "piled together". This means that recreating the original stack of books will be somewhat easier than having to go through each book one at a time. For the books that have stayed piled together, you can pick up the whole "mini-pile" and place it back on the original stack in the appropriate place.

For example, if the stack of books was originally <a,b,c,d,e,f>, where the right end represents the top of the stack, then the mini-piles after knocking the stack over may be <a,b,c>, <d>, <e,f>. To reconstruct the original stack, you start by pushing the mini-pile <a,b,c>, followed by <d>, followed by the mini-pile <e,f>.
Your goal is to write a computer program to help you recreate the original stack of books.

Details
Implement a function reconstruct_stack that takes two arguments: original and minipiles. The original argument represents the original stack of books before you knocked them over and is an instance of class Stack, and minipiles is a list of the mini-piles that exist after the original stack is knocked over. Each element of the list minipiles is a Stack instance representing a fragment of the original stack. The return value is a list representing the order in which the minipiles need to be pushed onto an empty stack in order to recreate the original stack. Each element of the returned list should simply be the top element of the corresponding minipile.

For example, suppose the original stack and the minipiles are constructed as follows:


# the original stack

original = Stack()
original.push('a')
original.push('b')
original.push('c')
original.push('d')
original.push('e')
original.push('f')

# the mini-piles after the stack is toppled

m1 = Stack()
m1.push('a')
m1.push('b')
m1.push('c')

m2 = Stack()
m2.push('d')

m3 = Stack()
m3.push('e')
m3.push('f')

A call to reconstruct_stack(original,[m1,m2,m3]) should return ['c','d','f']. The returned list indicates that the mini-pile with c at the top should be pushed first, followed by d, followed by the mini-pile with f at the top. Note that in this example the order of mini-piles in the second argument matches the order in which they should be pushed onto the stack. Your function should behave correctly even if this isn't the case. For example, reconstruct_stack(original,[m2,m1,m3]) and reconstruct_stack(original,[m3,m2,m1]) should also return ['c','d','f']. ''

Here below is the definitions of the class Stack:

class Stack:

def __init__(self):
'''A new empty stack'''
self.items = []

def push(self, o):
'''Make o the new top item in this Stack.'''
self.items.append(o)

def pop(self):
'''Remove and return the top item.'''
return self.items.pop()

def peek(self):
'''Return the top item.'''
return self.items[-1]

def isEmpty(self):
'''Return whether this stack is empty.'''
return self.items == []

def size(self):
'''Return the number of items in this stack.'''
return len(self)

I have created an algorithm which assumes that the original pile is a list (because this is what it supposed to be according to the __init__ method). But apparently, it is not (the IDE raises an exception that class object is not iterable, as it is not a sequence). Also, when I try to print the return of the push('whatever') methods - it comes out 0.
My question (apart from my begging to explain to me the relationship between classes and objects like you would to a three year old) is: If the after the last book is pushed into the pile, there is a list of books in the order they were pushed, how do I access it? And if there isn't - do you guys think it's ok for this assignment to just crudely turn the method objects into a list like this:

t = []
while not original.isEmpty():
t.append(original.pop())
print t

Huge thanks to everyone!
P.S. I can't find the syntax tags for python code again. Is it on this website?[/code]

[Zeroth]

Two ways you can do this:
-override the builtin methods for list-like objects
-change your algorithm

Override Builtin Methods for List-Like Objects:
Probably a bit beyond your current skill level, no offense.

Implement those methods, and it will be treated as a sequence.

Basic explanation of OOP:
Classes are the blueprints for building an object. They describe the methods the object must have, what those methods do, its relationship to other objects, and what kind of data the object has. Objects are a bundle of data, and code, all in one package, accessed in memory. If it is code, then the function is executed with the object itself passed as the first argument(hence self). In python code can be treated as data, and data treated as code, so it gets a bit amorphous in Python. As well, one can implement specific methods which when an object has those methods, it can act as a list, or a dict, or a tuple, and can be treated identically to them.

Does that help?

Now as to turning the stack into a list... why not just go:

code:

t=original.items

[Leela]

Thank you!

Zeroth @ Sun May 17, 2009 10:52 am wrote:

Implement those methods, and it will be treated as a sequence.

What do you mean? Aren't they being implemented as they appear?

[quote ]Basic explanation of OOP:
Classes are the blueprints for building an object. They describe the methods the object must have, what those methods do, its relationship to other objects, and what kind of data the object has. Objects are a bundle of data, and code, all in one package, accessed in memory. If it is code, then the function is executed with the object itself passed as the first argument(hence self). In python code can be treated as data, and data treated as code, so it gets a bit amorphous in Python. As well, one can implement specific methods which when an object has those methods, it can act as a list, or a dict, or a tuple, and can be treated identically to them.

Does that help?
[/quote]
Yes, it does, thanky you again!

Quote:

Now as to turning the stack into a list... why not just go:

code:

t=original.items

So, you think, generally the idea of turning the results of this bunch of methods into a list is ok? Isn't it awkward or something?

[Zeroth]

Oops, that was for when I was considering you could implement a bunch of methods that would make stack act exactly like a list.

Now, well, if you want a working algorithm, you can use all the pop, push methods, it can just get tedious.

Or you could build an iterator to surround the stack.

Extracting the internal list is a lot simpler than using your loop from before.

All sorts of ways. Just determine which way is the best for you, and your skills, and use it.

[Leela]

How does my function look?

Python:

def reconstruct_stack(original, minipiles):     s = []     t = original.items     d = dict()     for each in minipiles:         s.append(each.items[-1])     for each in s:         index = t.index(each)         d[index] = each     f = d.items()     f.sort()     res = []     for index, item in f:         res.append(item)     return res

[Zeroth]

Looks good. Needs some commenting Does it work? It appears to work, to me, in some fairly clever ways. Are you aware of list comprehensions? Used properly, they can be easier to read than some for loops, and they perform the loop at C speed, rather than Python speed.

[Leela]

Zeroth @ Sun May 17, 2009 3:16 pm wrote:

Looks good. Needs some commenting Does it work? It appears to work, to me, in some fairly clever ways. Are you aware of list comprehensions? Used properly, they can be easier to read than some for loops, and they perform the loop at C speed, rather than Python speed.

Thank you! Yeah, I am aware it needs commenting - I just didn't get to it yet. The function works like a charm. And no, I don't know about list comprehension.
I have a different question - if I wanted this function to depend more on the class methods, what do you think should I change? I am concerned that my implementation is too far away from the original class, and it might be frowned upon. I mean, I'm supposed to work around user defined methods pop, peek, and stuff, not around some well-known list and dictionary methods.

[Zeroth]

What do you think you should do? [/list]

[Leela]

Zeroth @ Sun May 17, 2009 4:45 pm wrote:

What do you think you should do? [/list]

I should leave the class objects as they are (without turning them into new objects) and work with them through functions pop, peek and the rest?

[Leela]

Does this look more assignment oriented?

# the original stack

code:

original = Stack() original.push('a') original.push('b') original.push('c') original.push('d') original.push('e') original.push('f')

# the mini-piles after the stack is toppled

code:

m1 = Stack() m1.push('a') m1.push('b') m1.push('c') m2 = Stack() m2.push('d') m3 = Stack() m3.push('e') m3.push('f')

code:

def reconstruct_stack(original, minipiles):     new = Stack()     t = original.items     for each in minipiles:         if each.peek() in t:             new.push(each.peek())     return new.items

Implementation:

code:

reconstruct_stack (original, [m2,m1,m3])

[Zeroth]

Well, its up to you how you complete the assignment, lol.

[Leela]

Zeroth @ Sun May 17, 2009 7:05 pm wrote:

Well, its up to you how you complete the assignment, lol.

It's just that I don't know how is it usually done in the programming environment - does it matter what kind of code I wrote as long as it works and readable?

[Zeroth]

It really depends on who is marking your stuff. Why don't you ask them which way they would prefer. Myself, I don't necessarily care, unless the assignment was to learn the Stack methods.