Adventures in junior programming, episode 1

In my last post I mentioned that I had been writing an instructional applet for my son to learn some math concepts. I received this half-joking reply:

If you truly loved your son, you would have made HIM program that applet! He's seven - that's old enough for Java, at the very least.

I actually think seven is a little young to get started, but as I thought about it, I decided, heck, why not? I picked up some extra money in college tutoring a thirteen year old in C++, and later taught classes for half a year in Fort Worth. It's been over ten years since I taught any actual classes, but is it all that unreasonable to try and give the essential concepts of Java across to a seven year old?

I was already six when my dad bought our first computer, and it wasn't for a few more years that I started reading and understanding the BASIC programs that were in vogue back then. But Ben, like many kids of his generation, was introduced to computers at an early age, and has been comfortable using them for most of his life. He's already seen what the inside of a computer looks like when I swapped out components, and I've even gone over some explanations of binary numbers with him, including the "counting on your fingers" trick.

I have done two lessons so far, first on paper and last night on a laptop. Since I've done only sporadic posts on this blog recently, I think it's not a bad idea to chronicle some of this effort. One thing I discovered while teaching classes is that there is no better way for you to solidify fundamental concepts in your own mind than to try to explain it to somebody else. There is nothing like having to break down assumptions that are second nature to you but completely foreign to another person.

So the first thing I've discovered is: Java is kind of hard.

Programmers traditionally write "Hello world" as their first program, so let's take a look at some ways that this is handled in various languages.

BASIC:

10 print "Hello world"

Nobody learns BASIC anymore, but it was a standard on those old PC 8086's I had as a kid. In fact, if you booted up the computer without inserting a floppy disk, the computer (which lacked a hard drive, and hence lacked a useful operating system in memory) would just load up a BASIC compiler environment directly from the BIOS. It was designed to be a beginner language.

Next let's look at Perl, which is known as a scripting language that is powerful at handling string manipulation:

print "Hello world";

Even simpler, superficially, because Perl is a procedural language which does not use line numbers. Once you start getting into program flow, BASIC starts looking simpler through heavy use of the "goto" statement to control program flow. But as everyone should know, "goto" sucks.

Next we'll look at C, which is what I initially taught in the semester before teaching my classes C++.

#include <stdio.h>

main() {
printf("Hello world");
}

Slightly trickier. In C, nothing runs unless it is directly or indirectly invoked by a "main" function. Thus, unlike the other two languages, in order to become proficient enough to run the most trivial of programs, you have to have some trivial understanding of what a function is about.

There's also the rather cryptic line "#include <stdio.h>", which contains additional wacky symbols that have to be either explained or hand-waved away. When I introduced students to this language, I initially just gave them a complete "hello world" program and said "Focus on what's inside the braces, you'll understand what they mean later." Students love to complain about this sort of thing, as they tend to view unexplained stuff as unnecessary and annoying.

Now here's the java program.

class Hello {
public static void main(String[] args) {
System.out.println("Hello world");
}
}

Seriously now, those are a LOT of details to expect a pure novice to absorb, even if he were older. Let me count the unfamiliar concepts:

1. "class Hello": Right from the get-go, all Java programs enforce object-oriented structure. Objects and classes are a beast to understand -- I first heard the concept as a senior in high school, failed to self-teach it, and then didn't really get it until my first college course in C++. Now let's explain the difference between a class and an instantiating object to kid who's going on eight.
2. "main": Just like in the C example, you're not going to get anywhere until you understand methods (aka functions inside a class). I had to make an analogy to nouns and verbs in sentences, since Ben has played Mad Libs before. Even so, it's all pretty abstract, and the word "main" does not suggest an action word at all.
3. "(...)": Now that we know that "main" is a verb, it's time to learn that all verbs in Java must be followed up with parentheses, which may or may not contain some arguments.
   
4. "void": Some methods return an object type and others don't... you know what? I'll tell you later.
   
5. "public": So here we encounter the notion of public and private methods, which is intended to separate interface from implementation. Simple, right?
6. "static": So yeah, this function can be called generically through the class itself, and does not need to be applied to a particular instance of the class. And by the way, all methods called directly from "main" must also be called "static," and the only way to simplify your calls is if you declare a second class and make an instance object.
7. "String ... args": It's an object declaration. A string is a sequence of characters. Your program won't recognize the "main" method unless that String argument is in there, even though we have no intention of reading the command line arguments yet...
8. "[]": ...but this string is not just any old single string, it's actually an array of strings, which means there can be any number of them sequentially, see?
9. "System.out.println": These are not even a proper part of the language definition. They are objects that are accessed by loading in the standard Java libraries, and they actually have a bunch of additional code written to accomplish their task somehow, but you will never see that code. You just have to accept that it will work as a "black box" that does what you expect. And then there's the idea that "System" contains an object called "out" which has a method called "println", where even the last word is not as easy to understand as plain old "print".
   
10. All the syntax: This is probably second nature to every programmer by now, but just try to think about how you would explain and reinforce the idea of all the funny characters and when to use them. Quotation marks must signify string literals. Parentheses are required for both declaring and calling methods. Semicolons must end all statements, but NOT the method declaration (I don't know for sure if he ever saw a semicolon before). And, again, what the dots mean in between "System", "out", and "println".

That's quite a lot to bite off just to write two words. And by the way, when I try to get into inputting text, the proper format will be something like this:

String name = "";
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(input);
try {
name = reader.readLine();
} catch (Exception e){};

Compare that to

INPUT "Input name: ", name$

in BASIC, and

$name = <>;

in Perl.

Nevertheless, we heroically slogged through that stuff, discussing some parts in detail and skipping over other parts. Then we finally got to String variables.

No input yet, and no kind of string manipulation or concatenate. Just

String name = "Ben";

followed by

System.out.print("Hello ");
System.out.print(name);

Had a tough time getting him to see that the second print statement would print "Ben" rather than "name," and why.

As far as I can tell, I still have his attention and he wants to keep at it. He would like to write a graphical game, but I told him he has a lot to learn about text-only programs first before we can start to cover that. I know a lot of graphics, but much of it requires knowledge of not only Cartesian coordinates but also trigonometry. Believe me, I'm not touching trig.

A couple of open questions for readers:

1. Was it a mistake to start in Java?
2. If not, why not?
3. If you were being introduced to programming for the very first time, which language would you want to be taught first?
4. Crazy thought: Ben has a bunch of favorite sites stuffed with Flash games. He even said that he wished he could make one someday, which prompted me to say that it's too advanced for now. I have never learned Flash myself. Is it easy? Is it free? Would it be better or worse than Java as a "first time" language?
   

Angle math

I've got a new applet posted on my web page, which I wrote for my son Ben. He is seven. It is a demonstration of how angles work. You can drag the points of the triangle around, and it will continuously update the display of numbers showing what angle is formed at each point. It also gives a little readout showing that the three angles will, indeed, always add up to 180 degrees.

I like to do a little graphical application every once in a while just to stay in practice. There are a lot of concepts from trigonometry that have to be applied. Debugging graphics is sometimes a tricky affair, because if you don't do the right thing then you might wind up with nothing but a blank screen, or a line might appear wildly out of place. Finding the angles required remembering what sines and cotangents and such represent. (SOH CAH TOA! That's one that never leaves your memory, but I got sin and asin mixed up for a while.)

I also had to fudge the numbers a little bit. For instance, one angle might be 70.14 and another might be 50.34. The third angle should be 59.52. However, if you reduce those to one significant figure, you find that 70.1+50.3+59.5 = 179.9. So I had to fake the third angle (a3) as displaying 180-a1-a2.

The hardest challenge came after I decided to change "nearly" right angles into true right angles. Notice that if you drag one corner so that it forms an angle between 80 and 100 degrees, it will automatically snap to the correct position so that it is 90 degrees. I had to put some thought into making that work, and here's the solution I wound up with.

1. Write an expression of the line segment opposite the point being moved.
2. Find a vector perpendicular to that line.
3. Project the moved point along that vector to find where it intersects the opposite segment.
4. Find the actual distance that the point must be from the segment in order to make a 90 degree angle.
5. Move the point there.

I had originally used only a "Point" class and a "Triangle" class to represent the problem space; I soon realized I needed a "Vector" class as well (one which could be used to offset a point, normalized, reversed, or made perpendicular to another vector). Then I had to make yet another class, "Line," in order to properly calculate where intersections can be found. I borrowed a lot from this page, and found out just how long it had been since I needed to do that math -- I had a totally incorrect idea of how a line formula is expressed.

Basically the key to correcting your math mistakes -- and I made a lot! -- is to create either a printout or a visual representation at every step. For instance: I think I've normalized the vector correctly, better print out the coordinates and make sure the length is really 1. I need to draw an extra line to make sure it really goes through this point. I need to draw an extra point to make sure it really intersects that line. Do these two lines LOOK perpendicular to me? And so on.

If I had remembered the math better then some of this rigor wouldn't have been necessary. But really, caution and constant testing while coding eliminates the need to be a perfect math whiz. Coding is both theoretical and experimental, you see.

The Chess Master And The Computer

Garry Kasparov On Chess Metaphors

Thirteen years after Deep Blue beat him at chess, Garry Kasparov has written a long, thoughtful article about humanity's search for a meaning behind the event. Manages to cram in quite a lot of insights about both artificial intelligence in general, and the way the game of chess has changed among human opponents. As someone with a small fondness for chess and a large fondness for AI, I enjoyed it a lot.

There have been many unintended consequences, both positive and negative, of the rapid proliferation of powerful chess software. Kids love computers and take to them naturally, so it's no surprise that the same is true of the combination of chess and computers. With the introduction of super-powerful software it became possible for a youngster to have a top-level opponent at home instead of needing a professional trainer from an early age. Countries with little by way of chess tradition and few available coaches can now produce prodigies. I am in fact coaching one of them this year, nineteen-year-old Magnus Carlsen, from Norway, where relatively little chess is played.

The heavy use of computer analysis has pushed the game itself in new directions. The machine doesn't care about style or patterns or hundreds of years of established theory. It counts up the values of the chess pieces, analyzes a few billion moves, and counts them up again. (A computer translates each piece and each positional factor into a value in order to reduce the game to numbers it can crunch.) It is entirely free of prejudice and doctrine and this has contributed to the development of players who are almost as free of dogma as the machines with which they train. Increasingly, a move isn't good or bad because it looks that way or because it hasn't been done that way before. It's simply good if it works and bad if it doesn't. Although we still require a strong measure of intuition and logic to play well, humans today are starting to play more like computers.

More on gambling and random seeds

I always appreciate it when people write in with questions about something I've posted before. Gives me an excuse to keep this blog at least somewhat active.

Joe in Illinois writes:

Enjoyed reading your article on google regarding how to set a seed and randomness. Would different seeds contain different overall results. For example, some people would argue that a simple Jacks or Better video poker game returning 99.54% (in the long run, whatever that is) is still not purely random because the maker must still set this % ( over time), So would/could some seeds produce more winning combinations, maybe with fewer overall winning numbers in the seed. Players would not recognize one seed starting or ending. The next seed would/could have say, only 16% of winning combinations. Some people are overly concerned with this RNG, I say it's just doing its job, running constantly. But I also think that the player should hope for a positive seed, along with some luck and knowledge.

The short answer is, yes, different random seeds would lead to better or worse luck. But in the long run, with a good random algorithm, it wouldn't matter to you. Hoping for a "good" string of numbers coming from the RNG makes neither more nor less sense than hoping for good luck when you sit down at a physical card table.

Look at it this way. If you take a video recording of your session at a poker game, obviously you'll draw more good hands than bad hands sometimes. If you took different videos on successive days, and later you compared the tapes, then you could say "Oh look: on day one I had a lucky streak, and on day two I had an unlucky streak." But that's just the way random numbers actually behave: it's a rare string of randoms that don't show signs of patterns that appear meaningful but aren't.

Since the nature of a correctly designed random number generator is to simulate real random numbers, of course an RNG will create those same apparent patterns. But as long as there is no way for you to reverse engineer the algorithm or figure out what the seed actually was, hoping for a certain pattern is not much more than superstition.

Another interesting thing to note is that the nature of probability is that the larger your sample set is, the more likely it is to confirm to the expected distribution. In other words, if you only play three games in a row, it's not entirely unlikely that you could get a lucky streak and win all three games. Of course, it's slightly more likely that you would lose all three games; but still, if you believe in luck, betting a lot on a small number of hands makes some sense. The longer you play, though, the less the game's outcome will look like a sequence of wild streaks, and the more it will look like a typical bell curve distribution of some sort.

Thus, if you play 5000 hands of video poker, you are almost guaranteed to gradually lose money at the expected rate, as very lucky or very unlucky streaks will tend to cancel each other out.

Ugly numbers in a heap

As I was saying, a good solution to finding ugly numbers would be to somehow enumerate only numbers which are known to be ugly, removing them from memory after they have been read. I couldn't think of the way to do that. Internet to the rescue.

Here's what you do:

1. Store the number 1 in a set.
2. Consider the smallest item, "n" in the set. That is counted as the next ugly number.
3. Add the numbers n*2, n*3, and n*5 to the set.
4. Remove n from the set.
5. Repeat steps 2-4 until you reach the desired ugly count (1500).

Each time you search for the next ugly number, you remove one number from the set but add three more, for a net gain of two. Thus, the set of numbers you are storing on each step i is (2*i-1). That's a manageable memory size. But there's still a snag.

Sets are unordered lists, and we want to always find the smallest number of the set as efficiently as possible. How do we do that? We can't just read every number in the set, or the problem scope quickly becomes O(n²). Can't have that.

Turns out there is an ideal data structure for handling this kind of thing, but it's something I haven't looked at since I was an undergrad. It's called a min-heap.

A heap is a special kind of binary tree, where every level of the tree is filled to maximum density. For instance, in a heap with 8 elements, you know that the top level has one node with exactly two children; each of those two children has two children (that makes 7), and the leftmost node at the third level has one child on the left.

The neat thing about using a heap is that because of its predictable structure, you can represent it using an expandable one-dimensional array. You don't have to mess with pointers or the other headaches of data structures. If you are looking for root.left.right, you just calculate the spot in the array and access element 4.

A min-heap is constructed in such a way that the children of each node are guaranteed to be larger than the parent node. In other words, the smallest value is guaranteed to be at the root, and each child of the root is itself a min-heap with the smallest element of that at the root.

(If I'm going too fast for you, speak up. I don't believe I've ever done a post specifically on binary trees, so maybe I should.)

In any case... you can do two things with a min-heap: add a new element, which is rapidly sorted to the right place; and remove the root element, which then moves the next smallest element into the root and fixes the rest of the heap so that it is still a min-heap.

This is exactly what we need. It keeps the cost of searching for the smallest known ugly number to O(log n), where n is the number of elements currently in the list.

So to recap:

1. Write your own min-heap class, which is the fun part. ;)
2. Add the number 1 to the heap.
   
3. Inspect the root of the heap, and count that number ("r") as ugly.
   
4. Add 2r, 3r, and 5r to the heap.
5. Delete the root.
6. Repeat steps 3-5 until you reach the desired ugly count (1500).

Actually it turned out that wasn't quite the answer, because you can get duplicate ugly numbers on the heap. For instance, in the second pass you add 2*3, while in the third pass you add 3*2, which results in multiple 6's on the heap. But that's easy to fix. All we have to do is change step 5 to: "Keep deleting the root until it is no longer equal to the last recorded ugly number."

And there you go. Small storage space, quick execution time, ignores non-ugly numbers, and finishes in 3 seconds easily.

SPOILER:

In case you wondered, the answer is 859,963,392.

Ugly numbers and prime numbers

The second wrong approach I tried taking to find ugly numbers was something called a Sieve of Erathosthanes. This was something that my dad taught me about in high school, and it helped me win a programming contest as a sophomore.

Here's where I should give a quick shout out to my favorite HS teacher, Thom Laeser, who I think might read this blog. Thom was kind of a Renaissance man as a teacher; across my four years in high school, I took one geometry class, two programming classes, and a journalism class from him. He also started the school's first Humanities course, which I did not attend. It wasn't until high school that started really programming (rather than just dabbling in BASIC), and I credit Mr. Laeser with giving me that extra boost.

When I was a sophomore, he gave all his programming students a challenge, which was to be the one who could write a program printing the most consecutive prime numbers within five minutes. This was 1990 and the computer lab probably was limited to 80386 processors or something.

It was clear early on that the contest was going to be between me and a senior. The next day, we both proudly came in with programs that printed all primes from 2 to MAXINT in well under 5 minutes. This was in Pascal, I think integers were 16 bit, so the highest number would be 65,536. Mr. Laeser shrugged and said that was very impressive, but we would have to keep going if we wanted to win.

So. Along the way, I had to learn to write my own large integer output, and also save space by representing numbers with bit manipulation instead of wasting entire "int" values on booleans. More importantly, I learned about the Sieve of Erathosthanes, which I mentioned before.

The sieve is a method for quickly weeding out prime numbers from a finite list of numbers. Here's how it works (simplified version): start with an array of booleans from 1 to, say, a million. The first true prime number is two, so cross out all multiples of 2 that are not 2; so, 4, 6, 8, 10, etc. Then we move up to three, crossing out 6 (again), 9, 12, etc. Next we encounter 4, but 4 is already crossed out, so we ignore it and move up to 5, eliminating 10, 15, 20, etc.

It turns out that you only have to filter on numbers up to the square root of the array size, which in this case is 1000 (sqrt(1000000)). After that, you know there are no multiples of 1001 because you would have had to multiply 1001 by something smaller, and hence already visited, to reach a million.

Long story short, I won the contest, but it was a grueling arms race for several weeks as we kept improving our programs and then "stealing" new ideas by observing how the other's program worked.

Sieve of Ugly

So that was a roundabout personal story, but I haven't told it here before so I thought I might as well get it out. And the point is that my second pass at solving the ugly number problem was to use a sieve.

Sort of a simple modification, really. I didn't just use a boolean array, because there are now three kinds of numbers: 1: prime; 2: ugly; 3: neither prime nor ugly. So I made it an integer array, where each integer stores one of three flags. All numbers start prime; then multiples of 2, 3, and 5 get marked as ugly. Then run another pass on all numbers above 5, marking their multiples as non-ugly.

Using integers was super-overkill, as an int is 32 bits, and I only needed 2 bits to represent my flags: 00=prime, 01=ugly, 10=non-ugly. What I found was that I couldn't sieve up to the 1500'th ugly number, because the array was so huge that I ran out of memory.

So first I changed it to an array of bytes (8 bits). Then, still not satisfied, I improved performance by writing some bit-manipulation routines to simulate an array of two-bit numbers using four numbers per byte.

It worked; I found the same number much faster than before, but still with a noticeable delay before the sieve finished running. 3 seconds was still way out of reach.

What next?

While I was coding the sieve, it occurred to me that it was a terrible waste of space to store ALL the numbers, both ugly and non-ugly, in an array until the entire program was finished. It seemed like there ought to be some kind of quicker way to figure out, given the current ugly number, what the next one in the sequence should be. At worst, I could maintain an array of only 1500 numbers to store only ugly numbers (instead of all numbers up to a trillion).

I wracked my brains for this method; I wrote down the factorization of the first 10 numbers or so, looking for a pattern, but couldn't find one. I'm pretty sure there isn't one, but I was on the right track at this point. I know because that's when I "cheated" by looking to see what other people had done.

And maybe they're smarter than me, or maybe they spent more time on it, but there is still a certain grim accomplishment in not having to reinvent the wheel.

There's a well known "hard" problem in computer science called the traveling salesman problem, which goes like this: You have a bunch of cities, separated by known distances. You have to visit all of them while spending as little time as possible in transit.

To solve this problem by brute force becomes impossible very quickly as you add more cities. So the best known approaches use short cuts; they use sneaky tricks that don't necessarily produce the "best" answer, but are guaranteed to produce a pretty good answer most of the time.

Anyway, I heard that some computer science genius was once asked how he would solve the traveling salesman problem, and he said: "I would put it on the back of a cereal box. 'Find the most efficient path through these points. Winner gets $100, mail your answer to the following address'..."

Well, that's one kind of divide and conquer solution right there. Hooray for the internet, though... now we don't even need cereal boxes.

Online programming puzzles and "ugly" numbers

Ran across this site while looking for general programming puzzles to stay in practice.

On the site, my attention was captured by this puzzle involving "ugly" numbers.

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 1500'th ugly number.

This isn't a particular hard puzzle if you brute force it. All you have to do is write an algorithm to determine whether a particular number is ugly or not, sort of like this:

while (num % 2 == 0) num /= 2;
while (num % 3 == 0) num /= 3;
while (num % 5 == 0) num /= 5;
if (num == 1) return true;

Then you can just loop through as many numbers as it takes, incrementing a counter as you find ugly numbers, until you reach 1500 numbers.

The problem with this approach is that there is a time limit of three seconds. The brute force approach requires you to do an increasingly long operation (dividing repeatedly to find the prime factors) on a series of numbers which turns out to be very large (I won't spoil it, but the answer is just short of one trillion). Early numbers are computer quickly; then it slows down so finding the 1500th number may take several minutes.

I confess I cheated to solve this puzzle. I came up with one other wrong approach after trying the brute force method, then went googling for discussions of this puzzle. As I hoped, I did find a protracted argument about the right way to solve it. One guy hit on a really clever solution, based on a data structure which I haven't used for years. It took me a few tries to implement, but it was very satisfying in the end.

I guess I could feel bad for "cheating," but I don't. I came close to finding the right answer, but really, if you want an optimal answer to a well defined puzzle then there's no harm in hunting around to see if someone did it better than you. Professionally, implementing a GREAT solution that you looked up is preferable to implementing a mediocre solution that you got with only the sweat of your brow. You can learn new tricks from other people that you'll have in your toolbox for next time.

As a tangent, I take the same approach to strategy games. I like to take my time and learn the rules of a game on my own, and I would scorn to look at a strategy guide during that period. However, there comes a point where you have a basic understanding of the rules and can improve much faster by considering input from others who have already mastered the game.

Anyway, more on the wrong approaches and the right one later.