Tower of Hanoi program in Higher-Order Perl book, ported to Python

Hi, readers,

I was reading the book Higher Order Perl (Wikipedia entry). It is by Mark Jason Dominus, a well-known figure in the Perl community. I've only read a bit of it so far, but it already looks very good. There are also many reviews of it, all of which say that it is a good book, including one by Damian Conway, another well-known Perl figure.

Early in the book, in chapter 1 - Recursion and Callbacks, there is a nice example program showing how to solve the Tower of Hanoi problem. I had come across the problem earlier, but had not seen a Perl solution before. It's not really any different from the same kind of solution written in other languages, except for some points related to Perl's syntax and semantics, such as the use of local (Perl's my) vs. global variables, specifically with regard to a recursive function, which is what Mark uses for Hanoi.

Anyway, since I had not implemented Hanoi before, I thought of porting Mark's hanoi function from Perl to Python. It's an easy recursive algorithm. (The Wikipedia article has multiple algorithms for Hanoi, some non-recursive too.)

I wrote two versions: the first is hard-coded to solve it for a tower with n equal to 3, where n is the number of disks, and the second does it in a loop for n ranging from 1 to 4, with a prompt and a pause after each one.

If you press q at any of the prompts, the program quits. If you press any other key, it goes on to the next iteration, until the last one. For reading a keypress without needing to press Enter, I used the getch function (get character) from the msvcrt module that comes with Python. MSVCRT stands for Microsoft Visual C Run Time.

So this program is Windows-specific. There are equivalent ways of reading a character without needing to press Enter, for Linux too, but they usually involve some low-level fiddling with the tty / terminal settings, termios, etc. I think ActiveState Code has a recipe for a getch-like function that works on Linux.

Here is the first version, hanoi_01.py:

from __future__ import print_function

"""
This is the code for the Perl version by Mark Jason Dominus:

sub hanoi {
    my ($n, $start, $end, $extra) = @_;
    if ($n == 1) {
        print "Move disk #1 from $start to $end.\n"; # Step 1
    } else {
    hanoi($n-1, $start, $extra, $end); # Step 2
    print "Move disk #$n from $start to $end.\n"; # Step 3
    hanoi($n-1, $extra, $end, $start); # Step 4
    }
}
"""

# This is my Python version ported from the Perl version above:

def hanoi(n, start, end, extra):
    """
    Function hanoi(n, start, end, extra)
    Solve Tower of Hanoi problem for a tower of n disks,
    of which the largest is disk #n. Move the entire tower from
    peg 'start' to peg 'end', using peg 'extra' as a work space.
    """
    if n == 1:
        print("Move disk #1 from {} to {}.\n".format(start, end))
    else:
        # Recursive call #1
        hanoi(n - 1, start, extra, end)
        print("Move disk #{} from {} to {}.\n".format(n, start, end))
        # Recursive call #2
        hanoi(n - 1, extra, end, start)
        
# Call to hanoi() with 3 disks, i.e. n = 3:
hanoi(3, 'A', 'C', 'B')

Here is the output on running it:

$ python hanoi_01.py
Move disk #1 from A to C.

Move disk #2 from A to B.

Move disk #1 from C to B.

Move disk #3 from A to C.

Move disk #1 from B to A.

Move disk #2 from B to C.

Move disk #1 from A to C.

Here is the second version, hanoi_02.py:

from __future__ import print_function
from msvcrt import getch

"""
Tower of Hanoi program
---
By Vasudev Ram
Web site: https://vasudevram.github.io
Blog: https://jugad2.blogspot.com
Twitter: https://mobile.twitter.com/vasudevram
Product store: https://gumroad.com/vasudevram
---
Translated to Python from the Perl version in the book Higher-Order Perl
by Mark Jason Dominus: https://hop.perl.plover.com/book/ , with some 
minor enhancements related to interactivity.
"""

def hanoi(n, start, end, extra):
    """
    Function hanoi(N, start, end, extra)
    Solve Tower of Hanoi problem for a tower of N disks,
    of which the largest is disk #N. Move the entire tower from
    peg 'start' to peg 'end', using peg 'extra' as a work space.
    """
    assert n > 0
    if n == 1:
        print("Move disk #1 from {} to {}.".format(start, end))
    else:
        hanoi(n - 1, start, extra, end)
        print("Move disk #{} from {} to {}.".format(n, start, end))
        hanoi(n - 1, extra, end, start)
        
for n in range(1, 5):
    print("\nTower of Hanoi with n = {}:".format(n))
    hanoi(n, 'A', 'C', 'B')
    if n < 4:
        print("\nPress q to quit, any other key for next run: ")
        c = getch()
        if c.lower() == 'q':
            break

Here is the output on running it - I pressed q after 3 iterations:

$ python hanoi_02.py

Tower of Hanoi with n = 1:
Move disk #1 from A to C.

Press q to quit, any other key for next run:

Tower of Hanoi with n = 2:
Move disk #1 from A to B.
Move disk #2 from A to C.
Move disk #1 from B to C.

Press q to quit, any other key for next run:

Tower of Hanoi with n = 3:
Move disk #1 from A to C.
Move disk #2 from A to B.
Move disk #1 from C to B.
Move disk #3 from A to C.
Move disk #1 from B to A.
Move disk #2 from B to C.
Move disk #1 from A to C.

Press q to quit, any other key for next run:

Note that getch does not echo the key that is pressed to the screen. If you want that, use getche, from the same module msvcrt.

Viewing the output, I observed that for 1 disk, it takes 1 move, for 2 disks, it takes 3 moves, and for 3 disks, it takes 7 moves. From this, by informally applying mathematical induction, we can easily figure out that for n disks, it will take 2 ** n - 1 moves. The Wikipedia article about the Tower of Hanoi confirms this.

That same Wikipedia article (linked above) also shows that the Tower of Hanoi has some interesting applications:

Excerpts:

[ The Tower of Hanoi is frequently used in psychological research on problem solving. There also exists a variant of this task called Tower of London for neuropsychological diagnosis and treatment of executive functions. ]

[ Zhang and Norman[10] used several isomorphic (equivalent) representations of the game to study the impact of representational effect in task design. ]

[ The Tower of Hanoi is also used as a Backup rotation scheme when performing computer data Backups where multiple tapes/media are involved. ]

[ The Tower of Hanoi is popular for teaching recursive algorithms to beginning programming students. ]

And this application is possibly the most interesting of the lot - ants solving the Tower of Hanoi problem :)

[ In 2010, researchers published the results of an experiment that found that the ant species Linepithema humile were successfully able to solve the 3-disk version of the Tower of Hanoi problem through non-linear dynamics and pheromone signals. ]

Also check out the section in that Wikipedia article with the title:

"General shortest paths and the number 466/885"

Not directly related, but similar to the above ratio, did you know that there is an easy-to-remember and better approximation to the number pi, than the ratio 22/7 that many of us learned in school?

Just take the 1st 3 odd numbers, i.e. 1, 3, 5, repeat each of them once, and join all those 6 digits, to get 113355, split that number in the middle, and divide the 2nd half by the 1st half, i.e 355/113, which gives 3.1415929203539823008849557522124. (See the section titled "Approximate value and digits" in the Wikipedia article about pi linked above, for this and other approximations for pi).

Pressing the pi button in Windows CALC.EXE gives 3.1415926535897932384626433832795, and comparing that with the ratio 355/113 above, shows that the ratio is accurate to 6 decimal places. I've read somewhere that this ratio was used by mathematicians in ancient India.

Here are some interesting excerpts from the Wikipedia article about pi:

[ The number pi is a mathematical constant. Originally defined as the ratio of a circle's circumference to its diameter, it now has various equivalent definitions and appears in many formulas in all areas of mathematics and physics. It is approximately equal to 3.14159. It has been represented by the Greek letter "p" since the mid-18th century, though it is also sometimes spelled out as "pi". It is also called Archimedes' constant. ]

[ Being an irrational number, pi cannot be expressed as a common fraction (equivalently, its decimal representation never ends and never settles into a permanently repeating pattern). Still, fractions such as 22/7 and other rational numbers are commonly used to approximate pi. The digits appear to be randomly distributed. In particular, the digit sequence of pi is conjectured to satisfy a specific kind of statistical randomness, but to date, no proof of this has been discovered. Also, pi is a transcendental number; that is, it is not the root of any polynomial having rational coefficients. ]

[ Being an irrational number, pi cannot be expressed as a common fraction (equivalently, its decimal representation never ends and never settles into a permanently repeating pattern). Still, fractions such as 22/7 and other rational numbers are commonly used to approximate p. The digits appear to be randomly distributed. In particular, the digit sequence of pi is conjectured to satisfy a specific kind of statistical randomness, but to date, no proof of this has been discovered. Also, pi is a transcendental number; that is, it is not the root of any polynomial having rational coefficients. This transcendence of pi implies that it is impossible to solve the ancient challenge of squaring the circle with a compass and straightedge. ]

[ Ancient civilizations required fairly accurate computed values to approximate pi for practical reasons, including the Egyptians and Babylonians. Around 250 BC the Greek mathematician Archimedes created an algorithm for calculating it. In the 5th century AD Chinese mathematics approximated pi to seven digits, while Indian mathematics made a five-digit approximation, both using geometrical techniques. The historically first exact formula for p, based on infinite series, was not available until a millennium later, when in the 14th century the Madhava–Leibniz series was discovered in Indian mathematics. ]

(Speaking of Indian mathematics, check out this earlier post by me:

Bhaskaracharya and the man who found zero.)

[ Because its most elementary definition relates to the circle, pi is found in many formulae in trigonometry and geometry, especially those concerning circles, ellipses, and spheres. In more modern mathematical analysis, the number is instead defined using the spectral properties of the real number system, as an eigenvalue or a period, without any reference to geometry.

It appears therefore in areas of mathematics and the sciences having little to do with the geometry of circles, such as number theory and statistics, as well as in almost all areas of physics.

The ubiquity of pi makes it one of the most widely known mathematical constants both inside and outside the scientific community. Several books devoted to pi have been published, and record-setting calculations of the digits of pi often result in news headlines. Attempts to memorize the value of pi with increasing precision have led to records of over 70,000 digits. ]

- Enjoy.

---

- Vasudev Ram - Online Python training and consulting

---

I conduct online courses on Python programming, Unix / Linux commands and shell scripting and SQL programming and database design, with course material and personal coaching sessions.

The course details and testimonials are here.

Contact me for details of course content, terms and schedule.

Try FreshBooks: Create and send professional looking invoices in less than 30 seconds.

Getting a new web site or blog, and want to help preserve the environment at the same time? Check out GreenGeeks.com web hosting.

Sell your digital products via DPD: Digital Publishing for Ebooks and Downloads.

Learning Linux? Hit the ground running with my vi quickstart tutorial.

I wrote it at the request of two Windows system administrator friends who were given additional charge of some Unix systems. They later told me that it helped them to quickly start using vi to edit text files on Unix. Of course, vi/vim is one of the most ubiquitous text editors around, and works on most other common operating systems and on some uncommon ones too, so the knowledge of how to use it will carry over to those systems too.

Check out WP Engine, powerful WordPress hosting.

Sell More Digital Products With SendOwl.

Get a fast web site with A2 Hosting.

Creating online products for sale? Check out ConvertKit, email marketing for online creators.

Teachable: feature-packed course creation platform, with unlimited video, courses and students.

Posts about: Python * DLang * xtopdf

My ActiveState Code recipes

Follow me on:

• My blog jugad2
• Gumroad
• LinkedIn
• Twitter

---