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

---

Perl-like "unless" (reverse if) feature in Python

By Vasudev Ram

Flowchart image attribution

I was mentally reviewing some topics to discuss for a Python training program I was running. Among the topics were statements, including the if statement. I recollected that some languages I knew of, such as Perl, have an unless statement, which is like a reverse if statement, in that only the first nested suite (of statements) is executed if the Boolean condition is false, whereas only the second nested suite is executed if the condition is true. See the examples below.

The term "suite" used above, follows the terminology used in Python documentation such as the Python Language Reference; see this if statement definition, for example.

That is, for the if statement:

if condition:
    suite1  # nested suite 1
else:
    suite2  # nested suite 2

results in suite1 being run if condition is true, and suite2 being run if condition is false, whereas, for the unless statement:

unless condition:
    suite1
else:
    suite2

, the reverse holds true.

Of course, there is no unless statement in Python. So I got the idea of simulating it, at least partially, with a function, just for fun and as an experiment. Here is the first version, in file unless.py:

# unless.py v1

# A simple program to partially simulate the unless statement 
# (a sort of reverse if statement) available in languages like Perl.
# The simulation is done by a function, not by a statement.

# Author: Vasudev Ram
# Web site: https://vasudevram.github.io
# Blog: https://jugad2.blogspot.com
# Product store: https://gumroad.com

# Define the unless function.
def unless(cond, func_if_false, func_if_true):
    if not cond:
        func_if_false()
    else:
        func_if_true()

# Test it.
def foo(): print "this is foo"
def bar(): print "this is bar"

a = 1
# Read the call below as:
# Unless a % 2 == 0, call foo, else call bar
unless (a % 2 == 0, foo, bar)
# Results in foo() being called.

a = 2
# Read the call below as:
# Unless a % 2 == 0, call foo, else call bar
unless (a % 2 == 0, foo, bar)
# Results in bar() being called.

Here is the output:

$ python unless.py
this is foo
this is bar

This simulation of unless works because functions are objects in Python (since almost everything is an object in Python, like almost everything in Unix is a file), so functions can be passed to other functions as arguments (by passing just their names, without following the names with parentheses).

Then, inside the unless function, when you apply the parentheses to those two function names, they get called.

This approach to simulation of the unless statement has some limitations, of course. One is that you cannot pass arguments to the functions [1]. (You could still make them do different things on different calls by using global variables (not good), reading from files, or reading from a database, so that their inputs could vary on each call).

[1] You can actually pass arguments to the functions in a few ways, such as using the *args and **kwargs features of Python, as additional arguments to unless() and then forwarding those arguments to the func_if_false() and func_if_true() calls inside unless().

Another limitation is that this simulation does not support the elif clause.

However, none of the above limitations matter, of course, because you can also get the effect of the unless statement (i.e. a reverse if) by just negating the Boolean condition (with the not operator) of an if statement. As I said, I just tried this for fun.

The image at the top of the post is of a flowchart.

For something on similar lines (i.e. simulating a language feature with some other code), but for the C switch statement simulated (partially) in Python, see this post I wrote a few months ago:

Simulating the C switch statement in Python

And speaking of Python language features, etc., here is a podcast interview with Guido van Rossum (creator of the Python language), about the past, present and future of Python.

Enjoy.

- Vasudev Ram - Online Python training and consulting

Get updates (via Gumroad) on my forthcoming apps and content.

Jump to posts: Python * DLang * xtopdf

Subscribe to my blog by email

My ActiveState Code recipes

Follow me on: LinkedIn * Twitter

Managed WordPress Hosting by FlyWheel

Share |

Interview: Linux Journal with Larry Wall (1999)

Larry Wall, the Guru of Perl | Linux Journal http://m.linuxjournal.com/article/3394

Entertaining.

Posted via mobile.
Vasudev Ram
Software training and consulting.
Python, Linux, SQL databases, open source technologies.
www.dancingbison.com

50% off on all O'Reilly books in Back to (Tech) School Sale

By Vasudev Ram

O'Reilly Media is conducting a sale - 50% off on the price of all O'Reilly books. The sale is on until 10 September 2013.

They are calling it the "Back to (Tech) School Sale".

You can click on the banner above to go to the site for the O'Reilly books sale.

Disclosure: it is an affiliate link, so I will get a small percentage of the sale value, since I recently became an O'Reilly Media affiliate under their Affiliates program for bloggers. More on that in a follow-up post, but let me say for now to my readers, that I'll use the affiliate feature judiciously, so as not to clutter up my blog with too many ads.

I also took a look at the sale site myself. It was interesting to see the variety of books (*) on display (many of which I have bought and read in the past), and also the fact that the O'Reilly book "Learning Python" was among the bestsellers shown.

(*) They do have a large variety and number of books. I have been buying and reading O'Reilly books for many years now, almost from the start of my career, so I've seen that they have books for many of the popular programming languages, such as C, C++, Python, Java, Scala, Perl, Ruby, JavaScript, etc., as well as books on many other programming, system administration, web design and other computer topics.

There are 7000 titles on sale.

This is a good opportunity to pick up some good O'Reilly books at half the cost.

And if you're an author or aspiring author yourself, you may wish to check out my xtopdf toolkit for PDF creation from other file formats. xtopdf includes a few tools for creating PDF ebooks, such as PDFBook.py, which lets you create a PDF ebook from a set of chapters stored in text files, and XMLtoPDFBook.py, which lets you create a PDF ebook from a set of chapters stored in XML format. xtopdf is released as open source software under the BSD License, so it is free for any use, commercial or non-commercial.

Packt Publishing of the UK/India uses xtopdf in their book production workflow, and the Software Freedom Law Center (SFLC) of the USA uses xtopdf for their e-discovery work (as I've been told by people from Packt and SFLC respectively). xtodf is written in Python and uses the open source version of the Reportlab toolkit.

Here is a guide to installing and using xtopdf, which can help you get started with creating PDF books using it.

Here are two posts about XMLtoPDFBook:

Create PDF books with XMLtoPDFBook.

XMLtoPDFBook now supports chapter numbers and names.

---

Read all xtopdf posts on jugad2.

Read all Python posts on jugad2.

---

- Vasudev Ram - Dancing Bison Enterprises

Contact me

Share |

Strawberry Perl for Windows

By Vasudev Ram



Strawberry Perl is free a distribution of Perl for Windkws, that comes with many commonly used modules included, and also lets you download and use at least some Perl XS-based modules (Perl modules that require a C compiler, to be installed), since it comes with a basic setup of the MinGW C oompiler and related tools. (On Linux and most other UNIX variants, this is not a problem, since C compilers and the other needed tools are typically installed by default).

According to the entry for Strawberry Perl on Wikipedia, Larry Wall, original creator of Perl, has used Strawberry Perl and says it is a good port of Perl to Windows. There is a link to a ComputerWorld interview of Larry in which he says that. See page 3 of
that Larry Wall interview.

- Vasudev Ram - Dancing Bison Enterprises

Share |

Camelia, the Perl 6 spokesbug :-)

Perl 6

Seen via a tweet by @jakeasmith.

- Vasudev Ram
Python training and consulting
www.dancingbison.com/about.html

How (not) to defend your dysfunctional programming language

[IWE] Why Lisp macros are cool, a Perl perspective

Interessant  ...

IMO, the post doesn't do a good job of explaining why Lisp macros are useful, at least until the part about setnth or so.

pinger utilities have multiple uses

Python | Host/Device Ping Utility for Windows

Saw the above pinger utility written by Corey Goldberg a while ago. It is in Python and is multi-threaded.

Seeing it reminded me of writing a pinger utility some years ago for a company I worked for at the time; it was for Unix systems, and was not multi-threaded.

It was written in a combination of Perl (for regex usage), shell and C.

The C part (a program that was called from the controlling shell script) was used to overcome an interesting issue: a kind of "drift" in the times at which the ping command would get invoked.

The users wanted it to run exactly on the minute, every n minutes, but it would sometimes run a few seconds later.

I used custom C code to solve the issue.

Later I learned (by reading more docs :) that the issue could probably have been solved by calling a Unix system call or two (like gettimeofday or getitimer, I forget exactly which right now) from my C program.

Anyway, the tool ended up being used to monitor the uptime of many Unix servers at the company. The sysadmins (who had asked me to create the tool) said that it was useful.

As Corey says in his post, pinger tools can be used to monitor network latency, check if hosts / devices are alive, and also to log and report on their uptime over an extended period, for reporting and for taking corrective action (as my utility was used).

Also check out pingdom.com for an example of a business built on these concepts. Site24x7.com is another such business; it is part of the same company as Zoho.com. They were (and still are)  into network monitoring / management before they created the Zoho suite of web apps.

I use both Pingdom and Site24x7 on my business web site www.dancingbison.com, from over a year or more now, to monitor its uptime, and both are fairly good at that.

UNIX means YOU get to choose your tools (*)

http://newcome.wordpress.com/2012/03/06/functional-programming-and-the-death-of-the-unix-way/

See the comment by Jmp on the above post.

(*) And if no tool is _just_ right for the job at hand, UNIX facilitates writing your own (in C, sh, sed/awk/et al, or in Perl, Python, Ruby, or other languages, with great integration and interaction with the OS, the shell and the many powerful command-line tools that are an integral part of UNIX.

Want proof? Just read the book "The UNIX Programming Environment" by Kernighan and Pike, and try out many of the examples in it.

Microsoft to switch back to ODBC from OLE DB, say reports

By Vasudev Ram - dancingbison.com | @vasudevram | jugad2.blogspot.com

Surprising as it may seem, Microsoft may switch back to ODBC from OLE DB.

I read about this a few days ago on the Net.

Here are some relevant links to the news about Microsoft going back to ODBC.

From the Microsoft SQLNCli team blog (I guess SQLNCli stands for SQL Native Client):

Microsoft is Aligning with ODBC for Native Relational Data Access:

http://blogs.msdn.com/b/sqlnativeclient/archive/2011/08/29/microsoft-is-aligning-with-odbc-for-native-relational-data-access.aspx

From the blog of Hal Berenson, former Distinguished Engineer and General Manager, and who, in his own words, "was both a godfather of the OLE DB strategy and responsible for the SQL Server implementations that have now been deprecated":

OLE DB and SQL Server: History, End-Game, and some Microsoft "dirt":

http://hal2020.com/2011/09/25/ole-db-and-sql-server-history-end-game-and-some-microsoft-dirt/

Interesting stuff. I had worked some years ago on a middleware product that involved ODBC - that sat on top of ODBC, actually (*). One of its main goals was to improve the performance of ODBC-based client-server applications. (Another goal was a more programmer-friendly API for application programmers working on client-server projects that used ODBC, in Visual Basic as well as C.) The product was a success, and was deployed in several large client-server projects of the company I worked for at the time.

Also, the Java JDBC API and the Perl and Python DBI API's were probably influenced quite a bit by the architecture / design of ODBC. (This is what I think, based on having studied and worked on both ODBC and JDBC a good amount, and some on the Perl and Python DB APIs). It (ODBC) was a pretty good technology for its time, and was very extensively deployed and used (almost universally, in fact, for client-server database applications), during the heyday of the client-server period of computing - though native database drivers were also used a lot then.

Interesting to see that Microsoft is now moving back to it - presumably, to improved versions of it, suited to today's requirements.

(*) If you are wondering how another software layer on top of ODBC could improve performance of ODBC apps, rather than only make it worse (due to more overhead of the extra layer), think a bit more. It may sound counter-intuitive, but is possible - it actually happened.

Posted via email

- Vasudev Ram @ Dancing Bison