Monday, December 3, 2018

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:


Sunday, December 2, 2018

Bjarne Stroustrup's FAQ

By Vasudev Ram


Bjarne Stroustrup's FAQ

Educational and entertaining.


- Vasudev Ram - Online Python training and consulting

Hit the ground running with my vi quickstart tutorial, vetted by two Windows system administrator friends.

Jump to posts: Python * DLang * xtopdf

Interested in a Python, SQL or Linux course?

Get WP Engine, powerful managed WordPress hosting.

Subscribe to my blog (jugad2.blogspot.com) by email

My ActiveState Code recipes


Follow me on:

* Gumroad  * LinkedIn

  * Twitter

Do you create online products? Get Convertkit:

Email marketing for digital product creators


Tuesday, November 20, 2018

A remote UK community living off-grid

By Vasudev Ram



Saw this via HN:

The remote UK community living off-grid

HN thread about it:

A remote UK community living off-grid (bbc.co.uk)

I commented too, about an earthship that I visited in India.

Here is an article about that earthship:

Earthship Karuna

- 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.

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

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 or want to create online products for sale? Check out ConvertKit, email marketing for online creators.

Own a piece of history: Legendary American Cookware

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

Managed WordPress hosting with Flywheel.

Posts about: Python * DLang * xtopdf

My ActiveState Code recipes

Follow me on:





Tuesday, November 13, 2018

Quick-and-dirty IPC with Python, JSON and pyperclip

By Vasudev Ram



Blue Gene image attribution

Hi, readers,

Some time ago I had written this post.

pyperclip, a cool Python clipboard module


The pyperclip module allows you to programmatically copy/paste text to/from the system clipboard.

Recently, I realized that pyperclip's copy and paste functionality could be used to create a sort of rudimentary IPC (Inter Process Communication) between two Python programs running on the same machine.

So I whipped up a couple of small programs, a sender and a receiver, as a proof of concept of this idea.

Here is the sender, pyperclip_ipc_sender.py:
'''
pyperclip_ipc_sender.py
Purpose: To send JSON data to the clipboard from  
a Python object.
Author: Vasudev Ram
Copyright 2018 Vasudev Ram
Web site: https://vasudevram.github.io
Blog: https://jugad2.blogspot.com
Training: https://jugad2.blogspot.com/p/training.html
Product store: https://gumroad.com/vasudevram
'''

from __future__ import print_function
import pyperclip as ppc
import json
import pprint

def generate_data():
    d = {"North": 1000, "South": 2000, "East": 3000, "West": 4000}
    return d

def send_data(d):
    ppc.copy(json.dumps(d))

def main():
    print("In pyperclip_ipc_sender.py")
    print("Generating data")
    d = generate_data()
    print("data is:")
    pprint.pprint(d)
    print("Copying data to clipboard as JSON")
    send_data(d)

main()
And here is the receiver, pyperclip_ipc_receiver.py:
'''
pyperclip_ipc_receiver.py
Purpose: To receive JSON data from the clipboard into 
a Python object and print it.
Author: Vasudev Ram
Copyright 2018 Vasudev Ram
Web site: https://vasudevram.github.io
Blog: https://jugad2.blogspot.com
Training: https://jugad2.blogspot.com/p/training.html
Product store: https://gumroad.com/vasudevram
'''

from __future__ import print_function
import pyperclip as ppc
import json
import pprint

def receive_data():
    d = json.loads(ppc.paste())
    return d

def main():
    print("In pyperclip_ipc_receiver.py")
    print("Pasting data from clipboard to Python object")
    data = receive_data()
    print("data is:")
    pprint.pprint(data)

main()
First I ran the sender in one command window:
$ python pyperclip_ipc_sender.py
In pyperclip_ipc_sender.py
data is:
{'East': 3000, 'North': 1000, 'South': 2000, 'West': 4000}
Copying data to clipboard as JSON
Then I ran the receiver in another command window:
$ python pyperclip_ipc_receiver.py
In pyperclip_rpc_receiver.py
Pasting data from clipboard to Python object
data is:
{u'East': 3000, u'North': 1000, u'South': 2000, u'West': 4000}
You can see that the receiver has received the same data that was sent by the sender - via the clipboard.

A few points about this technique:

- If you run the receiver without running the sender, or even before running the sender, the receiver will pick up whatever data was last put into the clipboard, either by some other program, or manually by you. For example, if you selected some text in an editor and then pressed Ctrl-C (to copy the selected text to the clipboard), the receiver would get that text (if it was JSON text - see two points below). However, that is not a bug, but a feature :)

- Obviously, this is not meant for production use, due to potential security issues. It's just a toy application as a proof of concept of this idea.

- Since I convert the Python object data to JSON in the sender before copying it to the clipboard with pyperclip, the receiver also expects the data it pastes from the clipboard into a Python object to be of type JSON. So if you instead copy some non-JSON data to the clipboard and then run the receiver, you will get an error. I tried this, and got:

ValueError: No JSON object could be decoded

To handle this gracefully, you can trap the ValueError (and maybe other kinds of exceptions that Python's json library may raise), with a try-except block around the code that pastes the data from the clipboard. You can then either tell the user to try again, or print/log the error and exit, depending on whether the receiver was an interactive or a non-interactive program.

The image at the top of the post is of an IBM Blue Gene supercomputer.

From the Wikipedia article about it:

[ The project created three generations of supercomputers, Blue Gene/L, Blue Gene/P, and Blue Gene/Q. Blue Gene systems have often led the TOP500[1] and Green500[2] rankings of the most powerful and most power efficient supercomputers, respectively. Blue Gene systems have also consistently scored top positions in the Graph500 list.[3] The project was awarded the 2009 National Medal of Technology and Innovation.[4] ]

- 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.

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

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 or want to create online products for sale? Check out ConvertKit, email marketing for online creators.

Own a piece of history: Legendary American Cookware

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

Managed WordPress hosting with Flywheel.

Posts about: Python * DLang * xtopdf

My ActiveState Code recipes

Follow me on:


Saturday, November 10, 2018

VIDEO: The History of Unix, by Rob Pike

By Vasudev Ram


This is a video about Unix history by Rob Pike, Unix veteran and co-creator of the Go programming language.

The History of Unix, Rob Pike

The video is also embedded below.

There is also a current HN thread about it.

- 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.

Here are the course outlines and some client testimonials.

Contact me for more details, terms and schedule.

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

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 or want to create 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: