Solving the Towers of Hanoi problem in Python by using 3 stacks

Question

I am attaching my code to solve the Hanoi problem. What do you think? Would you change something? I am attaching the instructions for solving the problem, does the code solve the question? In the role of the 3 towers, 3 cartridges will be used: s1,s2,s3 which initially the numbers 1,2,3,...,n (the big number at the bottom of the stack) are found in s1 and the other two stacks are empty.

It is required to develop a solution characterized by the following distinctions: Arrange the 3 towers in a circle. At every odd step, move the small ring clockwise. In every even step, make the possible move that does not involve the small ring

Requirements for implementing the program: Define n as the number of rings. You will produce 3 cartridges and enter values ​​for the first time. Activate the Hanoi function which accepts 3 cartridges. Requirements for the algorithm: The algorithm will transfer the rings from S1 to one of the other towers. After each transfer of a ring, the contents of the 3 cartridges, and the step number, must be printed. (Each ring transfer is a step).

class Stack:
 def __init__(self):
 self.items = []
 def is_empty(self):
 return self.items == []
 def push(self, item):
 self.items.append(item)
 def pop(self):
 return self.items.pop()
 def getLen(self):
 return len(self.items)
 
def print_stacks(S1, S2, S3):
 print("S1:", S1.items)
 print("S2:", S2.items)
 print("S3:", S3.items)
def hanoi(n, source, helper, target, step_count):
 if n > 0:
 hanoi(n - 1, source, target, helper, step_count)
 target.push(source.pop())
 step_count[0] += 1
 print("Step:", step_count[0])
 print_stacks(S1, S2, S3)
 print()
 hanoi(n - 1, helper, source, target, step_count)
N = 3
S1 = Stack()
S2 = Stack()
S3 = Stack()
for i in range(N, 0, -1):
 S1.push(i)
print("Initial state of the stacks:")
print_stacks(S1, S2, S3)
print()
step_count = [0]
hanoi(N, S1, S2, S3, step_count)
print("Final state of the stacks:")
print_stacks(S1, S2, S3)
print()
print("Length of S1:", S1.getLen())
print("Length of S2:", S2.getLen())
print("Length of S3:", S3.getLen())
print("Total steps:", step_count[0])

Answer 1

I want to concentrate on your class Stack. It is a superfluous Zombie. It does not add any value compared to a list except the single method push() which is only an alias to list.append(). On the other hand you provide a class with nonstandard getLen() and is_empty() methods. Any maintainer of your code has to look up your implementation of Stack to know how to use it. While using a standard list is a no-brainer even for newbies.

The disadvantages of your implementation:

We compare an empty list to an empty Stack

>>> l = list()
>>> s = Stack()

compare

>>> l = list()
>>> str(l)
'[]'
>>> repr(l)
'[]'

to

>>> s = Stack()
>>> str(s)
'<__main__.Stack object at 0x7f10bb040280>'
>>> repr(s)
'<__main__.Stack object at 0x7f10bb040280>'

You or the next maintainer will miss useful string representations for testing/debugging. Any "standard" container shall support str() and repr(). Thus it shall implement at least one of __str__() and __repr__()

compare

>>> len(l)
0

to

>>> len(s)
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
TypeError: object of type 'Stack' has no len()

Any "standard" container shall support len(). Your nonstandard getLen() is a pain. It shall implement __len__().

compare

>>> bool(s)
True

to

>>> bool(l)
False

Now, that is really dangerous. Python "standard" containers evaluate to False if empty. That is what any maintainer would expect. Your nonstandard is_empty() is a pain. No maintainer knows about it without lookup, everyone will rely on the standard way of evaluating to bool or more explicitly evaluating len() == 0 Thus your class shall implement __len__() and optionally __bool__() .

So there are many Problems in your implementation while there is no improvement compared to list. For more Information on "standard" class capabilities please look up https://docs.python.org/3/reference/datamodel.html#special-method-names

My strong advice is - stick to the standards everybody knows. Use a standard list and the method append(). For your personal training you could try to implement a perfect Stack and post it for review (tagged reinventing-the-wheel).

Answer 2

Why is step_count a (single-element) list? Is that because number objects are immutable, and updating that number in the hanoi function would not affect the value at the caller site?

I would return the updated step count instead:

def hanoi(n, source, helper, target, step_count = 0):
 if n > 0:
 step_count = hanoi(n - 1, source, target, helper, step_count)
 # ...
 step_count += 1
 # ...
 step_count = hanoi(n - 1, helper, source, target, step_count)
 
 return step_count

The call from the main program would then simply be

step_count = hanoi(N, S1, S2, S3)

Another suggestion is to add an optional argument with initial elements to the Stack constructor:

class Stack:
 def __init__(self, items = []):
 self.items = list(items)

so that the initialization of the three stacks simplifies to

S1 = Stack(range(N, 0, -1))
S2 = Stack()
S3 = Stack()

Answer 3

What do you think?

I think you did a good job of partitioning the code into a class with functions.

Would you change something?

Yes, I think you could create an array of Stack objects instead of 3 separate objects. Then you can take advantage of loops to construct all the stacks and print all the stacks. For example, instead of repeating print 3 times, use something like:

def print_stacks(stacks):
 i = 1
 for stack in stacks:
 print(f'S{i}:', stack.items)

This also allows you to scale your code better, for example, if you want 4 stacks.

---

You should add docstrings to describe the purpose of the class and each function.

---

Consider a different name for the hanoi function to describe what it does, along with a docstring to mention that it prints something and it calls itself recursively, etc.