Wondrous number graph

Like many great ideas should, my latest pet project was inspired by an XKCD cartoon.




Of course I recognized the graph right away. I never heard it described as Collatz Conjecture before, but this concept also makes an appearance in my very favorite book of all time, Godel, Escher, Bach. In a dialogue between Achilles and the Tortoise, they were referred to as "Wondrous Numbers," and Wikipedia confirms that both terms are acceptable.

After reading the cartoon, I started doodling my own graphs, which -- despite the convulted twistiness of Randall's picture -- are essentially binary trees, going downward from one. If you draw the left branches as multiplying by two, and the right branches as "minus one divided by three", then you may get a graph like this:

1
|
2
|
4
|
8
|
16
|...\
32...5
|....|
64...10

... and so on.

The tree is easy to generate. Of course, it's an infinitely large tree, so you have to decide which nodes to expand. The two main ways I can see to do it are:
1. Start with 1, balance the depth by always expanding the leaves that are at the least distance from the origin.
2. Start with 1, always expand the leaves that have the smallest numerical value.

So for example, in the tree above, I've used method 1. If I had used method 2, I would have needed to add 5, 10, 20, 3, 6, 12, 24,and 40 to the tree before I could expand node 32.

Now, obviously this tree gets large in the vertical direction faster than the horizontal direction at first; later on, when the branches increase exponentially, the opposite is be true. But when I tried sketching the graphs, I was annoyed by all the white space at the top. I thought the tree would look much neater if I started with the root in the upper left corner and tried to push the left nodes downward, and the right nodes rightward. So the above graph would be changed to something like this:

1...5--10--3--6--12--24
|../../
2.|.20
|.|.|
4.|.40
|.|
8.|
|/
16
|
32
|
64

and so on like that, giving me more space to expand toward the bottom right. (Hope that's clear.)

Once I was able to sketch this, I started writing it as a program, but currently haven't finished working out the algorithm to decide where in the grid to place each node. Basically the requirements are as follows:

1. You should be able to display any binary tree with this program (it doesn't have to be tied to Wondrous Numbers).
2. Root is displayed in the upper left corner.
3. Prefer to display children to the right of and below the parent, as much as possible.
4. The algorithm should eventually fill up all available space in a specified grid size.
5. The nodes should be as tightly packed as possible, avoiding empty spots.
6. Parents and children should be connected by straight lines, which do not cross. Failing that, fewer crossed lines is preferred.


I thought of a few different ways to accomplish these goals, but haven't been able to decide which one to focus on first. My first thought was just to place new nodes anywhere nearby, and then gradually move them out of the way as necessary when adding new nodes. This would require me to decide which nodes need to be moved, based on either position in the tree or position on the grid.

I also thought I might go with a hill climbing algorithm, where I just keep swapping nodes at random until the number of line intersections is decreased. However, I don't much like this solution, because calculating all possible intersections repeatedly could eat up more processing time than I like.

That's about as far as I've gotten. Any thoughts?

Adventures in junior programming, episode 2

Thank you, everyone, for all the great suggestions that you submitted to my previous post. As a result of all the recommendations, I decided to go ahead and teach myself Python. I'm sure Python enthusiasts will not be surprised to learn that I've found it... almost embarrassingly easy to work with. For instance, the Java program I listed:

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

And the Python equivalent:

print "Hello world"

Not even so much as a semicolon is required in this one, because Python actually enforces proper indentation and uses it to recognize code blocks. Since last week, I've checked out a book from the library and read much of the online tutorial, and implemented a simple object-oriented puzzle game that I used to assign to my C++ students. A special "Thank you" goes to Shawn, who volunteered to be my Python guru and code reviewer all week.

So the real question is, how would Ben take to it? I sought the answer to that question over some wings at Plucker's last night. (Before I get to the coding part, let it be known that Ben actually tried one of the hot ones, and pronounced it good. Then he stuck to the mild and drained two root beers.) We did some stuff before the food arrived, and after that we moved to a Starbucks inside a Barnes & Noble and got hot chocolate.

Python works pretty well as a first time language for a few reasons. It is an interpreted language, so you can run it line by line. To facilitate this, there is a command line interface. Type print "hello world" at the prompt and it gives immediate feedback. In fact, it's not even necessary to type "print", as the CLI will assume that if you type an expression without context, you want to see the value of that expression. Type 2+2 and the interpreter dutifully spits out 4. I got to work in some easy math lessons first by making him guess what the result was going to be as I typed various expressions.

After that I re-introduced him to variables. name = "Ben" is all you need to declare a string, and then you type name at the prompt and the interpreter returns 'Ben'. I pointed out the difference between typing name and "name", as one would print "Ben" and the other would print the string "name."

So next, input. By now we are getting to the point where the command line would just get in the way, so I start up a text file and type a two line program that says "Enter your name: "; you type something and then it says "Hello, [name]". Ben likes to try and confound the computer, so he banged out a long gibberish string, and then thought it was hilarious when the computer treated that as a name too. Lesson: computers aren't smart. They can only do what you tell them.

I demonstrated a simple "if" statement by writing a five line program where you are supposed to guess the secret number. (It was 17. No hints, just a magic number in the code. Maybe I'll work on the "higher"/"lower" binary search game next time.)

At this point, I explained, you know all the basic things that a computer program can do. Input, output, and logic. The rest is all variations on that from now on.

We did some more math, and then Ben said he wanted the computer to print the number googol. He was starting to type in all those zeroes, when I said "Wait! Don't count the zeroes!" Then I got to make a "for" loop, which starts with the number one and multiplies it by ten a hundred times.

That managed to impress him, but he was surprised that a hundred zeroes didn't take up more screen space. I said "Ah, but here's the great thing! Instead of 100 zeroes, can you change one thing in the program to make it a thousand?" After some thinking, he got it.

But then he insisted on upping the number to a million zeroes, which didn't work so well. The loop's too long, the computer got stuck calculating the number in the loop and didn't print anything. Lesson: computers are fast, but they don't have infinite speed. You have to write your programs in order to avoid making them get stuck.

I then showed how we would modify the loop to just print sequential numbers on each iteration. I was going to show how the computer can write progressive doubles, but at that point my laptop's battery ran out and we couldn't find a free plug in the entire bookstore, so we browsed some books and called it a night. Total time on programming was a bit less than two hours.

Ben's into it. We'll see how it goes next time I get a chance at him.

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?