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 *
xtopdfMy ActiveState Code recipesFollow me on:
