Why Not Python?, Part 1

Follow along as an old C hacker drags himself into the late 1990s.

Editor's Note: This article has been updated since its original publication.

It's been 20 years or more since I wrote my first few hundred lines of code in C, so it's about time I learned a more modern language, maybe something object oriented. But what?

One of the great things about running free software is a lot of programming languages are included on the installation media. It's like in the good old days. Back then if you bought, say, an HP 3000, you got Fortran, SPL/3000, a linker, a debugger and printed manuals, not to mention support for shared libraries since 1972. But I digress.

Today, if you buy a proprietary system and want to program it in, say, ANSI C, you might have to shell out hundreds or even thousands of dollars for some vendor's compiler. That's the case unless you can find free software, such as the GNU compiler collection (GCC), ported to your particular platform.

Now, in the good new days, I have C, C++, Ruby, Perl, Python, Pascal and Fortran 77 on my SuSE 8.0 CDs. I also have Tcl, Scheme, Smalltalk, Modula-2, Forth, Prolog, REXX, LISP, Ada95 and so on.

So a couple of years ago, when my teenage daughter became interested in programming, we worked out a few "toy" programs in Python. I had heard it would be a better choice than Perl for a first language. Python is current, it has object-oriented features, books are available for it and I'd seen some recent articles praising it. So I decided to give it a whirl on something a little bigger. I'll share that journey with you in Part 2 of this article, but for now I thought I'd revisit our answers to the Coconuts problem.

This problem, which appeared in a short story by Ben Ames Williams, concerns five men on a deserted island who gather a pile of coconuts. During the night, one of the men wakes up and decides to take his share in advance. He divides the coconuts into five equal piles. One coconut is left over, and he tosses it to a nearby monkey. Hiding his pile and consolidating the four remaining piles, he returns to sleep.

The second man does the same thing, dividing the now slightly smaller pile into five equal ones, tossing the one leftover coconut to the monkey, hiding his pile and returning to sleep. The third, fourth and fifth man all repeat the same pattern.

When all awake in the morning, the pile looks smaller, but each man is as guilty as the others, so no one says anything. They divide the remaining coconuts into five equal piles as the monkey watches. This time, though, there are no coconuts left over.

How many coconuts did they start with?

I remembered that the answer was less than 100,000, so what we needed was a program that did this:

  • A. run steps B-G with origPile in the range of 5 to about 100,000

  • B. set tempPile = origPile

  • C. do steps D-E five times, i.e., once for each man

  • D. if (tempPile mod 5) isn't 1, try a new value of origPile, that is, don't do E-G)

  • E. set tempPile to 4/5 of (tempPile-1)

  • F. if (tempPile mod 5) isn't zero, try a new value of origPile, that is, don't do G)

  • G. print the value of origPile, and exit the A-G loop

Or, pictorially, the program needed to do this:

The Coconuts Program in the Language of the 1980s

Back in the day, to implement the program I outline above, I coded the following in C:


    1   main()
    2   {
    3      int origPile, tempPile, man;
    4      for (origPile=5; origPile<99999; ++origPile) {   //A
    5          tempPile = origPile;                         //B
    6          for (man=0; man<5; ++man) {                  //C
    7              if ((tempPile%5) != 1) goto foo;         //D
    8              tempPile = (tempPile-1) * 4 / 5;         //E
    9          }
   10          if (tempPile%5) continue;                    //F
   11          printf("Victory! %d\n", origPile);           //G
   12          break;
   13   foo:
   14      }
   15   }

Here's a brief description of the C program; you can skip this if you like. Lines 1-2 are simply C boilerplate, so the compiler knows what you want to run as your main program.

Line 3 is a declaration; that is, we declare that origPile, tempPile, and man all are variables of type "int", a subset of integer.

Line 4 is essentially step A in the summary. It tells the compiler that we want to execute some statements--until the matching } in line 14--with origPile in the range of 5 up to but not including 99,999. Don't worry if the syntax isn't obvious to you; we're really here to talk about Python, not C, but this is just an illustration.

Line 5 does step B in the summary. That was easy!

Line 6 does step C, which tells the compiler we want to execute a loop--until the matching } in line 9--five times, with "man" taking on values 0, 1, 2, 3 and 4.

Line 7 does step D. It tells the compiler we want to jump to the label foo: if there isn't exactly one left over after dividing tempPile by five. In Perl, you could say:


    next OuterLoop unless ($tempPile%5 == 1);

In a bash(1) script, you could continue 2, but in C, goto probably is the easiest way to implement this step.

In line 10 it says to try a new value of origPile if tempPile doesn't divide evenly into five piles in the morning. That is essentially step F. Lines 11-12 do step G.

So basically, the program should work. Does it?


    % make c0
    cc     c0.c   -o c0
    % ./c0
    Victory! 3121
    %

Did the program return a good answer? Suppose the group of five start with 3,121 coconuts, as the program says. The first man divides 3,121 coconuts into five piles of 624 each, with one left over. He gives the leftover to the monkey, hides 624 and goes back to bed. 3,121-1-624 = 2,496.

The second man divides 2,496 coconuts into five piles of 499 each, with the one leftover going to the monkey. He hides 499. 2,496-1-499 = 1,996.

The third man divides 1,996 coconuts into five piles of 399, plus one leftover for the monkey. He hides 399. 1,996-1-399 = 1,596.

The fourth man divides 1,596 coconuts into five piles of 319 each, with one going to the monkey and hides 319. 1,596-1-319 = 1,276.

The fifth man divides 1,276 coconuts into five piles of 255 each and has one left over for the monkey. He hides 255. 1,276-1-255 = 1,020.

In the morning, 1,020 coconuts are left. These are divided into five piles of 204 each. So the program gave a reasonable answer.

The Coconuts Program in Python

How could I go about writing a similar program in Python? Looking at some examples in Learning Python, (Mark Lutz and David Ascher, O'Reilly 1999), the first thing I noticed was there are no declarations. That is, we don't say int origPile, we simply start using a name.

As in a Perl or shell script, the first use of a name brings its variable into existence. We also don't have to say main(). Python thinks you're in main from the first executable statement. Therefore, the basic Python loop is easier to write than is the basic C iteration loop. Instead of writing:


    for (origPile=5; origPile<99999; ++origPile) {

you write:


    for origPile in range(5,99999):

That can be line 1. For the rest, how about using this:


    1   for origPile in range(5,99999):             #A
    2      tempPile = origPile                      #B
    3      for man in range(5):                     #C
    4         if tempPile%5 != 1: break             #D
    5         tempPile = (tempPile-1) * 4 / 5;      #E
    6      else:                                    #if you didn't "break"
    7         if tempPile%5 != 0: continue          #F
    8         print "Victory!", origPile            #G
    9         break

Here are a few more differences: instead of using { curly braces } to show the range of a block--a loop or whatever--you use indentation. You don't need semicolons at the end of every statement, although I did slip and toss in a useless one in line 5. Python didn't object. Comments are signaled with # rather than // or /* */ .

Python doesn't have a "goto" statement, but in this case I didn't need it. The "else" after a loop is if you never execute break.

Make sense? Okay, let's call that code c0.py and run it:


    % python c0.py
    Victory! 3121
    % 

That sure was easy! You don't have to be a genius to write working Python code immediately.

Here is what my daughter wrote (I added the comments):


    1   import sys
    2   MoreCoconuts ="Whatever"
    3   
    4   for Coconuts in range(5,99999):                 #A
    5       Pile=Coconuts                               #B
    6       try:
    7           for dummy in range(0,5):                #C
    8               if (Pile%5)!=1: raise MoreCoconuts  #D
    9               Pile=(Pile-1)/5*4                   #E
   10           if Pile%5==0:                           #F (skip G if nonzero)
   11               print "Victory! "+`Coconuts`        #G
   12               sys.exit()
   13   
   14       except MoreCoconuts:
   15           continue

(I might have helped her a little with this.)

Because we want to call the system's exit routine in line 12, we have to say import sys. When a Python program wants to access that system call, it needs a Python module that knows how to do that. In hindsight, line 12 also could have been coded simply as break, which would have been fine. Then, we wouldn't need the "import sys" in line 1. But there are times when sys.exit(), which terminates the whole program, is just what you need.

The try/except construction may be familiar to C++ programmers. The basic idea is that anywhere in the "try" block, you can "raise" an exception, which is caught in the "except" block. Uncaught exceptions go to the next enclosing "try". If uncaught there, they propagate to the Python runtime system, which typically terminates your program.

Line 8 says that if the pile of coconuts doesn't have exactly one leftover when it is divided into the five smaller piles, we need to abandon this theory (or this "try") and try again with more coconuts.

Line 10 could also have been coded this way:


    if Pile%5 != 0: raise MoreCoconuts

As in Perl, there's more than one way to do it in Python.

So we've seen a few C/Python differences in action on a toy program. In Part 2, I'll show you a program to solve the Sudoku puzzle.

Collin Park works for Network Appliance, where he uses Linux on his desktop and laptop computers. He does data recovery and other Linux-related stuff at home, where he lives with his wife and their two teenage daughters. All use Linux to meet their computing needs.

______________________

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Very impressive list of comments

OldAl's picture

What an impressive collection of comments! I wish I knew more about the number theory, but being ignorant of it, I have only a small observation to add.

Your first listing of the "coconuts" program in Python has one superfluous line, namely line 7. I quote your program below with the line 7 commented out. The result with this line commented out is exactly the same as the original. Would I have known that before the code was written? Unfortunately, no way!
(start of quote:)
That can be line 1. For the rest, how about using this:

1 for origPile in range(5,99999): #A
2 tempPile = origPile #B
3 for man in range(5): #C
4 if tempPile%5 != 1: break #D
5 tempPile = (tempPile-1) * 4 / 5; #E
6 else: #if you didn't "break"
7#### if tempPile%5 != 0: continue #F
8 print "Victory!", origPile #G
9 break
(end of quote)

Regards, OldAl.

Not so fast...

amv's picture

OldAl,

Line 7 can be considered superfluous only if you want to solve for the smallest original pile that will satisfy the conditions of the problem. However, that solution is not unique - you can verify this if you comment out line 9 and leave line 7 intact, as per the author. The output will be as follows:

Victory! 3121
Victory! 18746
Victory! 34371
Victory! 49996
Victory! 65621
Victory! 81246
Victory! 96871

In fact, if you increase the upper bound of the main loop, you will see more solutions, all of which are perfectly valid.

amv

Why Not Python?, Part 1

walter kehowski's picture

Next lesson in Python: Modify the program not to just stop at the first solution but keep a list of solutions and you will observe that they form the arithmetic sequence 3121+3125*j, j>=0. Now to justify it. Assume the solution x0=3121 has been found. [Don't have a proof on the tips of my fingers. Any gunslingers with a clean one?] Define the map f := x -> 4/5*(x-1) and let f@k denote the kth iterate of f. Then it is easy to see that (f@k)(x0+d*j)=(f@k)(x0)+(4/5)^k*d*j for arbitrary k>=0. For k=5 we require that (4/5)^5*d be an integer so d=5^5=3125 is the smallest choice.

close, but not quite

Anonymous's picture

You skipped a factor of 5. Note that after 5 iterations of 4/5*(x-1), the result still has to be divisible by 5. If you start with 3121+3125=6246, the sequence is 4996, 3996, 3196, 2556, 2044. The 2044 coconuts left in the morning is not divisible by 5.

The proper increment is 5^6=15625. The following fragment finds all answers less than 100,000:

result = []
N=1
while 1:
    M = 15625*N+8404
    if M%1024==0: result.append(M/1024)
    if M>100000*1024: break
    N += 1
print result

(The test for (15625*N+8404)/1024 an integer is a result of unrolling the loop. N is the share each sneaky bastard gets in the morning.)

This yields
[3121, 18746, 34371, 49996, 65621, 81246, 96871]
and
>>> [result[x+1] - result[x] for x in range(len(result)-1)]
[15625, 15625, 15625, 15625, 15625, 15625]

i.e. the increment is indeed 15625.

If you only want the first solution

for M in range(0,100000):
    if (1024*M-8404)%15625==0: break
print M

is the shortest legible code I've come up with, but it's not very
useful, pedagogically. FORTH partisans note this could be formatted as only two lines.

function

Anonymous's picture


>>> def coconuts(ceil=100000):print [M for M in range(0,ceil) if (1024*M-8404)%15625==0]
...
>>> coconuts(1000000)
[3121, 18746, 34371, 49996, 65621, 81246, 96871, 112496, 128121, 143746, 159371, 174996, 190621, 206246, 221871, 237496, 253121, 268746, 284371, 299996, 315621, 331246, 346871, 362496, 378121, 393746, 409371, 424996, 440621, 456246, 471871, 487496, 503121, 518746, 534371, 549996, 565621, 581246, 596871, 612496, 628121, 643746, 659371, 674996, 690621, 706246, 721871, 737496, 753121, 768746, 784371, 799996, 815621, 831246, 846871, 862496, 878121, 893746, 909371, 924996, 940621, 956246, 971871, 987496]

*the function could also be defined using a "controversial" lambda statement:
coconuts = lambda ceil=100000:[M for M in range(0,ceil) if (1024*M-8404)%15625==0]

Function II

PabloZ's picture

A kind of optimization, using a generator (needs a rather recent version of Python).


>>> g = (M for M in count() if (1024*M-8404)%15625==0)
>>> g.next()
3121
>>> g.next()
18746
>>> g.next()
34371
>>> g.next()

Wrapping it in a function (or a lambda) is simple:


>>> coconuts = lambda items, g=(M for M in count() if (1024*M-8404)%15625==0):[g.next() for i in range(items)]
>>> coconuts(10)
[3121, 18746, 34371, 49996, 65621, 81246, 96871, 112496, 128121, 143746]

import

PabloZ's picture

Sorry, I forgot an important line in the code above...


from itertools import count

You can also notice what

chuck's picture

You can also notice what happens if you start with -4 coconuts. Give one to the monkey, -5 coconuts. Divide into 5 piles of -1 coconuts each and take one pile away, -4 coconuts left, i.e., it repeats. Add 5**5 to this and run the monkey business, then in the morning there are 4**5 - 1 coconuts, which is divisible by 5 since it is (-1)**5 - 4 = -5 mod(5). OK, that might not be the most obvious approach, but it works.

Using exceptions for program

Anonymous's picture

Using exceptions for program flow control is just pure blasphemy.

Not blasphemy, but bad programming

Anonymous's picture

Blasphemy is too strong a word, but it's certainly bad programming. I found this page by following a link in the Daily Python summary; I have to say that it makes me nervous that a technical magazine would promulgate this practice.

Exceptions should be used for exceptional situations. Something that won't happen in 999 runs of the program, but something you must handle when it occurs.

Finding an answer, or eliminating a candidate answer, are not exceptions; they are the expected events of running the code.

against whom?

Anonymous's picture

There's nothing wrong with exceptions, so long as they are implemented efficiently, and in Python, they are pretty good.

I would rather assert that using "goto" for flow control (or at all), as in the C example, is a blasphemy against Edsger W. Dijkstra's teachings...

blasphemy

Anonymous's picture

Against whom?

Python is great!!!

Anonymous's picture

I have been programming for the last 20 years or so and I had the possibility to work with many different programming languages. Just to name a few: Z80/x86 assembler, C99, C++, Objective C, D, Perl, ADA, guru, lisp, java, C#, ruby, javascript "shells", (Quick/Visual/Star)Basic, and Python of course.
Not to say there are not other great languages but Python has always beeing the most "sexy" language for me.
I think the secret of Python is that it takes complex structures like dictionaries (hash tables), tuples or lists as standard types and put lot of effort in doing its sintax intuitive so something really complex in Java or C or C#,... like a "dictionary whose keys are (tuples of tuples) and whose values are lists whose first element is another dictionary and second element is a tuple of functions and can have n elements more" is a matter of minutes in Python. To say the true I have never ever tried to do such same thing with C or Java and doing it with other more friendly languages like JavaScript or Ruby is hard.

Now I use Python for nearly everything and just change when an "speciallized" language makes things even easier: SQL for database access or R (r-project.org) for data mining processes.

Python is a great 2nd

Anonymous's picture

Python is a great 2nd language.
I've successfully used python for projects at Motorola, 3Com, and other companies.
I came from a C and assembler background, and chose python over perl, tcl/tk and others for my scripting needs.
No language is perfect for everything, but in an hour I can do almost anything I need in python.
Example: I spent only 1 day coding a network monitoring command which was distributed to our telco customers. I developed in python using activestate on a windows laptop, sent the compiled bytecodes to a solaris box, which ran the tool. When testing with the customer, I could add requested improvements (like a timestamp) in 10 minutes start to finish.
With internet access for code searching, Oreilly python pocket reference, and the included library reference I can do anything I want.

Don't bother...

Anonymous's picture

From one old C hacker to another... don't bother dragging yourself into the mess of modern languages. These newbies have no idea about why things were done the old way, and have reinvented the wheel to no purpose.

If you want to update your language skills, then keep the benefit of what you know about programming and use Objective C with either Cocoa or GNUstep. It has the juicy goodness (and inefficiency) of object orientated coding, without throwing the baby out with the bathwater.

All depends on what you are doing...

Anonymous's picture

If you've been programming in c for 30 years, let's hope you are a pretty good c programmer. The problem is, for every good c programmer out there, there are dozens of crappy ones.

If you want to exercise the reasons to use a modern language, don't choose number manipulation. Iterating between 1 and a million just hasn't evolved that much in the last 30 years. (Perhaps it was just fine before, eh?)

Doing something that forces you to use pointers as a c programmer is a much more appropriate comparison. Wasting time dealing with pointers (and most specifically pointer bugs!) is a significant waste of time with c. People complain that garbage collection is slow or a waste of space, etc. It is mostly fiction at this point. The difference in performance for desktop (or even server performance) is probably not something that a user will ever notice. Yet at the same time, the effect on programming efficiency is significant.

While we are at it, consider concepts like metaprogramming, closures, and continuations. They may be able to be replicated in a library, but the average c programmer wouldn't consider them because they aren't part of the mindset you use when programming in c. People starting in other languages (not necessarily newer ones, but just other ones) learn these concepts and apply them every day to their work.

C certainly has its place and it is an extremely useful tool in a number of situations, but let's not go so far to think that the only tool we need is a hammer. I have no plans on using it to implement the backend of a web site any time soon.

Hah!

Anonymous's picture

Well, okay. You can program your memory-starved PDA or mobile phone app in assembler if infinitesimal control and efficiency is that important to you. In the mean-time, I'll be writing my next multi-user financial web aplication in a high-level language, thanks very much. The time and money I save on using existing libraries and data structures will more than make up for any "control" I've lost.

Absolutely...

old school's picture

I couldn't agree more.

In fact instead of the "mess of modern languages" you might as well say the mess of "languages" in general.

Before C, we all knew what programming meant. It meant writing in assembler, as I prefer to do for all my own projects. With assembler, you really know what your code is doing. If you want a for loop, you build a for loop from JMP statements. Why would you want a language getting between you and the machine? People who were weaned on C, and have never done a significant app in assembler (not just an exercise), have sort of isolated themselves from real programming in my opinion.

For the same reasons we should generally prefer C to python, we generally should prefer assembler to C. Doesn't that just say it all?

Well, I still use punch-card

Anonymous's picture

Well, I still use punch-card machines and abbacusses...
Heh, why do we need those newbies reinventing the wheel..?

Youth today, so lazy with

Anonymous's picture

Youth today, so lazy with your abacuses. I just use a pile of rocks and move them from one to pile to another.

A "computer upgrade" is simply finding lighter rocks.

Rocks?

Anonymous's picture

Rocks?! You had rocks? We used to dreeeeeaaam of rocks.

First liar never stands a

GreatWhiteDork's picture

First liar never stands a chance. :) We didn't have dreams or sleep.

Well said.

Anonymous's picture

It's been a while but I did try Python. For my purposes it's "advantages" were not compelling enough to make me want to learn to write and maintain two languages. I didn't see where it was all that easy to use. Hard programs are hard to write. The language is relatively small part of the effort. One thing that made Python interesting to me was the cross-platform capability. But I understand that C interpreters exist. If they work well that could solve the cross platform problem. I also didn't understand the advantage of being able to type commands in on the command line. At not not for programs of any significant size. Once you've typed in series a series of trial and error commands at the command line and finally arive at something that works, how do you recall what you typed in? Also, I seem to recall that Python was only useful for GPL projects. Since there's no compiled executable you have to give your source away. (Maybe I'm wrong about that, I don't recall how that works.)
xyz

Python source giveaway

Ken Roberts's picture

Actually, you have several options:
- Distribute the *.pyc (precompiled) / *.pyo (python object) files
- Run the py2c program to convert python source to C
- Run the python compiler program (sorry, can't remember which one this is yet) to convert to an executable

Just because Python itself is open source does not mean what you code must be open source as well.

Too many people have misconceptions about what can/cannot be done with open source TOOLS.

Not to mention the misconceptions about open FORMATS and open SOURCE.

Python is under a GPL

Anonymous's picture

Python is under a GPL compatible license, but you can release your own code under whatever license you like.

As for coding from the command line, the python shell keeps a history of the commands you've typed much like the bash shell so you can use the up arrow to scroll through your previous commands, or use the Ctrl+R command to search for commands you previously issued in a given session. You can even put breaks in your programs pretty trivially that allow you to drop into a shell and examine/manipulate the state of your objects at arbitrary points in your program.

That's all gravy to me though - the thing I like most about python is that the required indentation pretty much requires other users to write readable code, and when I have to maintain someone else's code I'd rather work with Python than Perl for instance any day.

C program

Anonymous's picture

The identifier five on line 6 of the C program is undefined. Also, I'm getting the error 'label at end of compound statement' on line 13.

re: C program

collin's picture

The five is now fixed. Thanks for catching that!

About line 13: gcc 2.95.3 doesn't mind the construct (not even a warning); gcc 3.2.3 throws a warning; gcc 4.0.0 treats it as an error.

Thanks for your comment.

This works...

Anonymous's picture

Adding a semicolon after the label foo fixes the 'label at end of compound statement' error.

foo:;

Why a page of Python when 3 lines of Forth will do?

Hans Bezemer's picture

: men 5 0 do dup 5 mod 1 <> if drop 6 leave else 1- 4 * 5 / then loop ;
: coconuts 10000 5 do i men 5 mod 0= if ." Victory! " i . cr leave then loop ;
coconuts

It probably could have been even shorter and better, but I was in a hurry. No variables, no exceptions.. Eat your heart out..!

Hans Bezemer

1 line of python will do...

Anonymous's picture


filter(lambda x: (1024*x-8404)%15625==0, range(1,100000))[0]

but it's not legible, efficient, or educational. Brevity is not necessarily a virtue.

God Save the Queen

Michael Carter's picture

Thats got to be about the most unintelligble god-forsaken mess that I've ever seen in response to such a straight-forward problem.

how long untill...

Nubis's picture

...Someone starts a contest about solving this problem in lesser characters using any lenguage.

Chaitin's Elegant program: algorithmic complexity

HernanOlivera's picture

Solving a program in lesser characters is similar to the Gregory Chaitin's definition of elegant program: the shortest program that solve the problem. And there is a constant factor in size that is code-dependent. Maybe the lenght in characters is affected by language minimal reserved words. It´s possible to think about other metrics for the code, as primitives used or something else.

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState