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

---

perm_facts version with list comps and functional programming

By Vasudev Ram

Cartoon attribution

A little after writing the program (perm_facts.py) in my recent post:

Permutation facts

(which showed that the number of permutations of n things was the same as n factorial), I saw that I could replace the program's for loops with list comprehensions. So I did that, in the functions num_perms_upto and factorials_upto.

Then I also changed the recursive factorial function to the iterative version shown in the code below. (Although people sometimes use recursive algorithms instead of iterative ones, because they can be simpler to implement, often by using elegant divide and conquer methods), in this case, the recursive version is not really simpler than the iterative one.)

However, I then realized that I could replace the iterative version by a one-line functional version using reduce and operator.mul. So here is the program, perm_fact2.py, with all the changes mentioned above (the iterative version is left in, as comments, but the for loops from the original perm_fact.py are gone, replaced by shorter list comprehensions).

A small benefit of the changes is that the number of lines comes down by a few (if you don't count the commented lines for the iterative version, which I left in there, since it was not in the original), but that was not the goal of the exercise - I was just exploring different ways of doing it.

And whether the code is clearer or not after the changes, may be a matter of personal opinion. For those used to the procedural / imperative style, the changes may make it a bit harder to read, but I think the functional part (reduce with operator.mul, here) and list comprehensions seem to have a certain elegance, and they take slightly less LOC.

Excessive use of reduce, map, etc., just for the sake of it, isn't good, though. And up to 3 or so nested list comprehensions is easy to understand, IME. The thing to remember is that the nested for's (in a nested list comp) run in the same order (leftmost or outermost first) as in a nested for loop. (This is mentioned in the Python docs, and I think they did it that way to be intuitive.)

I ran the program the same way as the previous one, and it gave the same output (verified by DOS's "fc /l outfile1 outfile2", so I will not show the output again here.

#--------------------------------------------------------------
# perm_fact2.py
# Modified version of perm_fact.py, with:
# - two for loops replaced by list comprehensions;
# - recursive factorial() replaced by iterative function;
# - iterative factorial() in turn replaced by 
#   functional version, using reduce().
# Author: Vasudev Ram
# Copyright 2016 Vasudev Ram
# Web site: https://vasudevram.github.io
# Blog: http://jugad2.blotspot.com
# Product store: https://gumroad.com/vasudevram
#--------------------------------------------------------------

import sys
from itertools import permutations
from operator import mul

def num_perms_upto(n):
    return [ len(list(permutations(range(i)))) for i in range(1, n + 1) ]

def factorial(n):
    if n < 0:
        print "Argument n should be >= 0"
        sys.exit(0)
    #-------------------------------------------------------
    #Iterative computation of factorial.
    #f = 1
    #for i in range(1, n + 1):
    #    f *= i
    #return f
    #-------------------------------------------------------
    # Functional computation of factorial, using reduce().
    return reduce(mul, range(1, n + 1), 1)

def factorials_upto(n):
    return [ factorial(i) for i in range(1, n + 1) ]

print "Number of permutations of 1 .. n, where n in 1 .. 10:"
print num_perms_upto(10)
print "Factorial of n, where n in 1 .. 10:"
print factorials_upto(10)

I also timed the runs of both perm_fact.py and perm_fact2.py (and perm_fact2.py separately for both the iterative and functional versions of factorial), a few times each, but did not notice any significant difference. Sometimes one was a bit faster, sometimes the other was, sometimes nearly the same.

(One reason why I thought of timing it in the first place, was because I had read somewhere recently that using map on a sequence can be faster than processing its items in a for loop; haven't tested that, so don't know whether is right or not, but it could be - IIRC, the reason given was that the iteration then happens inside the C implementation of map, and if true, that probably holds for reduce too.)

Also, due to the small amount of code in each, and only a few iterations happening in the code, versus the size of the Python interpreter, it is likely that a good (relative) chunk of the total run time was taken by the loading and initialization of the interpreter, and maybe by parsing the .py files. Other random OS processes running on my machine could also account for the variations. Anyway, the goal here was not really to see if the changes made it faster.

- Vasudev Ram - Online Python training and consulting

FlyWheel - Managed WordPress Hosting

Get updates on my software products / ebooks / courses.

Jump to posts: Python   DLang   xtopdf

Subscribe to my blog by email

My ActiveState recipes

Share |

Recursive computation of simple functions

By Vasudev Ram

Image: Squares. Attribution: Vasudev Ram.

I got this idea to compute some simple functions using recursion, after browsing a chain of links recently, that happened to lead me to the original paper about Lisp, RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I), by its inventor, John McCarthy. I remembered that I had come across it, maybe in a public library, in my college days, and had read it then.

Anyway, I didn't understand the whole paper at the time, but did understand some of the examples of recursion. So today I thought of implementing, just for fun, a few simple algorithms in a recursive way, even though there exist simple non-recursive solutions for them.

So here are a few simple recursive algorithms:

1: Recursive computation of list length:

This uses recursion to find the length of a Python list, i.e. it does what the built-in function len() does. Languages that support recursion often use the terms head and tail of a list, to mean the first item of the list, and the rest of the list (not counting the first item). Of course, the tail of a list is also a list, which is where the recursive algorithm comes in. So the length of a list can be defined recursively as:

0, if the list is empty (i.e. contains no items)
or
1 + the length of the tail of the list, if the list is non-empty, i.e. if it has at least one item in it.
This is a recursive definition because we are using the concept of the list's length in the very definition of its length. As long as the recursive calls terminate at some point, the definition will work.

The code for rec_list_len.py:

# Recursive list length computation.

def rec_list_len(lis):
    if not lis:
        return 0
    #print "calling rec_list_len with lis = {}".format(lis)
    return 1 + rec_list_len(lis[1:])

print "Recursive computation of list length:"
print
for lis_siz in range(5):
    lis = range(lis_siz)
    lis_len = rec_list_len(lis)
    print 'List: {}   Length: {}'.format(lis, lis_len)
    print

# Also test rec_list_len on other kinds of sequences than lists:

s = 'hello there'
print 'String: "{}"   Length: {}'.format(s, rec_list_len(s))
print
s = 'the quick brown fox'
print 'String: "{}"   Length: {}'.format(s, rec_list_len(s))
print

student = ('Jack', 25, 'New York')
print 'Tuple: {}   Length: {}'.format(student, rec_list_len(student))
print
student = ('Jill', 27, 'Paris', 'France')
print 'Tuple: {}   Length: {}'.format(student, rec_list_len(student))
print

Running the program gives this output:

$ python rec_list_len.py
Recursive computation of list length:

List: []   Length: 0

List: [0]   Length: 1

List: [0, 1]   Length: 2

List: [0, 1, 2]   Length: 3

List: [0, 1, 2, 3]   Length: 4

String: "hello there"   Length: 11

String: "the quick brown fox"   Length: 19

Tuple: ('Jack', 25, 'New York')   Length: 3

Tuple: ('Jill', 27, 'Paris', 'France')   Length: 4

Notice that in the above output, we also have the length of strings and tuples computed by the same function. This works, even though I initially wrote the function only to compute list lengths, because lists, strings and tuples are all kinds of Python sequences, and the code I've used in the function is valid for any Python sequence that supports slicing. Lists, strings and tuples all do.

Also, if you uncomment the print statement in function rec_list_len, and run the program, you will see that successively smaller segments (tails, really) of the list are being passed to the function on each (recursive) call. This will help understand what is going on, if it seems unclear otherwise.

This program demonstrates, via a simple computation, the essence of the recursive approach to problem-solving: defining the solution in terms of smaller problems of the same kind. But recursion can also be used to solve harder problems, often elegantly and with a relatively simple algorithm, once we have figured out to solve the original problem in terms of sub-problems of the same kind. For example, tree traversal.

[ It's also worth noting that any recursive solution can be transformed (manually, by the programmer) into an iterative solution that does not use recursion, and uses a while or for loop and a stack instead, and this is sometimes done for the sake of efficiency. ]

Once we've worked out the logic for recursive length computation, code for similar computations on a list is straightforward, with only minor changes from the above:

2: Recursive computation of sum of numbers in a list:

This uses recursion to find the sum of the numbers in a Python list, i.e. it does what the built-in function sum() does.
The code for rec_list_sum.py:

# Recursive list sum computation.
# Assumes list items are numbers.

def rec_list_sum(lis):
    if not lis:
        return 0
    return lis[0] + rec_list_sum(lis[1:])

for r in range(5):
    lis = range(r)
    print "Sum:", rec_list_sum(lis), "List:", lis

Program run and output:

Sum: 0 List: []
Sum: 0 List: [0]
Sum: 1 List: [0, 1]
Sum: 3 List: [0, 1, 2]
Sum: 6 List: [0, 1, 2, 3]

3: Recursive computation of product of numbers in a list:

This uses recursion to find the product of the numbers in a Python list.
The code for rec_list_product.py:

# Recursive list product computation.
# Assumes list items are numbers.

def rec_list_product(lis):
    if not lis:
        return 1
    return lis[0] * rec_list_product(lis[1:])

for r in range(1, 7):
    lis = range(1, r)
    print "Product:", rec_list_product(lis), "List:", lis

Program run and output:

$ python rec_list_product.py
Product: 1 List: []
Product: 1 List: [1]
Product: 2 List: [1, 2]
Product: 6 List: [1, 2, 3]
Product: 24 List: [1, 2, 3, 4]
Product: 120 List: [1, 2, 3, 4, 5]

And that images of nested squares at the top of the post? You guessed it, it's generated by a Python turtle graphics program - not the preceding link in this sentence, that's for the graphics module; see below for the program.

It's a recursive program, naturally :)

Here is the code for the squares program, pasted straight from an IPython session, where I wrote and ran it:

In [63]: def square_and_move(side, dist):
   ....:     square(side)
   ....:     t.penup()
   ....:     t.forward(dist)
   ....:     t.right(90)
   ....:     t.forward(dist)
   ....:     t.left(90)
   ....:     t.pendown()
   ....:     side -= 20
   ....:     if side >= 60:
   ....:         square_and_move(side, dist)
   ....:

In [64]: square_and_move(200, 20)

in which, function square has the obvious definition of drawing a square of the given size (the argument 'side'), by moving forward(side) and then doing right(90), four times each.

Here is the basis of another turtle graphics program that let's you draw stuff interactively.

-Enjoy.

- Vasudev Ram - Online Python training and programming

Signup to hear about new products and services I create.

Posts about Python  Posts about xtopdf

My ActiveState recipes

Share |