Maudlin ruminations of a mind bit by wanderlust.

And a shaft of light shall sunder the heavens...

Subscribe to RSS feed

Posts tagged with "python"

The Towers of Hanoi, recursion, and the end of the world.

These are the towers of Hanoi :



The story goes that a bunch of monks in Vietnam were given 3 pegs and 64 golden discs, and had to move all of them from one peg to another, using the third as storage. However, they could never place a larger disc on top of a smaller one. The day they finished their task would be the end of the world, says the legend. That's quite ok with the most of us though, because if we assume that the monks can move one disc in one second, we can show that it will take them 584542046.09062564 millenia or thereabouts to finish the task. So unless they started a reeeally long time ago, the end of the world isn't going to happen any time soon. But that's assuming they know how to go about doing it. We can do better.

Recursion is a great tool for the lazy programmer. If it is easy to state the problem at hand in terms of the problem itself, then recursion is the way forward. Consider, that to solve the problem of hanoi,

-- We want to move all the discs from one peg to another (source to destination, with the other being called storage).
-- We can do this as follows :
-- If there are no discs on a peg, do nothing.
-- Move all but the last disc from the source peg to the storage peg using the destination as storage.
-- Move the last peg from source to destination.
-- Move all the discs you moved earlier to the destination, now that the largest disc is there.

Using this description, we can write :
def transfer(discs, source, destination, storage) :
    # If there is nothing to transfer, do nothing.
    if discs == 0 :
        return

    # Transfer all but the last disc to the temporary storage location
    transfer(discs - 1, source, storage, destination)

    # Transfer the last disc to the destination
    print "Moving disc %d from %s to %s" % (discs, source, destination)

    # Transfer all but the last disc from the temporary storage to the
    # destination
    transfer(discs - 1, storage, destination, source)

def main() :
    n = int(raw_input("Enter the number of discs : "))
    source = 'A'
    destination = 'B'
    storage = 'C'
    transfer(n, source, destination, storage)


Note that we start the process for n discs by calling,

transfer(n, source, destination, storage)


For 3, 4 & 5 discs, the moves are as follows :

(sykora@nexus)(pts/3 | 0 job(s))(Thursday June 14, 2007 : 22:08:54)
(%:python)- python2.5 hanoi.py
Enter the number of discs : 3
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 3 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B

Enter the number of discs : 4
Moving disc 1 from A to C
Moving disc 2 from A to B
Moving disc 1 from C to B
Moving disc 3 from A to C
Moving disc 1 from B to A
Moving disc 2 from B to C
Moving disc 1 from A to C
Moving disc 4 from A to B
Moving disc 1 from C to B
Moving disc 2 from C to A
Moving disc 1 from B to A
Moving disc 3 from C to B
Moving disc 1 from A to C
Moving disc 2 from A to B
Moving disc 1 from C to B

Enter the number of discs : 5
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 3 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B
Moving disc 4 from A to C
Moving disc 1 from B to C
Moving disc 2 from B to A
Moving disc 1 from C to A
Moving disc 3 from B to C
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 5 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B
Moving disc 3 from C to A
Moving disc 1 from B to C
Moving disc 2 from B to A
Moving disc 1 from C to A
Moving disc 4 from C to B
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 3 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B


Forgetting for the moment about the actual moves, and concentrating on the number of moves, we find :
3 : 7
4 : 15
5 : 31
...


Notice a pattern? For 64 discs, the number of steps would be 2**64 - 1, which is 18446744073709551615. Taking this as a number of seconds we get the above mentioned number of millenia if the monks moved a disc a second.

What's the use? I'm told that a major use of this problem is to evalutate the pyschological stability of patients. Yes, that's apart from predicting the end of the world, and teaching recursion.

Playing the 'Guess my number' game recursively

,

This has probably occurred to a lot of you, but I only just realized it, after reading a book on Haskell. I'd never thought of it before.

Most programmers have written their own version of the 'Guess my number' game -- You know, it picks a number, you guess, it says if you're too high or too low, that kind of thing.

What we usually do is this :

def guess(n) :
    while True :
        x = int(raw_input('Enter a number : '))
        if x < n :
            print 'You're too low.'
        if x > n :
            print 'You're too high.'
        if x == n :
            print 'You're absolutely right.'
            return


I'd never realized that it could be done recursively, although it looks pretty obvious. No, it doesn't offer any performance boosts, and no, it doesn't make it easier to read. It's just something different.

def guess(n) :
    x = int(raw_input('Enter a number : '))
    if x < n :
        print 'You're too low.'
        guess(n)
        return
    if x > n :
        print 'You're too high.'
        guess(n)
        return
    if x == n :
        print 'You're absolutely right.'
        return


The usefulness of recursion is not perhaps as apparrent in this case as it usually is, but still...

Java, anyone?

, , , ...

I found this awesome site, which has a number of cool number theoretic projects such as the ECM Factorization Algorithm. The only problem is, the source code for the applet is in java, something I'm not prepared to grapple with yet. If anyone has any expertise with Java Applets, can they please go through it (no mean task), and tell me what the general algorithm is, without the applet part.

There's only one problem - It's 9522 lines long :|

In the meantime, I've been working on a python module for mathematical functions that are a bit higher than the standard library. They're not very fast, as they're written in python, but I'm trying to optimize them as much as possible. One upset I found was that the traditional python idiom for adding large strings : ''.join(huge_list) vs string += string : Is actually losing relevance. Of course I didn't test every possible contingency, but for smaller strings, string addition is faster, while for larger strings, the join idiom is faster.

I also found that most linux distributions come with a console command factor, which outputs the prime factors of a given number. Although it's pretty fast, its algorithm is still fairly primitive.

I'll put my math module (which I've tentatively called imath smile ) up when I've completed a decent amount of it. It's coming out quite well, actually.

Now, back to 9522 lines of java... :|

The Aftermath

, , ,

My exams are over. I did well in almost all of them, except for Electrical Engineering. Blech.

Anyway, now I'm int he market for a new PC, so if any of you have some blockbuster ideas about that, please drop me a line. One specific worry I have is that a particular motherboard that I have been after for some time...simply isn't available. I can't find it anywhere. (In case you're wondering, it's GA-965P-DQ6. There, are you happy now?)

My college reopens on the fourth of july, prosaic for the freedom it gives me. </sarcasm>

On the happier side, I'm back to doing the things I like, like Python and sleeping. I may even get my own webspace. That'll be cool.

Variety

, , , ...

My exams start tomorrow, and end on the 23rd of May. An era will have ended, as I will no longer be subjected to Physics and Chemistry after these exams. Anything I do in these subjects after this will be my own folly.

In other news, I was recently keeping up with the French Presidential elections. I was backing Segolene Royal (Inconsequential, since I can't vote, but still), for the same reason why many people voted for her -- Because I didn't like the other alternative. Being a student, I can sympathize with the student riots in 2005, and can't see my way to elect a president who did tantamount to incite it. Granted, I know almost nothing about any of these issues, but still this is what my gut feeling says.

The Python posts are on hold, because my exam on C is tomorrow. I don't like C. One quote compares a C program to a dance on a waxed dancefloor holding knives. That's pretty much how I feel. In C, you need to think about what you can do practically, and then write a program. In Python, you write a program, with the confidence that you can make it work.

Australia won the World Cup, and the Sri Lankans are in uproar about Adam Gilchrist's keeping a squash ball in his glove. I don't know what to say.

Let the circus begin...

,

Over the last 6 months, and especially in the last month, I have immersed myself in the study of Python (Hence my inactivity, or so I justify it). Because of this, My next few posts will probably be Python related, with this one being an inaugural post of sorts. For anyone who's going or thinking of going into Computer Science or related fields, or even anyone who likes nifty shortcuts to get things done, or anyone geeky enough to use Linux, read on. Even if you don't fit into one of the above categories, maybe I can change your mind.

What is Python?

The Python website says :

Python® is a dynamic object-oriented programming language that can be used for many kinds of software development. It offers strong support for integration with other languages and tools, comes with extensive standard libraries, and can be learned in a few days. Many Python programmers report substantial productivity gains and feel the language encourages the development of higher quality, more maintainable code.



I more or less agree.

Python is arguably one of the most elegant and simplest programming languages in existence. It has very simple syntax, (ie to say, almost none at all), which borders on natural English. Many people have remarked that Python is akin to "executable pseudocode". Because of this, it's very easy to pick up, and lets you concentrate on the logic, rather than grappling with complicated syntax rules. In effect, it's a perfect beginner's language.

But don't think that it's just a beginner's language. Its extensive libraries (more on that later) and exhaustive constructs give it as much functionality as any program would require, and then some. Many mundane/difficult tasks become simpler when using Python.

I'll just give the one example this post, to keep it readable. This is the "Hello World" Program in C++

/* File HelloWorld.cpp */
#include <iostream>

using namespace std;

int main(int argc, char* argv) {
    cout << "Hello World";
    return 0;
}

And to run it, you'd have to do

$ gcc HelloWorld.cpp -o HelloWorld.o
$ ./HelloWorld

on a linux box. Don't ask me for Windows, I hate programming on Windows.

And now for something completely different...

# File HelloWorld.py
print "Hello World!"

and to run,

$ python HelloWorld.py

See the difference? Inevitably, both these programs are the first taught in their respective languages, and yet I'd never want to teach what exactly '#include', 'namespace', and 'int main(int argc, char* argv[])' mean. All I'd want to teach would be the 'print'/'cout' statement, which is exactly what Python asks for.

Biased though I am, I must tell you which are the only 2 inadequacies I've found so far in Python :

  • It's slow compared to other compiled languages. Not that slow, but it becomes noticeable in large programs of the number crunching sort.
  • You must have Python installed on any computer you want to run a Python program on. This is not a problem for linux machines, as most of them have python by default, but can be a minor headache for windows users.


But these aren't that important for many people, and they certainly aren't important for the casual programmer.

One other point worth mentioning about Python is its 'Batteries Included' Policy. This means that when you install Python (all of a 9MB download), you get a huge wealth of standard libraries -- almost all the built-in functions you're ever going to need. There are very few separate downloads I have needed to make to obtain code to use in my programs.

A final note for this post :
The name 'Python' does not come from the class of non-venomous constricting snakes genus pythonidae, but rather from the name of the British comedy troupe Monty Python's Flying Circus and subsequent creations.

Links worth looking at :

The KlueLESS Pythonist.

, , , ...

You know about me and Klueless. I don't know if you know about me and python, but if you don't, know it now.

The Python Challenge is a riddle similar to Klueless (Perhaps such a format is standard for all internet riddles), but requires programming knowledge in Python. It was launched in May 2005 (which means I just found out about it) and has 33 levels. The challenge helps you find your way through the nooks and crannies of all the amazing modules included with python, features you didn't know were there and can almost certainly find a use for in the future. It's as addictive as klueLESS is/was, although you need to know python first.

For those who are KlueLESS wink as to what Python is, it's a very simple and elegant language that rids you of syntax problems so you can concentrate on the important stuff. Python is an awesome programming language which I'm definitely going to blog about in the near future. It's very easy to learn, and very soon you'll start applying it to problems you have everyday.

NB, About the challenge : You can do the problems in a language other than python (I considered doing some in C++ because I was lazy) but in the end you'll find that python was simpler, faster and more elegant. Besides, it's against the spirit of the game (And all the hints are in python code wink).

Go try it out, and tell me what you think.
February 2012
S M T W T F S
January 2012March 2012
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29