The Programming Game

When I was learning my first programming language (Fortran 95) two or three years ago, the students in my class had a fun little game; to see who could solve the problem in the fewest number of lines of code! It was an extremely good way of learning how to make programs more efficient, but it was a somewhat bad way of learning to comment code and make it clear.

Fast forward to 2013 and the Facebook group I started to support people learning and coding in Fortran at my University turned up an interesting example of the efficiency game;

Just solved the last ‘extra’ exercise on Paul Stevenson‘s tutorial in 14 lines of code without any new functions or KINDs. Do I win a prize?

The “extra exercise” refers to a set of problems which aren’t necessary to complete the course, but can be done for the student’s entertainment. The particular problem is quite simple, and is meant to simply give the student experience in the KIND statement and intrinsic function in Fortran 95. However, this serves as a perfect example of how success in computing does not solely rely on your efficiency at coding! Another important lesson is the simplification of your problems into a form which a computer will find easy to solve.

The problem is simple: Calculate the probability  that in a class of 30, two or more people share the same birthday. It’s a classic problem in probability, and the equation typically used as a solution is;

P = 1 – ( n! / ( (n-c)! n^c ) )

Where is the number of days in a year and c is the number of classmates. The stumbling block for a very simple calculation is that the program cannot normally handle such huge numbers as 365! ( = 1x2x3x…x364x365). It’s a massive number which can’t be handled by the normal protocol which is used in a standard Fortran compiler. One way to solve the problem is to force the compiler to allocate more space to the number so that it can be calculated. However, that’s not the only way of solving the problem.

What this clever chap Adam decided to do was to simplify the term with the n! in it. If you can remove the need to make that calculation, the program becomes trivial. So that’s what he did! You can simplify the formula by realising that n! and (n-c)! simplify to the product of the numbers from (n-c+1) to n. With that, it’s fairly easy to produce a DO loop which makes that calculation;

DO i=(n-c+1),n

product=product*i

END DO

P = 1 – product * n^-c

However, this is still an inefficient solution because 365^30 is still a massive number. Here’s another simplification which he used; since you multiply c times in the loop, and you have n^-c on the outside, you can collapse one of the n‘s in that term into each iteration of the loop! The line product=product*i goes to product=product*i/n. However, you can simplify it further by removing the need to have that ugly set of calculations in the DO statement.

Once you realise that the loop makes a substitution for i=(n-c+i), you can rewrite the inside of the loop with that substitution and remove it from the loop statement. With the two changes combined;

DO i=1,c

product=product*(1-(c-i)/n) !simplified

END DO

P = 1 – product

Doesn’t that look a lot nicer? I think it does. But there’s one more thing you can do to make it even easier. When you remember that the action taken here is multiplication, you know it can be done in any order! Which means that you don’t have to start at (c-i), rather you can start at c-(c-i) and work up to c. Since c-(c-i) simplifies to i, you can write;

DO i=1,(c-1)

product=product*(1-i/n) !simplified further

END DO

P = 1 – product

So all it takes is some creative thinking to make your complicated KIND statements disappear! The program was reduced to 14 lines in it’s entirety, so well done Adam.

Finally, if you want to half the number of lines again, try using Matlab. This is the code I made to check it, in it’s entirety;

n=365;
c=30;
cumulative=1;
for i=1:(c-1)
cumulative=cumulative*(1-(i/n));
end
P1=1-cumulative

Without even trying to minimize code length! 7 lines.

So that’s one of the things that I think people forget when they see someone solve a computing problem really easily; often, it takes intuitive leaps to see where the bit is which makes it difficult for you. Once you remedy that, your programming is often a lot faster. (and you can win code length competitions with your friends!)

Disclaimer: after adopting Matlab on my home PC, I haven’t written a full program in Fortran at all. I’m a bit rusty, so please don’t beat me up about the syntax!
Advertisements

About stoove

A physicist, researcher, and gamesman. Likes to think about the mathematics and mechanics behind all sorts of different things, and writing up the thoughts for you to read. A competent programmer, enjoys public speaking and mechanical keyboards. Has opinions which might even change from time to time.
This entry was posted in General Science, Maths and tagged , , , , , , , , , . Bookmark the permalink.

One Response to The Programming Game

  1. Here’s a shorter Fortran solution, at 5 lines for a complete program with I/O:

    program birthdays
    write(6,*) 'input number of people in the class :' ; read(5,*) c
    x=exp(log_gamma(366.0)-log_gamma(365.0-c+1.0)-c*log(365.0))
    write(6,*) 'probability of two birthdays on same day is ',1-x
    end program birthdays
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s