Tower of Hanoi without recursion

Question

Hi I am pretty new to programming and I would like you to give me some feedback about my code, how does it look, what could be better. Thank you.

A = [] 
B = []
C = []
PegDict = {'A': A,'B': B,'C': C} #Would it be better to use a two dimensional array?
discs = int(input("Podaj ilość dysków: "))
for i in range(discs, 0, -1):
 A.append(i)
movesNeeded = pow(2, discs) - 1
StartingPeg = A.copy()
def move(fromm, to):
 to.append(fromm[-1])
 fromm.pop()

Moves the smallest disc one peg to the left. This part could be done better i think.

def moveLeft():
 if A and A[-1] == 1:
 move(A, C)
 return
 if B and B[-1] == 1:
 move(B, A)
 return
 if C and C[-1] == 1:
 move(C, B)
 return

Moves the smallest disc one peg to the right

def moveRight():
 if A and A[-1] == 1:
 move(A, B)
 return
 if B and B[-1] == 1:
 move(B, C)
 return
 if C and C[-1] == 1:
 move(C, A)
 return

Returns key of a peg that is the only valid move target for a cartain peg

def PossibleMove(Peg):
 if Peg:
 if Peg[-1] != 1:
 for i in PegDict:
 x = PegDict[i]
 if not x:
 return i
 elif Peg[-1] < x[-1]:
 return i

Main part

moves = 0
while not C == StartingPeg:
 if discs%2 == 0:
 moveRight()
 moves += 1
 else:
 moveLeft()
 moves += 1
 print(A)
 print(B)
 print(C)
 print()
 for key in PegDict:
 if PossibleMove(PegDict[key]) != None:
 fromPeg = PegDict[key]
 onePossibleMove = PossibleMove(PegDict[key])
 if fromPeg:
 moves += 1
 move(fromPeg, PegDict[onePossibleMove])
 print(A)
 print(B)
 print(C)
 print()
print()
print('Moves: '+ str(moves))
print('Minimal number of moves: '+ str(movesNeeded))

Answer 1

PEP-8

The Style Guide for Python Code has many stylistic guidelines that all Python programs should follow.

• Naming
  • functions, methods, and variables should all be snake_case. CapitalWords are reserved for Types and ClassNames. So movesNeeded should be moves_needed and PegDict should be peg_dict, and so on.
• Commas
  • All commas should be followed by exactly one space. {'A': A,'B': B,'C': C} violates this.
• Binary operators
  • Binary operators should be surrounded by one space. You mostly follow this, except for the print('Moves: '+ str(moves)) statements at the end.

Exponentiation

movesNeeded = pow(2, discs) - 1

Python has the ** operator, for exponentiation. Thus, this could be written slightly more compactly:

moves_needed = 2 ** discs - 1

Initial list generation

A = []
for i in range(discs, 0, -1):
 A.append(i)

This is a little verbose. You are already using the range() method to generate the disc numbers; you could simply create a list directly from the result:

a = list(range(discs, 0, -1))

Moving a Disc

def move(fromm, to):
 to.append(fromm[-1])
 fromm.pop()

I'm going to assume fromm is not a spelling error, but rather avoiding the from keyword. The PEP-8 recommendation is a trailing underscore: from_. My personal preference is to use synonyms.

.pop() returns the item removed from the list, which is the value you used fromm[-1] to retrieve. Therefore, these operations could easily be combine into one statement:

def move(source, destination):
 destination.append(source.pop())

Repeated Code

 print(A)
 print(B)
 print(C)
 print()

You've repeated this code twice. Once moving the small disc, once moving a larger disc. Instead of repeating the code, you should move this into a function. Then, if you change how the discs are shown (curses, GUI, ...), you only have to alter the code once.

def print_pegs(a, b, c):
 print(a)
 print(b)
 print(c)
 print()

Iterating over a container

 for key in PegDict:
 if PossibleMove(PegDict[key]) != None:
 fromPeg = PegDict[key]
 onePossibleMove = PossibleMove(PegDict[key])

In this code, you are iterating over the PegDict, fetching the keys, and using the key to look up the dictionary value. In fact, you never use the key for anything else. You do not need the key at all, and could simply iterate over the contents of the dictionary:

 for peg in peg_dict.values():
 if possible_move(peg) != None:
 from_peg = peg
 one_possible_move = possible_move(peg)

But notice we are computing using possible_move(peg) twice. This is inefficient. You should compute the result once, save it in a temporary, and use the temporary variable for further tests and assignments:

 for peg in peg_dict.values():
 move = possible_move(peg)
 if move != None:
 from_peg = peg
 one_possible_move = move

More Advanced Changes

Left or Right?

Each iteration, you check if the number of discs was even or odd, and call the moveLeft() or moveRight() function. Since the number of discs is constant, you always make the same choice. You could move this decision out of the loop.

move_smallest_disc = move_left if disc % 2 != 0 else move_right
while len(c) != discs: # A simpler termination condition
 move_smallest_disc()
 print_pegs(a, b, c)
 moves += 1
 ...

But I've a different option...

Cyclic Peg Order

You always move the smallest disc either:

• a -> b -> c -> a -> b -> c
• a -> c -> b -> a -> c -> b

You can keep track of which order you need with a list:

 if discs % 2 == 1:
 peg = [a, c, b]
 else:
 peg = [a, b, c]

And move the smallest disc from peg[0] to peg[1], without having to hunt for which peg the smallest disc is on:

 move(peg[0], peg[1])

And later rotate the peg list:

 peg = peg[1:] + peg[:1] # [a, b, c] -> [b, c, a] -> [c, a, b] -> [a, b, c]

After moving the smallest disc onto peg[1], the only possible moves for the larger disc will be peg[0] -> peg[2] or peg[2] -> peg[0], so you can greatly simplify the possible move determination, by just looking at those two pegs:

 source, destination = possible_move(peg[0], peg[2])
 move(source, destination)

Refactored Code

from pathlib import Path
import gettext
gettext.install('hanoi', Path(__file__).parent)
def move(source, destination):
 destination.append(source.pop())
def possible_move(peg1, peg2):
 if peg1 and (not peg2 or peg1[-1] < peg2[-1]):
 return peg1, peg2
 else:
 return peg2, peg1
def print_pegs(a, b, c):
 print(a)
 print(b)
 print(c)
 print()
def tower_of_hanoi(discs):
 a = list(range(discs, 0, -1))
 b = []
 c = []
 minimum_moves = 2 ** discs - 1
 if discs % 2 == 1:
 peg = [a, c, b]
 else:
 peg = [a, b, c]
 moves = 0
 while len(c) != discs:
 if moves % 2 == 0:
 move(peg[0], peg[1]) # Smallest disc now on peg[1]
 else:
 source, destination = possible_move(peg[0], peg[2])
 move(source, destination)
 peg = peg[1:] + peg[:1] # Rotate the peg ordering
 print_pegs(a, b, c)
 moves += 1
 print()
 print(_('Moves:'), moves)
 print(_('Minimal moves:'), minimum_moves)
if __name__ == '__main__':
 discs = int(input(_('Enter the number of disks: ')))
 tower_of_hanoi(discs)

If you run pygettext on this, you can make a hanoi.pot template file, copy it to hanoi.po and put translations into it:

msgid "Moves:"
msgstr "Liczba ruchów:"
msgid "Minimal moves:"
msgstr "Minimalna liczba ruchów:"
msgid "Enter the number of disks: "
msgstr "Podaj ilość dysków: "

Run msgfmt on that to generate an hanoi.mo file, and store it the subdirectory: pl/LC_MESSAGES.

Running LANG="pl" ./hanoi.py on my machine, gives:

Podaj ilość dysków: 2
[2]
[1]
[]
[]
[1]
[2]
[]
[]
[2, 1]
Liczba ruchów: 3
Minimalna liczba ruchów: 3

With luck, I haven't butchered the translated strings too badly.

• Eman Yalpsid: Hi! To me the following is more readable at a glance: def possible_move(*args): return sorted(args, key=lambda ls: ls[-1] if ls else float('inf')), but that may very well simply be a sign of deeper personal issues. Cheers.
• AJNeufeld: You're not wrong. I'm unhappy with my current possible_moves(). I'd like to hit the sweet spot between yours & mine, though.
• AJNeufeld: @Andrew Compromise: when no-one gets what they want. Reduced it from 10 lines down to 4, but 1 line is just going too far. :-)