How often will a bus jam the Lincoln Tunnel?

https://logicgrimoire.files.wordpress.com/2012/09/wpid-sierpinski.jpg

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?

https://logicgrimoire.files.wordpress.com/2012/04/wpid-star-spring.jpg

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)

https://logicgrimoire.files.wordpress.com/2012/04/wpid-orange-tesselation.jpg

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).

https://logicgrimoire.files.wordpress.com/2012/03/wpid-scheme-kata-2-backlit-tesselation.jpg

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

https://logicgrimoire.files.wordpress.com/2012/02/wpid-scheme-kata-paper-quilt.jpg

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.)

What is the Highest Sum of a Number Triangle?

https://logicgrimoire.files.wordpress.com/2012/02/wpid-paper-triangles.jpg

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.

Some additional restrictions:

  • 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.

(Read the original description here.)

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"

def read_triangle_input
  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

tri = read_triangle_input
highest_sum = triangle_sum(tri)
write_triangle_output(highest_sum)  

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

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

Finding the Equilibrium Index of an Array

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:

https://logicgrimoire.files.wordpress.com/2012/02/wpid-equi.png

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 
Loaded suite literate-equi
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

https://logicgrimoire.files.wordpress.com/2012/09/wpid-sierpinski-molecule-cp.jpg

“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.)