I have just finished a small program for Tower of Hanoi using recursion. I did it to practice OOP which I recently learnt. It took me about 2 hours to research about the recursive algorithm and write out the code. It works, after much debugging... However, after comparing to other implementations, I realised my code is rather long, plus unconventional when it comes to how I approach and execute as well as the naming conventions.

Could I have some feedback about the program? Thank you!

class rod:
    move_count = 0

    def __init__(self,disks=[],position=""):
        self.diskslist=disks
        self.rod_position=position
    # Remove the top disk of a rod
    def remove_top(self):
        print(f"Move the disk of size {self.diskslist[0].size} from {self.rod_position} Rod ", end="")
        rod.move_count += 1
        return self.diskslist.pop(0)
    # Add a disk to the top of a rod. Only allows in two conditions a. No disks currently on that rod b. Disk smaller than the disk below it
    def add_to_top(self,current_disk,announce=True):
        if len(self.diskslist) == 0:
            if announce==True:
                print(f"on to the top of the {self.rod_position} Rod", end="\n")
            self.diskslist.insert(0,current_disk)
            return True
        else:
            if current_disk.size < self.diskslist[-1].size:
                if announce == True:
                    print(f"on to the top of the {self.rod_position} Rod", end="\n")
                self.diskslist.insert(0,current_disk)
                return True
            else:
                return False


class disk:
    num=0
    def __init__(self,size):
        self.size=size
        disk.num += 1


#Generating 8 disks of increasing size
disk_num=8
disks = []
for i in range(disk_num):
    disks.append(disk(i))

#Generating 3 rods
rods = []
rods.append(rod([],"Left"))
rods.append(rod([],"Middle"))
rods.append(rod([],"Right"))

# Attaching all disks to the left rod
for i in range(len(disks)):
    rods[0].add_to_top(disks[len(disks)-i-1],False)


def recursive_solve(current_rod, lower_range, target_rod):
    # If only moving the top disk, execute it
    if lower_range == 0:
        rods[target_rod].add_to_top(rods[current_rod].remove_top())
    # If not, keeping simplifying the recursion.
    else:
        alt_rod = 3 - current_rod - target_rod
        recursive_solve(current_rod, lower_range - 1, alt_rod)
        recursive_solve(current_rod, 0, target_rod)
        recursive_solve(alt_rod, lower_range - 1, target_rod)

print(f"The steps needed to move {disk_num} pieces of disks are:")
recursive_solve(0,len(disks)-1,2)

for i in range(len(rods)):
    print(f'\n For rod number {i+1}:',end=" ")
    for j in range(len(rods[i].diskslist)):
        print(rods[i].diskslist[j].size,end=" ")

print(f'\n The number of moves taken in total is {rod.move_count}')
up vote 19 down vote accepted

Your code seems to be working and trying to use OOP is a nice touch. Let's see what can be improved.

Style

There is an official standard Python style guide called PEP 8. This is a highly recommended reading. It gives guidelines to help writing code that is both readable and consistent. The Python community tries to follow these guidelines, more or less strictly (a key aspect of PEP 8 is that it provides guidelines and not strict rules to follow blindly).

It deals with various aspects of the code style: naming conventions, indentation convention, etc.

You'll find various tools to try to check whether your code is PEP 8 compliant and if is it not, to try and fix this:

In your case, various things can be modified: class names should start with an uppercase letter, whitespace can be improved, etc.

Docstring

There is also a document describing Docstring conventions called PEP 257.

The comments you've written on top of the functions definition could be used as the function docstring.

The Disk class

It seems like num is not needed. Thus, the whole class could be written:

class Disk:
    def __init__(self, size):
        self.size = size

Ultimately, we could try to see if such a class is needed at all.

Building disks

disk_num could be written in uppercase as it is a constant.

disks could be initialised using list comprehension:

# Generating disks of increasing size
DISK_NUM = 8
disks = [Disk(i) for i in range(DISK_NUM)]

Building rods

You could use keyword arguments to provide only the position value without the need to provide the disks value (and thus, rely on the default behavior). Another option could be to change the argument order to have the position first - by the way, maybe "name" would be better than "position" as it conveys better the fact that it is not an integer used for computation but just a string just for logging.

rods.append(Rod(position="Left"))
rods.append(Rod(position="Middle"))
rods.append(Rod(position="Right"))

We could once again use list comprehension to define the rods here:

# Generating rods
rods = [Rod(position=p) for p in ("Left", "Middle", "Right")]

Comparison to boolean

You don't need to write: if announce==True, you can simply write: if announce.

Rewrite logic in add_to_top

You could use elif to make the various cases easier to identify and remove a level of indentation in the second part of the function.

def add_to_top(self,current_disk,announce=True):
    """Add a disk to the top of a rod. Only allows in two conditions a. No disks currently on that rod b. Disk smaller than the disk below it."""
    if len(self.diskslist) == 0:
        if announce:
            print(f"on to the top of the {self.rod_position} Rod", end="\n")
        self.diskslist.insert(0,current_disk)
        return True
    elif current_disk.size < self.diskslist[-1].size:
        if announce:
            print(f"on to the top of the {self.rod_position} Rod", end="\n")
        self.diskslist.insert(0,current_disk)
        return True
    else:
        return False

It is now clearer that the 2 first cases are identical and can be merged:

def add_to_top(self,current_disk,announce=True):
    """Add a disk to the top of a rod. Only allows in two conditions a. No disks currently on that rod b. Disk smaller than the disk below it."""
    if (len(self.diskslist) == 0) or (current_disk.size < self.diskslist[-1].size):
        if announce:
            print(f"on to the top of the {self.rod_position} Rod", end="\n")
        self.diskslist.insert(0,current_disk)
        return True
    else:
        return False

Also, maybe you could throw an exception when the disk size is invalid instead of just returning False:

def add_to_top(self,current_disk,announce=True):
    """Add a disk to the top of a rod. Only allows in two conditions a. No disks currently on that rod b. Disk smaller than the disk below it."""
    if self.diskslist and current_disk.size >= self.diskslist[-1].size:
        raise Exception("Invalid disk size")

    if announce:
        print(f"on to the top of the {self.rod_position} Rod", end="\n")
    self.diskslist.insert(0,current_disk)

Reconsider the Rod initialisation

A disk list can be provided to the Rod initialisation.

Two things are a bit awkward here:

  • you are using Mutable Default Arguments which is a common Gotcha in Python

  • the provided list may be unsorted: if we really want to provide the list, maybe we should pass it through the add_to_top logic element by element or just check that it is sorted.

It may be easier to weaken the API by getting rid of it and default to [].

def __init__(self, name=""):
    self.diskslist = []
    self.rod_name = name

At this stage, the code looks like:

class Rod:
    move_count = 0

    def __init__(self, name=""):
        self.diskslist = []
        self.rod_name = name

    def remove_top(self):
        """Remove the top disk of a rod."""
        print(f"Move the disk of size {self.diskslist[0].size} from {self.rod_name} Rod ", end="")
        Rod.move_count += 1
        return self.diskslist.pop(0)

    def add_to_top(self,current_disk,announce=True):
        """Add a disk to the top of a rod. Only allows in two conditions a. No disks currently on that rod b. Disk smaller than the disk below it."""
        if self.diskslist and current_disk.size >= self.diskslist[-1].size:
            raise Exception("Invalid disk size") 

        if announce:
            print(f"on to the top of the {self.rod_name} Rod", end="\n")
        self.diskslist.insert(0,current_disk)


class Disk:
    def __init__(self, size):
        self.size = size


def recursive_solve(current_rod, lower_range, target_rod):
    # If only moving the top disk, execute it
    if lower_range == 0:
        rods[target_rod].add_to_top(rods[current_rod].remove_top())
    # If not, keeping simplifying the recursion.
    else:
        alt_rod = 3 - current_rod - target_rod
        recursive_solve(current_rod, lower_range - 1, alt_rod)
        recursive_solve(current_rod, 0, target_rod)
        recursive_solve(alt_rod, lower_range - 1, target_rod)


# Generating disks of increasing size
DISK_NUM = 8
disks = [Disk(i) for i in range(DISK_NUM)]

# Generating rods
rods = [Rod(name=p) for p in ("Left", "Middle", "Right")]

# Attaching all disks to the left rod
for i in range(len(disks)):
    rods[0].add_to_top(disks[len(disks)-i-1],False)


print(f"The steps needed to move {DISK_NUM} pieces of disks are:")
recursive_solve(0,len(disks)-1,2)

for i in range(len(rods)):
    print(f'\n For rod number {i+1}:',end=" ")
    for j in range(len(rods[i].diskslist)):
        print(rods[i].diskslist[j].size,end=" ")

print(f'\n The number of moves taken in total is {Rod.move_count}')

Loop with the proper tools

I highly recommend Ned Batchelder's talk "Loop like a native". Basically, anytime you use something like for xxx in range(len(yyy)), there is a better way to do it. In your case, enumerate can help you as well to write:

# Attaching all disks to the left rod
for d in reversed(disks):
    rods[0].add_to_top(d, False)

print(f"The steps needed to move {DISK_NUM} pieces of disks are:")
recursive_solve(0,len(disks)-1,2)

for i, rod in enumerate(rods):
    print(f'\n For rod number {i+1}:',end=" ")
    for d in rod.diskslist:
        print(d.size,end=" ")

Also, we could consider that we can refer to rod by their name instead of their positions and thus get rid of positions altogether:

for rod in rods:
    print(f'\n For rod {rod.rod_name}:',end=" ")
    for d in rod.diskslist:
        print(d.size,end=" ")

The recursive_solve function

The fact that you access rods from the recursive_solve function seems a bit weird to me. It may be easier to provide the 3 rods to the function.

Also, providing the length of disks should not be necessary: in the best possible world, we could just rely on the number of disks on the starting rod.

I've performed a few changes to handle this, using an intermediate function:

def recursive_solve(start_rod, end_rod, third_rod, nb_disk_to_move):
    if nb_disk_to_move == 1:
        end_rod.add_to_top(start_rod.remove_top())
    # If not, keeping simplifying the recursion.
    else:
        recursive_solve(start_rod, third_rod, end_rod, nb_disk_to_move - 1)
        recursive_solve(start_rod, end_rod, third_rod, 1)
        recursive_solve(third_rod, end_rod, start_rod, nb_disk_to_move - 1)




def move(start_rod, end_rod, third_rod):
    nb_disk = len(start_rod.diskslist)
    print(f"The steps needed to move {nb_disk} pieces of disks are:")
    recursive_solve(start_rod, end_rod, third_rod, nb_disk)

...    
move(rods[0], rods[2], rods[1])

Also, that removes the need for the disks variable:

# Attaching all disks to the left rod
for i in reversed(range(DISK_NUM)):
    rods[0].add_to_top(Disk(i), False)

move(rods[0], rods[2], rods[1])

Finally, the function can be slightly simplified:

def recursive_solve(start_rod, end_rod, third_rod, nb_disk_to_move):
    if nb_disk_to_move:
        recursive_solve(start_rod, third_rod, end_rod, nb_disk_to_move - 1)
        end_rod.add_to_top(start_rod.remove_top())
        recursive_solve(third_rod, end_rod, start_rod, nb_disk_to_move - 1)

More OOP

One of the principle of OOP is the encapsulation. In our case, disklist could be considered as an implementation detail which is best not to rely on. In order to print the content on a rod, we could write a __str__ magic method. Then, the calling code becomes much simpler:

    def __str__(self):
        return self.rod_name + ": " + " ".join(str(d.size) for d in self.diskslist)

for rod in rods:
    print(f' For rod {rod}')

At this stage, the code looks like:

class Rod:
    move_count = 0

    def __init__(self, name):
        self.diskslist = []
        self.rod_name = name

    def remove_top(self):
        """Remove the top disk of a rod."""
        print(f"Move the disk of size {self.diskslist[0].size} from {self.rod_name} Rod ", end="")
        Rod.move_count += 1
        return self.diskslist.pop(0)

    def add_to_top(self,current_disk,announce=True):
        """Add a disk to the top of a rod. Only allows in two conditions a. No disks currently on that rod b. Disk smaller than the disk below it."""
        if self.diskslist and current_disk.size >= self.diskslist[-1].size:
            raise Exception("Invalid disk size") 

        if announce:
            print(f"on to the top of the {self.rod_name} Rod", end="\n")
        self.diskslist.insert(0,current_disk)

    def __str__(self):
        return self.rod_name + ": " + " ".join(str(d.size) for d in self.diskslist)


class Disk:
    def __init__(self, size):
        self.size = size


def recursive_solve(start_rod, end_rod, third_rod, nb_disk_to_move):
    if nb_disk_to_move:
        recursive_solve(start_rod, third_rod, end_rod, nb_disk_to_move - 1)
        end_rod.add_to_top(start_rod.remove_top())
        recursive_solve(third_rod, end_rod, start_rod, nb_disk_to_move - 1)

def move(start_rod, end_rod, third_rod):
    nb_disk = len(start_rod.diskslist)
    print(f"The steps needed to move {nb_disk} pieces of disks are:")
    recursive_solve(start_rod, end_rod, third_rod, nb_disk)


# Generating rods
rods = [Rod(name=p) for p in ("Left", "Middle", "Right")]

# Attaching all disks to the left rod
DISK_NUM = 8
for i in reversed(range(DISK_NUM)):
    rods[0].add_to_top(Disk(i), False)

move(rods[0], rods[2], rods[1])

for rod in rods:
    print(f' For rod {rod}')

print(f'\n The number of moves taken in total is {Rod.move_count}')

I have to stop here, I'll try to continue.

  • 1
    i'd advise preferring __repr__ to __str__ (and formatting the result appropriately) unless the type actually represents a string in some sense — much the same way as i'd advise avoiding __int__ unless it actually makes sense to convert the type to an integer :) – Eevee Oct 15 at 18:35
  • Thanks for the suggestion! I always used the 2 functions in such a way that __str__ returned a string for a human while __repr__ returned a string corresponding to Python code. Your explanation seems good (or better), I'll keep that in mind next time I have to choose! – Josay Oct 15 at 20:32
  • 1
    I have one nitpick: rod_names are just duplicated and named versions of their position in rods and used so they can identify where they are. It having to maintain a property of it's own container is not ideal: if you move the announcements into recursive_solve you can remove names/positions entirely and just use index of rods, probably via a lookup for the friendly name/position, ala friendly_position = ["Left', 'Middle', 'Right']; print(friendly_position[end_rod]) – TemporalWolf Oct 15 at 23:10
  • @TemporalWolf This sounds promising. Maybe it'd be worth making this an answer on its own. Please let me know if you do so because I'd be interested in the result. – Josay Oct 16 at 7:41

Just a couple minor suggestions unrelated to the algorithm:

In a couple places, you have:

if announce==True:

This is redundant though. if is just checking if a value is truthy or not. If announce is equal to True, that means it's already truthy. Just write:

if announce:

Along that same vein, you have:

if len(self.diskslist) == 0:

Which is also arguably verbose.

If you open a REPL and run:

bool([])

You'll see that it evaluates to False. Empty collections are falsey in Python. Instead of checking the length, you could write:

if self.diskslist: # True if non-empty

Or

if not self.diskslist: # True if empty

If you don't want to need to reverse your conditional bodies

  • "and you want to make sure that it's actually equal to True and not just truthy" Actually, it doesn't even serve that purpose. Try typing 1==True into a Python console. To check that announce actually is True, and not just truthy, you have to do announce is True. – Acccumulation Oct 18 at 17:25
  • @Acccumulation Oops, you're right. I'll fix that on my break. – Carcigenicate Oct 18 at 18:00

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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