My Introduction to Computers and Email

I wrote a few programs using BASIC on a sinclair in 1981, then a few more, again in BASIC, on an Apple II+. But honestly, it did not come naturally to me. I basically just copied the programs out of books, and never took the time to design something original.

I sent and received my first emails in October of 1992. I was then a student in my first year of college in Massachusetts.

The system was a VAX running VAX/VMS. I remember that it had the commands "mail" and "finger" but lacked an editor. When typing an email message, after hitting the return key, that line could not be edited again.

In January of 1993, I heard about a college-sponsored contest called the Great Minds Challenge. After dominating the high school haloween candy-jar-estimation contests, I assumed I would be a shoo-in. I went to the meeting where the problems was explained. The participants had one month to prepare. At the end of the month, all participants would be emailed a list of 100-1000 numbers between 0 and 100,000. These numbers would correspond to the weights of hypothetical rocks. We would have one hour to somehow divide the rocks into two piles of equal weight. At the end of the hour, we would have to return by email the same list of numbers, and next to each number the letter A or B depending on which pile the rock should be in.

I came up with dozens of schemes to do this, first using slips of paper, then using a spreadsheet. The one thing I did not want to do was lower myself to the level of the "computer science" students who would be solving the problem with their own programs. I was insistent on this point for about a week, until a friend of mine convinced me quite easily that there was no way for a human to beat a computer on such a clearly defined problem. It was no wonder that the Great Minds Challenge, sponsored by the computer science department, had chosen an NP-complete problem.

There was just one problem: I didn't know how to program. Luckily, that same friend taught me how to use emacs and cc, and with our accounts on the computer science department's low-end sun box, I wrote one long main() function thousands and thousands of lines long.

After brutal printf mania, debugging was finally done. I wish I could say I had come up with a clever algorithm, but I didn't. All the program did was brute-force testing. Well, maybe it's a little clever, but not very.

To begin with, all the rocks were put in one pile (A) and none in the other pile (B).

Then the program went through and tested, one rock at a time, whether moving that rock to the other pile would result in a better balance. Remember, the goal was to have the weight of the rocks in pile A as nearly as possible equal the weights of the rocks in pile B.

After the basic sort, then the program proceeded to pick every combination of two rocks, and consider whether moving those two rocks would result in a better balance.

Then, the program would check every combination of three rocks, and consider whether moving all three of those rocks would result in a better balance.

Then, five rocks, six rocks, seven rocks. And that was the limit of what the algorithm could handle.

Ultimately, the program tied for first place. I do not understand to this day how it came to pass that most of the programs did not successfully sort the list of rocks because the problem was elementary, the list of rocks was random (and therefore odds were good that it wouldn't contain a trick set of rocks more difficult to sort). And there were a lot of rocks (also making the problem easier, rather than harder).

Amazingly enough, in testing, time and again, with random list after random list, it was remarkable how easy it was to sort a large list of rocks into two equally weighted piles.

Luckily, I no longer have the source code for that program.