Algorithm puzzles

Posted on November 28, 2006 by pm286

I love algorithms. I’m not good at them, but I think they’re a wonderful expression of human creativity. An algorithm is a formal procedure which – in simple terms – works out the answer to a problem. A good algorithm has few frills, is general and is usually beautiful and can be proved to give the right answer.
So here are two algorithms which I think are beautiful and slightly mystical. Each carries the author’s name. I’m going to leave you to work out what each does. I have created meaningless variables and names so as to give few hints. I have written them in Java, but you should be able to follow them (int means integer;
The original version of the first algorithm (using iteration) (!= means notEqual):

int foo(int a, int b) {
while (a != b) {
if (a > b) {
a = a - b
} else {
b = b - a
}
}
return a
}

“To Iterate is Human, to Recurse, Divine” wrote James O. Coplien of the legendary Bell Labs. Here is the same algorithm using recursion (a mod b means the integer remainder after dividing a by b):

int foo(int a, int b) {
return (b == 0) ? a : foo(b, a mod b)
}

Isn’t that beautiful? Even if you’re not a programmer you can see that it’s very clever to create an algorithm with only one line.
If you don’t recognize this algorithm you can probably work out what it does by running a few trial variables throuh it. But what about this one…

void foo(int c, int d, int e) {
int a = 0;
int b = c;
int sum = 3 - 2 * c;
while(a <= b) {
outputProcedure(a, b, d, e);
if (sum <= 0) {
sum = sum + 4 * a + 6;
} else {
sum = sum + 4 * (a - b) + 10;
b = b - 1;
}
a = a + 1;
}

(* means multiply; <= means lessThanOrEqual).  Here we pass 3 integers (c, d, e) into a routine which runs through a loop and outputs something each time. What does it output? What are c,d,e?
The numbers 2, 3, 4, 6, 10 are fundamental parts of the algorithm – I find this remarkable!
============
PS  If any of you are still struggling with the mystery molecule, the answer is completely contained within http://wwmm.ch.cam.ac.uk/blogs/murrayrust/?p=160 – just save the picture.

This entry was posted in programming for scientists, puzzles. Bookmark the permalink.

8 Responses to Algorithm puzzles

  1. Noel OBoyle says:
    November 29, 2006 at 2:20 pm

    When I got into programming with microcomputers, what was most interesting was drawing things on the screen. Here is a graphical algorithm, whose result I won’t describe:
    (1) Pick three points on the XY plane; let’s call them a, b, and c
    (2) Place a point, p, at one of a, b or c
    (3) Move the point p halfway from its current position to one of a, b, or c (chosen randomly)
    (4) Repeat (3) indefinitely, plotting the point p on the screen
    A good way of learning recursion, and depth-first vs. breadth-first is to:
    (1) Draw a rectangle
    (2) Recursively draw a smaller rectangle at each of the four corners of that rectangle.
    (3) Try doing it depth-first, vs. breadth-first.
    Also, drawing the Mandelbrot fractal with lots of nice colours is a good introduction to manipulating complex numbers.

    Reply
  2. pm286 says:
    November 30, 2006 at 9:19 am

    (1) I haven’t run this so here’s my suggestions. (a) This is not deterministic so there can be no single answer. For example if the the random point is always C, then the point will slowly move to C. If the point is always the next in cyclic order (A,B,C,A,B,C…) then the point will converge (quite rapidly) to the vertices of an included triangle (I cannot work out the sides but I guess they are about 1/3 of the original. For a random distribution I’m guessing the results are similar but the triangle is somewhat larger.

    Reply
  3. Noel OBoyle says:
    November 30, 2006 at 1:59 pm

    I would be *very* impressed if you could figure out the solution without running the program. Try coding it – a picture tells a thousand words. 🙂

    Reply
  4. pm286 says:
    November 30, 2006 at 2:55 pm

    (3) All right. I have to decide yet again what graphics system I should aim for – GTK, Swing, or even SVG.
    My latest guess is a Cantor set of some sort (perhaps a Sierpinski gasket) with an empty triangle in the middle

    Reply
  5. Noel OBoyle says:
    November 30, 2006 at 5:44 pm

    In the old days, this would take 5 minutes on a BBC to code up and run. Even in Windows with Qbasic, it was easy. The barrier is higher now…Python requires an additional module such as PyGame.
    BTW, I *am* impressed 🙂

    Reply
  6. jat45 says:
    November 25, 2007 at 10:15 pm

    I just stumbled across these over the weekend… I am interested to know if there are any mistakes in the last algorithm foo(c, d, e)
    d and e are never altered and don’t have any effect on the behaviour of foo.

    Reply
  7. pm286 says:
    November 26, 2007 at 12:36 am

    (6) I don’t believe there are mistakes – I copied it from Wikipedia. d and e are simply passed to the output routine (whose name would give the game away). They are required in the real world, but are not involved in the algorithm.
    Try running it with different values of c and tabulate a and b.

    Reply

  8. Pingback: Unilever Centre for Molecular Informatics, Cambridge - Staudinger’s Semantic Molecules » Blog Archive » D’oh…..

Leave a Reply

Your email address will not be published. Required fields are marked *