How to calculate the circumference of a circle (without knowing pi)

Some time ago I posted the following little challenge to www.reddit.com/r/programming:

Dear Proggit: Imagine that you must devise a method to calculate the circumference of a circle of any radius. The catch? You are unaware of the existence of Pi.

The other catch? You must begin right now. You may use only what tools you have in front of you (text editor, calculator, pencil and paper with compass(!)), without looking anything up. That means no Google searches, no Wikipedia, no formulas in a book, nothing.

Once you have devised a method, please write a small program in the language of your choice that performs the calculation (the more accurate, the better). Bonus points will be awarded for brevity, cleverness, etc.

I will post my little solution sometime tomorrow. Enjoy!

One final note: If you are a total geometry/math wizard who thinks this is lame, please refrain from posting; I want this to be a fun problem for those of us who will get something out of it.

Below is my method for calculating (or rather, estimating) the circumference of a circle without using pi. This method involves summing the lengths of the hypotenuses of smaller and smaller triangles, as shown in the diagram above.

Begin by cutting the given circle into quarters. Using the radius r, find the hypotenuse of triangle A using Pythagoras’ method. Cut the hypotenuse in half; using that, and the radius, you can calculate the length of line segment Q. Subtract Q from r, and you have the length of line segment P, which is one side of the right triangle B. That, combined with half the hypotenuse of A, will allow you to calculate the hypotenuse of B. Continue, calculating the hypotenuses of smaller and smaller triangles. Sum as many lengths as are required to cover the quarter-circle arc, and multiply by 4 (or multiply the current length by 2^(n*+1), where *n is the number of iterations of the method you’ve performed).

Below I’ve provided an implementation in Perl. Note that the Perl interpreter doesn’t optimize away recursive function calls (that I know of), so you could in theory blow up the stack. In practice, it only takes a few iterations to arrive at a reasonable estimate, so it’s not a problem.

```#!/usr/bin/env perl

use strict;
use warnings;
use autodie;
use Math::Trig ':pi';

my \$iterations = 0;

sub main {
my (\$radius, \$a, \$b) = @_;
my \$hyp = hypotenuse(\$a, \$b);
\$iterations++;
die "Current hypotenuse is \$hyp after \$iterations iterations\n"
. "Estimated circumference: " . \$hyp * (2**(\$iterations+1)) . "\n"
. "Actual circumference: " . (\$radius*2) * pi . "\n"
if \$iterations == \$maxiter;
}

sub hypotenuse {
my (\$a, \$b) = @_;
return sqrt(\$a**2 + \$b**2);
}

```

As you can see, we pretty much mirror the textual description given above, but in code. We then compare our work to the “real” value of pi using the Perl core’s `Math::Trig` constant. Save the above into a file named circ.pl, and you can run it like so:

mel@foo:~\$ ./circ.pl 4 12 # Given a radius of 4, run through 12 iterations
Current hypotenuse is 0.00306796150057116 after 12 iterations
Estimated circumference: 25.132740612679
Actual circumference: 25.1327412287183

I might not want to try to calculate planetary orbits using this kind of rough estimation, but for 99% of real-world cases, it’s good enough.

Preamble

For a long time now, I’ve been looking to make my life more Lispy. As part of that transformation, I’ve begun porting some of my little Perl scripts over to Guile Scheme. Today I’m going to walk through a script that renames my files in a nice, *nix-friendly fashion. For example, if I download a file that someone has erroneously (if good-naturedly) called “My Cool Data.tar.gz”, this script will rename it to “my-cool-data.tar.gz”.

A note on filename style: I’ve never liked the common practice of naming files using underscores (`_’), so I use hyphens instead (`-‘). It’s more Lispy! Also, regular expressions usually recognize the underscore character as part of a word, such that `my_cool_data’ is considered one word, whereas `my-cool-data’ will be treated as three, and the latter is almost always what I’d prefer (since those are, in fact, three words).

Ok. So what about Guile then? It’s an R5RS-compatible scheme, so you get all of that goodness. If you’re an Emacs user, check out Geiser, which turns Emacs into an AWESOME Scheme hacking environment. You don’t need to be an Emacs weirdo like me to write programs in Guile, however. Vim works very nicely, as a matter of fact, and it also highlights Scheme source code beautifully.

Finally, not that it matters that much, but this short essay is also a literate program, thanks to Orgmode (a.k.a. “The Teal Unicorn”). Fun!

Just like any other *nix script, we need to declare a path to our interpreter, as well as any arguments to the interpreter itself. In Guile’s case, there are two things to notice: (1) The `guile` executable must be passed the `-s` argument to execute in script-mode, and (2) The opening `#!` in the interpreter path must be matched by a closing `!#` due to the way Scheme works (or at least, this particular Scheme).

Next, we declare the modules we’d like to use. In this case, it’s just the one: `ice-9 regex`. Please don’t ask me what the `ice-9` part means, but Guile has a whole bunch of functionality under the `ice-9` umbrella, such as regular expression support (which we’re using here), POSIX-related stuff, a `getopt-long` library, and more. For details see [the fine manual]. Or just type “C-h i C-s guile” as \$DEITY intended.

```#!/usr/local/bin/guile -s
!#

(use-modules (ice-9 regex))

```

Defining the `main` procedure

We’re ready to start writing our actual program! Because we’re exciting and creative folk, we’ll call our single procedure `main`.

We’ll go ahead and use a `let` statement to grab all but the first element of the `program-arguments` list and stick it in the `args` variable for brevity (the first element is the name of the executable file). This use of `let` isn’t really required in such a simple program, but I find that it makes things easier to read, and if I expand the program later, it’s easier to modify.

```(define (main)
(let ((args (cdr (program-arguments))))
```

We can’t just assume that the `args` list is going to have anything in it, however, so we’ll print a short message and exit the program if it’s empty. If it’s not empty, we travel on to the `else’ clause of the `if` expression.

```(if (null? args)
(begin (display "No arguments, exiting...")
(newline)
(exit))
```

Now that we’ve invoked the interpreter with the right incantations, loaded our required module, and checked the program arguments list to make sure that we have something there to process, we can write the part of the program that actually does something. Sweet!

In the `else’ clause of the `if` expression, we iterate over `args` using the `for-each` procedure. We use `for-each` in this case (rather than our beloved `map`) because we don’t want to build a new list by transforming each element of `args`, we just want to iterate over our list being all “side-effect-y” (a technical term that in this case means “affecting the state of stuff on disk”).

The best way to read Lisp code is usually “inside-out”. Begin with the innermost element, figure out what argument(s) it takes, and see what it passes along as a return value. That return value is then an input for something else. This is true in most computer languages, but in Lisp it becomes especially necessary to read things this way.

Therefore we’ll start inside the innermost expression, at `regexp-substitute/global`. The documentation says that it needs a port, a regular expression, and a string to match that regular expression against. Since `regexp-substitute/global` isn’t writing its output to a port, but passing its arguments out to `string-downcase`, we specify “no port” as `#f`. `Post` has to do with making `regexp-substitute/global` recur on any unmatched parts of the string in `arg`, and the literal `-` is what we’d like to replace our matches with. For more comprehensive information on `pre` and `post`, I actually needed to consult the documentation on `regexp-substitute`, since `regexp-substitute/global` is apparently a special case of the former (and is perhaps implemented using `regexp-substitute`? I didn’t check, but it would be easy enough to do so).

Let’s look at that regex, `[,'!_ \t]+`. In English, it means “match any commas, apostrophes, exclamation points, underscores, blank spaces or tabs”. As noted above, we want to replace any occurrences of these characters with `-`.

For example, a string like `Hey Kids I Have Spaces.txt` would become `Hey-Kids-I-Have-Spaces.txt`. We then pass it out to the `string-downcase` procedure, which transforms it into `hey-kids-i-have-spaces.txt`.

That value is then passed as the second argument to the `rename-file` procedure, which renames `arg` (our original, uncool filename) to `hey-kids-i-have-spaces.txt`.

It’s all wrapped in a `lambda` expression, which does the job of creating and invoking a one-argument procedure out of the several we’ve discussed; this procedure is then applied to every item in our argument list `args`.

```(for-each (lambda (arg)
(rename-file arg
(string-downcase
(regexp-substitute/global
#f "[,'!_ \t]+" arg
'pre "-" 'post))))
args))))
```

Invocation and Program Listing

In this way the file renaming operation that we’ve defined here is applied to each of our program’s arguments, and we invoke it like so (shown here operating on two files):

`\$ guile renamer.scm Hey\ Kids\ I\ Got\ Spaces.txt Oh_no_ugly_underscores.html`

A final note: even for a program as simple as this, I didn’t sit down and bang it out all in one go. Especially with the regex, I was testing little parts of it at the REPL the whole way, consulting the documentation for these functions via the relevant Geiser and Emacs commands. But that’s a story for another day…

Finally, here’s the complete program listing:

```#!/usr/local/bin/guile -s
!#

(use-modules (ice-9 regex))

(if (null? args)
(begin (display "No arguments, exiting...")
(newline)
(exit))
(for-each (lambda (arg)
(rename-file arg
(string-downcase
(regexp-substitute/global
#f "[,'!_ \t]+" arg
'pre "-" 'post))))
args))))

(main)
```

(Image courtesy Melisande under Creative Commons license.)

How often will a bus jam the Lincoln Tunnel?

I commute into Manhattan four or five days a week. Like a lot of people who ride the bus, I really really hate it when the Lincoln tunnel gets jammed. Even though there are tow trucks standing by at all times (from what I can tell), it seems to cost you about 30-60 minutes of commute time. Because it happens often enough to be a pain in the ass, I’ve been thinking lately about how the numbers play out.

As it turns out, there are statistics on bus usage in the lincoln tunnel available on the port authority website:

…in 2009, the XBL averaged 1,791 daily buses…

Since we’re talking averages, i’m going to assume that the weekday load is heavier than on weekends due to commuters. that should bring the average up a bit. The product of 1,791 buses * 7 days is 12,537 buses each week. Guesstimating that 85% of those buses pass through the tunnel Monday through Friday gives us 10,656 buses divided by 5 days for a weekday average of 2,131 buses.

That’s a lot of buses to push through a tunnel each day. But what about during peak commute times? The signage along the road says that the XBL is open from 6am to 10am. Since the statistics from the above website refer only to the XBL, we can infer that all of their measurements come from those morning commute hours. (There is no special commuter lane for buses leaving the city in the evenings that I’ve seen.) Therefore I’ll assume that these statistics refer only to the peak AM commute.

You might infer from the picture on the Port Authority website that there is only one lane leading up to and through the tunnel. I can confirm this. Not only is there only one bus lane, but it’s one lane that stretches quite a ways back from the tunnel and into New Jersey. Once inside the lane, you may not change into another lane, either (this is probably obvious, but worth noting).

What about bus reliability? How often do buses break down? Let’s be generous and assume that any given bus will make this trip successfully 99.9% of the time. This means that the bus will only break down once every 1,000 trips through the lane. I’d estimate that the XBL is ~3 miles long, measured beginning at the EZPASS out in Jersey and ending when the bus has entered normal city traffic around 40th street. Once inside the city proper, a bus can still stall and create problems in the tunnel, but we’ve got to end our measurement somewhere.

According to the multiplication rule 1, we can get the probability that none of the 2131 buses going through the XBL will stall (that is, that they will all make it) by taking our probability that any given bus will make it and raising it to the 2131 power. This gives us 0.999 ^ 2131, yielding 0.119. This means that there is only an 11.9% chance that all 2131 buses will get through the XBL on any given weekday morning without stalling or breaking down!

But is this true? My anecdotal experience over the past few months of commuting says yes. I’ve had to sit through a number of traffic jams coming into the city in the mornings. As a result, I’ve switched to an earlier bus in order to avoid most of the peak commuter buses.

(Image courtesy Melisande under Creative Commons license.)

Footnotes:

1 wonderfully described in John Paulos’ book Innumeracy

What is a Continuation?

This week we explore the continuation, that noble construct of the mind – O bright, shining tool in the aspiring wizard’s toolchest! Half of what you shall read here is paraphrase, half allegory, and the rest? Sprinkled with a few potent grains of Scheme code.

Continuations are constructs that give a programming language the ability to save the execution state at any point and return to that point at a later time in the program’s execution.

Note that continuations do not save program data, only execution context. Taking a function f as its only argument, `call/cc` takes the current continuation (i.e., a “snapshot” of the current control context or control state of the program) as an object and applies f to it.

As you might imagine, the Grand Wizards Sussman and Steele themselves (all hail!) were the first to bring this power to the hands of the humble. Since then continuations have been implemented in a number of other languages, though in my biased opinion Scheme is the most lovely of them all.

Yet another way to think of a continuation is as “that thing that is waiting for the current computation to finish.” When we say “computation,” we really just mean “function” or more loosely “whatever the program is doing at the moment.”

For the more magically inclined, the continuation can be imagined as a jump, or “non-local exit,” that allows the practitioner to teleport from one computational place to another (or from one computational palace to another, even!).

Suppose for example that you are a Sorceror’s Apprentice (as I am). You’ve been asked to clean the Master’s tower while he’s away, but it’s quite boring and will take a long time. Lazy apprentice (and aspiring wizard programmer) that you are, you’d much rather be writing on your obscure programming blog or doing logic proofs. Or even writing Scheme programs!

The state of the tower could best be described as “abysmal”. It turns out that he’s a total slob, though of course he’d probably describe himself as an eccentric genius who’s concerned with things other than housecleaning. Whatever the reasons, the place is a wreck.

How do continuations fit in? Let’s say you’re thinking about writing up a new post for your aforementioned obscure programming blog. You’d like to write about continuations, in part as a teaching exercise for yourself, and in part because it’s just good, clean fun. Now you take a continuation (i.e., save the current execution state of this little program we call “Life”1) – let’s call our saved program state “The Master’s Tower is a wreck and I’m thinking about a post on continuations for my obscure programming blog” for short (or long). Let’s call this time $T_1$.

Having thus taken the continuation, you merrily go about the business of cleaning the Master’s tower, or more precisely, attempting to write Scheme programs that will somehow result in the cleanliness of said tower. Hours later, you invoke the continuation you saved earlier, and you wake up to find yourself thinking about writing up a new post for your blog. You look around and see that the tower is clean (for the moment), leaving you free to go and procrastinate in front of your computer and call it blogging.

Are you tired from having cleaned (or taught Scheme to clean) the whole messy tower? No! Remember that we saved the current execution state at $T_1$, and you were feeling energetic then. Hours later, we’re at $T_2$, and you’re not so fresh anymore. However, you are a Sorceror’s Apprentice, tired or not, and you know a few tricks, such as how to jump back to the continuation you saved at $T_1$.

That’s how you come to find yourself sitting at your tiny desk in the corner of the Master’s tower, surrounded by orderliness, calm, and quiet. The tower is clean, you’re feeling refreshed, and you have an idea for something to write about. Ain’t life grand?

But wait! What the hell does this have to do with anything? Is there any actual code we can look at? Of course!

Our motivating example is taken from a couple of earlier posts regarding a little Scheme problem. (See here for details.) The following procedure was implemented the first time around using good-ol’-fashioned recursion. You can see its implementation and a trace of its output here. I thought it would be fun to play around a bit with continuations, and so I wrote the following:

```(define (gather-next-batch-cc pred seq)
(let ((result '()))
(call-with-current-continuation
(lambda (return)
(for-each (lambda (elem)
(if (pred elem)
(set! result (cons elem result))
(return (reverse result))))
seq)))))
```

As you can see, we’re doing a simple iteration over a list using `for-each`, but we’ve wrapped it in the `call-with-current-continuation` form. According to the venerable R5RS:

procedure: `(call-with-current-continuation /proc/)`

Proc must be a procedure of one argument. The procedure `call-with-current-continuation` packages up the current continuation (see the rationale below) as an “escape procedure” and passes it as an argument to proc.

In our example above, `call-with-current-continuation` (which I’ll refer to as “call/cc” from here on out) takes a `lambda` with one argument, return. We then iterate over seq, checking to see if elem matches our predicate. If it does, we push it onto result. Because we know the format of the list that `gather-next-batch-cc` will be dealing with, e.g.,

```'(1 2 3 b 4 5 c 6 7)
```

We know that, as we move down the list, we can jump to return as soon as we start seeing elements of the list that don’t match our predicate (`number?` in this case), rather than iterating down the whole thing.

But don’t take my word for it! Let’s trace that puppy! I must return once again to my lovely Scheme 48 REPL. First, we’ll run a trace using our recursive implementation of `gather-next-batch`:

> (plist->alist gather-next-batch L)
[Enter (gather-next-batch #{Procedure 585 number?} ‘(1 2 3 b 4 5 c 6 —))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(2 3 b 4 5 c 6 d —))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(3 b 4 5 c 6 d e))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(b 4 5 c 6 d e))
Leave gather-next-batch ‘()]
Leave gather-next-batch ‘(3)]
Leave gather-next-batch ‘(2 3)]
Leave gather-next-batch ‘(1 2 3)]
[Enter (gather-next-batch #{Procedure 585 number?} ‘(4 5 c 6 d e))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(5 c 6 d e))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(c 6 d e))
Leave gather-next-batch ‘()]
Leave gather-next-batch ‘(5)]
Leave gather-next-batch ‘(4 5)]
[Enter (gather-next-batch #{Procedure 585 number?} ‘(6 d e))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(d e))
Leave gather-next-batch ‘()]
Leave gather-next-batch ‘(6)]
[Enter (gather-next-batch #{Procedure 585 number?} ‘(e))
Leave gather-next-batch ‘()]
[Enter (gather-next-batch #{Procedure 585 number?} ‘())
Leave gather-next-batch ‘()]
‘((a (1 2 3)) (b (4 5)) (c (6)) (d ()) (e ()))

As we expect, we’re recurring down through the list, banging on the empty list at the bottom, and then building back up from that. Easy-peasy.

Now let’s trace the version under discussion, the continuation-powered `gather-next-batch-cc`:

> (plist->alist gather-next-batch-cc L)
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘(1 2 3 b 4 5 c 6 —))
Leave gather-next-batch-cc ‘(1 2 3)]
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘(4 5 c 6 d e))
Leave gather-next-batch-cc ‘(4 5)]
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘(6 d e))
Leave gather-next-batch-cc ‘(6)]
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘(e))
Leave gather-next-batch-cc ‘()]
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘())
Leave gather-next-batch-cc #{Unspecific}]
‘((a (1 2 3)) (b (4 5)) (c (6)) (d ()) (e #{Unspecific}))

As you can see (and if the trace output is to be believed), we’re performing significantly fewer operations here. I count 5 procedure entries using this implementation, compared to 11 for the recursive version. I performed this same test using a list with 8 separate groups of numbers, totalling 28 numbers in all. The recursive version called itself 36 times, whereas the “call/cc’d” version came in at 8. In both these cases, `gather-next-batch-cc` is only called as many times as there are groups of numbers, since it only iterates until it runs out of numbers, and then jumps back.

(Image courtesy Melisande under Creative Commons license.)

Footnotes:

1 Yes, I know about Conway’s Game of Life.

A Scheme Code Kata, Explained (Part II)

Last time I walked you through the `gather-next-batch` procedure. Now let’s put it together with its caller. As I mentioned before, I was inspired by the Schemish stylings of the good Mr. Harvey to implement the ‘plist’ to ‘alist’ transformation using a higher-order procedure. `gather-next-batch` was that procedure.

One way I like to think about higher-order procedures is as follows: Imagine a man pushing a lawn-mower along on a beautiful Saturday morning. As he pushes the mower along, it lifts, slices, and ejects the grass that comes underneath its blade. In order for it to move along and do its work, it needs the man pushing, since the forward momentum is essential to its operation – otherwise there would be no grass underneath for it to cut!

It’s much the same with higher-order procedures: one procedure (the man) pushes another (the lawn-mower) across a data structure (the lawn). Of course, this is the simplest use case, but it’s where most of us start.

That might help you to understand how `gather-next-batch` works, at least in broad strokes. Coming back to our overall problem, we need to figure out how to use `gather-next-batch` to our advantage. We’ll call it from inside another procedure which will collect the entire ‘alist’ together, the cryptically-named `p->a`.

`p->a` will transform the given type of ‘property list’ into an ‘association list.’ Here it is:

```(define (p->a p)
(cond ((null? p) '())
((symbol? (car p))
(cons (list (car p)
(gather-next-batch number? (cdr p)))
(p->a (cdr p))))
(else (p->a (cdr p)))))
```

Let’s walk through it. We take a property list p as our only parameter. As is usual with Scheme, we walk the list recursively, checking first for `null?`, and returning an empty list in that case. If the first item is a symbol, we make a new, smaller list whose first item is the first item of p and whose other items are the result of calling `gather-next-batch` with `number?` as its predicate. `gather-next-batch` walks the rest of p (a.k.a., `(cdr p)`) and return the next group of numbers.

We then take the little list we’ve made (which will look something like `(a 1 2 3)` ) and push it onto the result of `p->a` when called with all but the first element of p.

If the first element of p is not a symbol, we just call `p->a` on the rest of p.

That’s rather more verbose in English than in Scheme, but I was able to write the English description much more quickly than I was able to write the initial solution in Scheme. See if you can step through the Scheme code in your mind, and use the English as an aid where necessary.

Note that Scheme and Lisp, more so than some other languages, require you to read the code “from the inside out.” The heart of a procedure will return a little data structure, which you’ll then pass to another procedure, and perhaps another, etc.

In closing, let’s look at the trace of `p->a` printed by my lovely assistant, Scheme 48. Ain’t recursion beautiful?

```> (p->a '(a 1 2 3 b 4 5 c 6 7 d e))
[Enter (p->a '(a 1 2 3 b 4 5 c ---))
[Enter (p->a '(1 2 3 b 4 5 c 6 ---))
[Enter (p->a '(2 3 b 4 5 c 6 7 ---))
[Enter (p->a '(3 b 4 5 c 6 7 d ---))
[Enter (p->a '(b 4 5 c 6 7 d e))
[Enter (p->a '(4 5 c 6 7 d e))
[Enter (p->a '(5 c 6 7 d e))
[Enter (p->a '(c 6 7 d e))
[Enter (p->a '(6 7 d e))
[Enter (p->a '(7 d e))
[Enter (p->a '(d e))
[Enter (p->a '(e))
[Enter (p->a '())
Leave p->a '()]
Leave p->a '((e ()))]
Leave p->a '((d ()) (e ()))]
Leave p->a '((d ()) (e ()))]
Leave p->a '((d ()) (e ()))]
Leave p->a '((c (6 7)) (d ()) (e ()))]
Leave p->a '((c (6 7)) (d ()) (e ()))]
Leave p->a '((c (6 7)) (d ()) (e ()))]
Leave p->a '((b (4 5)) (c (6 7)) (d ()) (e ()))]
Leave p->a '((b (4 5)) (c (6 7)) (d ()) (e ()))]
Leave p->a '((b (4 5)) (c (6 7)) (d ()) (e ()))]
Leave p->a '((b (4 5)) (c (6 7)) (d ()) (e ()))]
Leave p->a '((a (1 2 3)) (b (4 5)) (c (6 7)) (d ()) (e ()))]
'((a (1 2 3)) (b (4 5)) (c (6 7)) (d ()) (e ()))
```

(Image courtesy Mélisande* under Creative Commons license.)

A Scheme Code Kata, Explained (Part I).

A little while ago I dumped some Scheme code on you, without much in the way of context. Unless you clicked on those delicious links and spent time poring over the information therein, what I posted might not have made much sense. I intend to rectify that sad situation with this little post.

(BTW: If you want this code, it’s available at github, as is the entire source of this blog. Though I heartily recommend that you type it in for yourself, since that will probably force you to pay slightly closer attention to it. And attention is the name of the game, I think.)

I’ll begin by restating the problem in my own words. Suppose you are given a regular Lisp list of the form

```(a 1 2 3 b 4 5 c 6 d e).
```

Write code that will convert said list into a so-called “association list.” This is a very ancient Lisp structure that serves a function similar to a primitive hash table (though much, much slower).

```((a (1 2 3)) (b (4 5)) (c (6)) (d ()) (e ()))
```

This will allow us to get at the “values” associated with each symbol using the `assoc` procedure. In this case:

```scheme@(guile-user)> (assoc 'b (plist->alist foo))
\$397 = (b (3 4))
```

After wrestling with a few of my own failed solutions, I came across one by Brian Harvey in the comp.lang.scheme discussion surrounding this problem. He used a couple of higher-order procedures, as I recall. I didn’t fully grok his particular solution; I decided that I could write something a bit more concise.

His solution did inspire me to separate the act of gathering the next batch of non-symbols from the act of creating the alist.

Here I’ll define a procedure, `gather-next-batch`, which accepts two arguments: a predicate procedure and a sequence. The predicate will tell `gather-next-batch` what, exactly, to gather the next batch of:

```(define (gather-next-batch pred seq)
(cond ((null? seq) '())
((pred (car seq))
(cons (car seq)
(gather-next-batch pred (cdr seq))))
(else '())))
```

You can see that this is a pretty bog-standard recursive Scheme procedure. Let’s walk through it together. First, we test if our sequence `seq` is `null?`, or empty. If not, we check the first element of `seq` (a.k.a. `(car seq)`) against our `pred`, or predicate procedure, which will return true or false. If `pred` looks at `(car seq)` and returns `#t`, then we `cons` the aforementioned first element of `seq` onto a list created by recursively calling `gather-next-batch` on what’s left of `seq`, namely, all but the first element, which we’ve just processed.

(If you’re looking for a set of rules/patterns on how to write nice little recursive procedures like this, I can highly recommend a tome of great power known as The Little Schemer. Or should I say: a tome that deposits one, slightly bewildered, at the outer gateways of great power! But I digress…)

Let’s test out our awesome new procedure:

```scheme@(guile-user)> (gather-next-batch number?  '(a 1 2 3 b 4 5 c 6 d e))
\$404 = ()
```

What happened? I was expecting to get back `(1 2 3)`! Well, as it turns out the first element of the list we passed to `gather-next-batch` didn’t match our supplied `number?` predicate. Therefore, we crashed through our conditional to the bottom (where `else` lives), and in this case we asked `else` to return the empty list, `()`. And so it did!

Let’s try this again, using a list whose first element matches our predicate:

```scheme@(guile-user)> (gather-next-batch number? (cdr '(a 1 2 3 b 4 5 c 6 d e)))
\$403 = (1 2 3)
```

In this case we asked for the `cdr` of our list, which does begin with a number. Therefore `gather-next-batch` was able to get going on its work of gathering up a list containing the next batch of numbers, `(1 2 3)`.

Next time we’ll look at how to integrate this procedure with our larger solution. For now I’ll leave you with the trace output of `gather-next-sequence` (helpfully drawn for us by Scheme 48). It should help visualize what this little procedure’s actually doing.

Until then, may you hack gracefully, friends!

```> (gather-next-batch number? (cdr foo))
'(1 2 3)
> ,trace gather-next-batch
> (gather-next-batch number? (cdr foo))
[Enter (gather-next-batch #{Procedure 585 number?} '(1 2 3 b 4 5 c 6 ---))
[Enter (gather-next-batch #{Procedure 585 number?} '(2 3 b 4 5 c 6 d ---))
[Enter (gather-next-batch #{Procedure 585 number?} '(3 b 4 5 c 6 d e))
[Enter (gather-next-batch #{Procedure 585 number?} '(b 4 5 c 6 d e))
Leave gather-next-batch '()]
Leave gather-next-batch '(3)]
Leave gather-next-batch '(2 3)]
Leave gather-next-batch '(1 2 3)]
'(1 2 3)
```

(Image courtesy Mélisande* under Creative Commons license.)

A Scheme Code Kata

Reader beware! This is a meta-creature, a post about a post about a post. By way of comp.lang.scheme, the musings of the great jao (who incidentally is the Wizard behind Geiser (which is the way to Scheme with Emacs these days)), and finally, this humble blag, I present my (straight R^5RS!) solution to the Scheme kata described in the above links:

```(define (plist->alist p)
(cond ((null? p) '())
((symbol? (car p))
(cons (list (car p)
(gather-next-batch number? (cdr p)))
(plist->alist (cdr p))))
(else (plist->alist (cdr p)))))

(define (gather-next-batch pred seq)
(cond ((null? seq) '())
((pred (car seq))
(cons (car seq)
(gather-next-batch pred (cdr seq))))
(else '())))
```

(Image courtesy Mélisande* under Creative Commons license.)

A Description of the Problem

We are given a triangle of numbers, and we are asked to write a program that computes the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.

• Each step can go diagonally down to the left or the right.
• The number of rows in the triangle will be between 1 and 100, inclusive.
• The numbers that populate the triangle are integers between 0 and 99.

What are our Inputs and Outputs?

Our initial input data will live in a file called `triangle-input.txt`, which contains the following:

```5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
```

Note that the first line of the file is not part of the triangle itself; it’s there to tell us how many levels deep the triangle goes.

```30
```

We’ll place our output in a file called `triangle-output.txt`, which will contain a single integer. We’ll place the names of our input and output files in the program constants `INPUT_FILE` and `OUTPUT_FILE`, respectively.

Reading the Input, Writing the Output

First, we’ll need to get the values out of `triangle-input.txt` and store them in a convenient structure. In this case, an array of arrays should do.

We begin by creating an empty array, tmp, which will act as a temporary storage space for the lines of `triangle-input.txt`.

We’ll read the lines of the file one at a time. For each line, we `split` the string, e.g., “1 2 3 4 5\n”, into a list, and `push` that line onto our array `tmp`.

```tmp = []

File.open(INPUT_FILE, "r") do |f|
f.lines.each do |line|
tmp.push line.split
end
end

```

Unfortunately, we’re pushing an array of strings onto tmp, since

```"4 5 2 6 5\n".split
```

returns this:

```["4", "5", "2", "6", "5"]
```

Therefore, we’ll take a second pass through and convert those arrays of strings into arrays of numbers. The resulting array will allow us to – finally! – begin our real work. Notice that this is a nested call to `map`, best read from the inside out. The value returned by the inner `map` is returned to the outer, with the results stored in variable tri, since the return value of `map` is always an array.

```tri = tmp.map { |array| array.map { |elem| elem.to_i } }
```

We’ll wrap everything here up in a method, `read_triangle_input`, which will show up in the complete program listing below. We’ll also leave the `write_triangle_output` method for the listing; it requires little explanation.

Solving our Actual Problem

Now that the housekeeping chores are out of the way, we can jump in and begin the real work of finding the highest sum in our triangle.

We’d like to write a method, `triangle_sum`, which, given an array of arrays like the one we’ve just constructed, returns an integer representing the highest sum calculated on its imagined path “down through the triangle.”

Since our route through the triangle is restricted to “steps” that can “go diagonally down to the left or the right,” the most natural representation of this data is as a tree. We’ll simulate this in a crude way using an array of arrays.

The Inner Loop

Since our fundamental data structure is an array, we’ll need to choose a looping construct; we’ll stick with the “C-style” iterative constructs here since they map well onto this problem (no pun intended). We’ll use an `index` variable to keep track of where we are in the iteration.

Inside the loop, we want to know three things (among others):

• Where am I?
• Where is the element to my upper left?
• Where is the element to my upper right?

We’ll denote the answers to these questions with the variables `this`, `upleft`, and `upright` in our program listing below.

Remember the problem description: Starting at the root of the tree, we’ll keep a running sum of all the numbers we’ve seen thus far on this particular path through the tree.

Visualizing Our Movement Down the Triangle

In order to solve this problem, we started with some hand-simulation of what would eventually become the final algorithm. The example below shows how it works: given where we are in the array of arrays, we look “up and to the left” and “up and to the right” of where we are. In the following diagrams, we denote our position in the algorithm with a lovely text arrow.

```Index: 1

[7] <---
[3, 8]
[8, 1, 0]
[2, 7, 4, 4]
[4, 5, 2, 6, 5]
```

When `index` is 1, there isn’t anything to do, since we can’t look “up” at anything. Therefore, move on.

```Index: 2

[7]
[10, 15] <---  Was: [3, 8]
[8, 1, 0]
[2, 7, 4, 4]
[4, 5, 2, 6, 5]
```

When `index` is 2, we look up and to the left (7), and up and to the right (also 7). Each time through the loop, we create a new temporary array called `next_row`, in which to store the running sums. In this case, we create a new array `[10, 15]` by adding 7 to each of `[3, 8]`. We then replace the old array with the new.

```Index: 3

[7]
[10, 15]
[18, 11, 16, 15] <--- Was: [8, 1, 0]
[2, 7, 4, 4]
[4, 5, 2, 6, 5]
```

`index` is now 3. We perform the same operations as above: first, create an empty array. Then, for each element in the old array `[8, 1, 0]`, we add the value of the element (which we’ll call `this` in our program code) to the values of `upleft` and `upright` (these are obviously our variable names for the “up and to the left” and “up and to the right” values we’ve already mentioned). In each case we push the results of these additions onto the new temporary array. Once we’ve finished, we replace the existing array with the new, as before.

```Index: 4

[7]
[10, 15]
[18, 11, 16, 15]
[20, 25, 18, 15, 20, 20] <--- Was: [2, 7, 4, 4]
[4, 5, 2, 6, 5]

Index: 5

[7]
[10, 15]
[18, 11, 16, 15]
[20, 25, 18, 15, 20, 20]
[24, 25, 30, 27, 20, 24, 21, 20] <--- Was: [4, 5, 2, 6, 5]

Result: 30
```

Here we show two steps more of the process, and its completion. We can easily see that 30 is the largest sum in the last array, and our answer.

We notice that the “new” interior arrays we’re creating on each turn through the loop are longer than the originals they replace, so we’re not being as efficient with memory as we’d like. At least Array expansion is an O(n) operation!

The Complete Program Listing of `triangle.rb`

This essay is over 1200 words long already according to `wc -w`. Therefore, since this algorithm can be described very succinctly in code, I’ll break the rules of literate programming and simply end with the program listing itself. Note the temporary variables `next_row`, `this`, `upleft`, and `upright`, which are described in the section “Visualizing Our Movement Down the Triangle” above.

As always, the contents of this literate program are available at Github.

(Update: better solutions and discussion over at the Ruby Reddit)

```#!/usr/bin/env ruby

require 'test/unit'

INPUT_FILE  = "triangle-input.txt"
OUTPUT_FILE = "triangle-output.txt"

tmp = []

File.open(INPUT_FILE, "r") do |f|
f.lines.each do |line|
tmp.push line.split
end
end

tri = tmp.map { |array| array.map { |elem| elem.to_i } }
end

def write_triangle_output(result)
File.open(OUTPUT_FILE, "w") do |f|
f.print result
end
end

def triangle_sum(tri)
a = Array.new(tri)
index = 1
len = a.shift[0]-1
while index <= len
next_row = []
for i in 0..index
this = a[index][i]
upleft = a[index-1][i-1]
upright = a[index-1][i]

if i == 0
next_row.push this + upright
elsif i == index
next_row.push this + upleft
else
next_row.push this + upleft
next_row.push this + upright
end
end
a[index] = next_row
index += 1
end
a[index-1].max
end

highest_sum = triangle_sum(tri)
write_triangle_output(highest_sum)

class TestTriangleSum < Test::Unit::TestCase
def test_01
expected = triangle_sum(tri)
assert_equal expected, 30
end
end
```

(Image courtesy Mélisande* under Creative Commons license.)

The Problem Description

A zero-indexed array A consisting of N integers is given. An
equilibrium index of this array is any integer P such that 0 <=
P < N and the sum of elements of lower indices is equal to the sum
of elements of higher indices, i.e.,

```A[0] + A[1] + ... + A[P-1] =
A[P+1] + ... + A[N-2] + A[N-1].
```

The sum of zero elements is assumed to be equal to 0.

Write a function that, given a zero-indexed array A consisting of
N integers, returns any of its equilibrium indices. The function
should return -1 if no equilibrium index exists.

• Expected worst-case time complexity is O(N)
• Expected worst-case space complexity is O(N), beyond input storage

(not counting the storage required for input arguments).

The above is taken from the problem description by Codility; they discuss one solution (written in C) here.

Notes on this Implementation

First things first: we’ll avoid the `return -1` “C-ism,” as it’s more natural to return `nil` in Ruby. In fact, Ruby sees -1 as `True`, so returning it will break many common predicates, whereas `nil` won’t.

Experienced programmers will observe that this implementation does not meet the `O(n)` time and space complexity requirements as listed above. Absolute simplicity of implementation is the focus right now, but that may change in a future version.

Finally, notice that this short essay is itself a literate program, implemented using the wonderful Org-mode capabilities which are included with the Emacs text editor.

The Inner Loop

Since most of the program’s work is done inside a single `while` loop, we’ll begin there.

Let A be the Ruby array

```[-7, 1, 5, 2, -4, 3, 0].
```

The equilibrium index of A can be computed by hand, so it’s a good place to start. It’s also our first test case (see below).

We’ve chosen to implement the iteration over A using a `while` loop rather than the more idiomatic `Array#each` method since we need to keep track of our current index into the array.

As we begin the loop, the variable `index` is initialized as the length of the array minus one. This is required because Ruby’s arrays are zero-based, but the value returned by its `Array#length` method is not.

```while index > 0
left  = a[0..index-1].reduce(:+)
right = a[index+1..len].reduce(:+)
if left == right
return index
end
index -= 1
end
```

We’ll iterate backwards through the array from the end. At each value of `index`, we’ll split A into two smaller arrays, `left` and `right`. This requires allocating two new arrays in memory, reading the values of the desired “slices” of A, and copying them into `left` and `right`, respectively. This operation provides for an implementation that is simple to visualize and understand, but it’s also the reason why we fail to meet the requirements for `O(n)` space and time complexity. A more efficient implementation would avoid these unnecessary allocation and copying steps, and we might change this program at some point to achieve that.

Visualizing the Iteration

Let’s look at `left` and `right` at each stage of the iteration:

We can see that when we split A at `index`, we always leave a “gap” in between, and it’s this gap which will provide us with the answer we seek: the equilibrium index (provided that the equilibrium index is defined for the given array, that is). At every iteration in the diagram above, we sum the values within `left` and `right` using the `Array#reduce` method. If `left` and `right` are equal, `index` is defined as the equilibrium index, and we `return index`. Otherwise, we’ll end up escaping the loop and returning `nil`.

The `equi` Function

Looking briefly at the entire `equi` function, we can see that it’s just a wrapper for the `while` loop. First we set the value of `index` and `len` as bookkeeping measures. We then enter the `while` loop as described above. If the loop completes without returning a value, the program returns to the next outer context and returns the `nil` value, which lets our caller know that this array doesn’t have an equilibrium index.

```def equi(a)
index = a.length-1
len   = a.length-1
while index > 0
left  = a[0..index-1].reduce(:+)
right = a[index+1..len].reduce(:+)
if left == right
return index
end
index -= 1
end
nil
end

```

Test Cases

Over the course of developing the program, a number of test cases have come to mind. We’ll begin with the given array A that we started with.

```def test_random
sample_array = [-7, 1, 5, 2, -4, 3, 0]
expected = equi(sample_array)
assert_equal expected, 3
end

```

Here we’ve defined a trivial `pyramid’ array of values that ascend and descend symmetrically.

```def test_trivial_pyramid
sample_array = [1, 2, 3, 4, 3, 2, 1]
expected = equi(sample_array)
assert_equal expected, 3
end
```

This test checks the case where the first value is equal to the sum of all the rest (save the equilibrium index, of course).

``` def test_biggest_first
sample_array = [99, 0, 66, 32, 1]
expected = equi(sample_array)
assert_equal expected, 1
end
```

Similarly, we check for the case where the last value alone is equal to the sum of `left`.

```def test_biggest_last
sample_array = [66, 32, 1, 0, 99]
expected = equi(sample_array)
assert_equal expected, 3
end
```

We should return `nil` for an array with a single element, since the equilibrium index is not defined in that case.

```def test_single_element
sample_array = [0]
expected = equi(sample_array)
assert_equal expected, nil
end
```

The same is true of an array containing a single `nil`.

```def test_single_nil
sample_array = [nil]
expected = equi(sample_array)
assert_equal expected, nil
end
```

The Complete Program Listing

Finally, we have the complete program listing for the `tangle`‘d file `literate-equi.rb`. Since we’ve included our tests by subclassing the `Test::Unit` class, Ruby will run them for us when we invoke the program. Running `ruby literate-equi.rb` at the command shell should return the following output:

```~/Desktop/Dropbox/current/logicgrimoire \$ ruby literate-equi.rb
Started
......
Finished in 0.002195 seconds.

6 tests, 6 assertions, 0 failures, 0 errors
```

The program itself:

```#!/usr/bin/env ruby

require 'test/unit'

def equi(a)
index = a.length-1
len   = a.length-1
while index > 0
left  = a[0..index-1].reduce(:+)
right = a[index+1..len].reduce(:+)
if left == right
return index
end
index -= 1
end
nil
end

class TestEqui < Test::Unit::TestCase
def test_random
sample_array = [-7, 1, 5, 2, -4, 3, 0]
expected = equi(sample_array)
assert_equal expected, 3
end

def test_trivial_pyramid
sample_array = [1, 2, 3, 4, 3, 2, 1]
expected = equi(sample_array)
assert_equal expected, 3
end
def test_biggest_first
sample_array = [99, 0, 66, 32, 1]
expected = equi(sample_array)
assert_equal expected, 1
end
def test_biggest_last
sample_array = [66, 32, 1, 0, 99]
expected = equi(sample_array)
assert_equal expected, 3
end
def test_single_element
sample_array = [0]
expected = equi(sample_array)
assert_equal expected, nil
end
def test_single_nil
sample_array = [nil]
expected = equi(sample_array)
assert_equal expected, nil
end

end
```

First Post

“Imagination is more important than knowledge.”
— Albert Einstein

At the age of 30, I finally started learning Calculus. If that sounds crazy to you, you’re not alone. It sounded pretty crazy to me too. It still does, in fact. I was never much good at math in school, as my transcripts would show anyone who cared to look. I failed New York State’s Course II on geometry in tenth grade, and ended up taking it again the next year. I barely passed, even the second time around — with a 68, I believe. As for Course III in trigonometry, I failed outright. In short, I was not considered one of the bright mathematical lights at my high school.

It was some years later, in college, that I discovered computers. Up to that point, I’d used them mostly to write term papers for my classes, but as time went on, I became more interested in how they worked. In my travels on the web, I stumbled across a few message boards frequented by programmers, and discovered another world. It was amazing; there were people who actually just wrote computer programs all day long. In return, people paid them money. This seemed hard to believe at the time.

I soon found out what drove these people to do what they did: it was a whole lot of fun. Before long, I was writing my own little programs. There was something really neat about giving a computer a set of instructions and then standing back and seeing what happened. Sometimes, I could get it to do what I was imagining. Most of the time, I couldn’t. Slowly, I got better at talking to the computer in ways it could understand. In its own language.

There comes a point in the life of any programmer, however, when a lack of math skills starts to really hold her back. Once I reached that point, my historical disinterest in math disappeared. I couldn’t wait to get started. I bought a book from the local bookstore that promised to “demystify” trigonometry and worked on it almost every day after work, carefully reading through descriptions of terms like “vector” and “parallax,” all the while amazed that here I was, actually doing what I never thought I could: I was teaching myself the math I never learned in school, and what’s more, I began to look forward to those sessions as the best part of my day.

Why does any of this matter? It matters because I know that there are lots of kids out there like I was. They may think they aren’t any good at math, or that it’s boring. They may even believe that they hate it. What they’re lacking is a fun way to apply it. After all, memorizing trigonometric formulas is only fun if you have a reason.

That is exactly what I aim to do with this blog: give people a reason to care about math, and help them to understand that math isn’t just about some abstract notion of “intellectual enrichment,” but that it can help us do cool things, whether we’re interested in programming computers, experimenting with model rocketry, or building our own robots.

I don’t consider myself an expert in math or programming, of course. I’m just another PC hobbyist with an itch to scratch, and in many ways, I’ve spent the last few years learning just how little I really know. That doesn’t matter — if something I write here helps even one other person out there achieve their dream, I’ll consider the time well spent.

Bottom line: whatever this strange way of thinking that makes a computer programmer is, I’m determined to keep going until I master it. It doesn’t matter how long it takes me to get there, since I consider the journey itself to be a labor of love, and it’s something that I know I will enjoy for the rest of my life.

What activities can you say that about?

(Image courtesy Melisande under Creative Commons license.)