Castles of Air

Troubleshooting my own user idiocy

2011-10-12T08:32:00.004-05:00

Random dumb tech story: For months my computer microphone has had a lot of loud static on it. Every time I say something in a game like Left 4 Dead 2, people complain and tell me not to talk again.

I finally got around to investigating the issue, which involved unplugging things, looking at the sound controls, etc. I was bewildered to find that the computer was recording noise even when the mic was unplugged. Then I realize: I have a USB webcam that I rarely use. It's plugged into the back, it has its own built in mic... and it's hanging behind my desk RIGHT NEXT TO THE FAN.

Everything's crystal clear now.

Operation HackMaster Crit Tables, episode 2

2011-09-19T10:49:00.002-05:00

Now that I've explained what data structures are for, I can finally explain how I approached the problem of deciphering those ponderous HackMaster tables.

First of all, I discovered to my dismay that the tables were only available in the form of PDF files -- images, not text. Just as I was about to tell my friend that I didn't want to waste time converting six pages of tiny print to very usable data, my lovely assistant Lynnea (the aforementioned fiancee who actually plays the game) stepped in and volunteered to do it. This is one thing about her personality that I've never been able to understand, but she loves doing data entry, filling out forms, etc. I think it's some kind of OCD thing. But for whatever reason, she's extremely enthusiastic, diligent, and thorough about this kind of work. And by the way, if you need this kind of work done, she's available to hire! Ask me for a resume. :)

With this powerful ~~slave~~ human resource at my disposal, I wrote up a few sample lines of text in a spreadsheet to show how I wanted them, wound her up and let her go at it. She cranked the rest out in a surprisingly short time. I then converted the results to standard comma-separated value format, some of which you can download from here: Hacking weapon table part 1; List of effects. In case you're not familiar with them, .csv files are a generic text-only format which can be read in a spreadsheet program like Excel, or any standard text editor.

Working with just my sample rows, I set out to work out what the abstract properties of the data were. The first thing to consider is the way a body part is selected. In the hacking weapon table, you can see that if you roll a 1-100, you get hit in the "Foot, Top"; if you roll 101-104, you get hit in the heel, 105-136 is Toe, and so on.

This is like a hash table, almost, but it's not one. If it was a hash table, you'd usually have one body part per number: 1 -> Foot Top, 2 -> Heel, and so on. Here, we're working with a range of numbers corresponding to each lookup value.

I decided to start with a generic lookup table, where you start with objects which contain a "low" value, a "high" value, and a generic object which can get returned from the lookup. The declaration looks like this:

public class RangeLookup<T>
{
   private List ranges;

   private class Entry
   {
      protected T item;
      protected int low, high;

      public Entry( T i, int l, int h )
      {
         item = i;
         low = l;
         high = h;
      }
   }
   ...
}

In Java using the "<T>" notation means that "T" could be anything. Even though I wasn't going to be using this lookup table more than once, I like to keep structures as all-purpose as possible. That's partly because I might want to reuse them in the future, and partly because I want to be able to test how the component works without making it dependent on the equally complex item which will be retrieved by the lookup.

Every structure needs an interface -- a means of communicating with it that only does what you want and hides the guts of it from the rest of the program. I created an "addEntry" function to the RangeLookup class, so that you could insert a new entry with a high, a low, and a retrieved object of type T. Then I added a "lookup" function where you send in a number, it gives you an object. In my implementation, the lookup function simply walks through all of the possible results and checks whether the requested number is between the high and the low. This would be inefficient if there were going to be a lot of entries, so I might have come up with some kind of hashing structure or tree search; but since there are only about 20 or so body parts, it wasn't worth the extra effort and runs fine as is.

After verifying that this was working right, I created the following additional structures:

Looking at the Effects table, it is a basic mapping (in my case, placed in a HashMap) from one string to another. You put in the code "f", and the resulting effect is "fall prone and drop items". So, I created a simple object called an "effect," containing "key" and "description."
It's a bit more complicated than that, though. Often the table will contain numbers, but the effects will contain only the symbol "X". For instance, if the table says "d4" then the relevant effect is "dX", which means "reduce Dexterity by X". Therefore I made another class called an "Outcome," which contains an Effect AND a number (which may be zero if it's not necessary).
I made an EffectTable, which implements the HashMap of Effects.
Almost ready to create an actual table object, I first made a class called "CritTableEntry." This represents a cell in the table. It contains: a low roll, a high roll, the name of a body part, and a List of effects (because each cell may result in several outcomes, not just one).
A CritTable class to put them all together. This class has an addEntry method and another method for retrieving the entries.

As a final step, I created a "Reader" class which did the heavy lifting of reading and interpreting the CSV files and adding one row at a time into a generated table. I don't like to reinvent the wheel, so I googled class libraries which would read CSV files and interpret them as lists. I settled on using OpenCSV. I could have written my own parser, but when the task is as common as reading a CSV, I tend to assume that somebody has already done all the work before me and has already been through the process of making all the mistakes and catching the bugs which come up.

Notice that none of these objects deals with input and output directly. It's preferable to test each component of your program separately as much as possible BEFORE trying to decide what kind of user interface to make. Your interface should be tailored to the problem space. As it turns out, I wound up creating several different interfaces before I settled on created a web application. I'll discuss these concerns in a later post.

When testing your data structures it's a good idea to create unit tests. A unit test is a small, self contained application which is designed to test one thing at a time. You need to think about every possible way that your program might break, create a unit test for each one, and make sure that it works right at the boundary conditions.

Off the top of my head, here are some boundaries of the crit tables that needed to be tested:

Spot check several "body part" rolls with random(ish) numbers and see that the returned information matches the table.
Spot check several "outcome" rolls in one row and see that the returned effects match the table.
Test the boundaries of some rolls. For instance, on the table I linked, "4301-4492" corresponds to "Arm, upper inner", and "4493-4588" corresponds to "Elbow". Therefore I have to make sure that a roll of 4492 returns a different part from 4493.
Test when happens when the body part roll is 0 (invalid), 1, 10000, and 10001 (invalid).
Test what happens when the effect roll is 0, 1, 24, and 25.

Keep all your unit tests around forever. If something breaks, that's a quick way of figuring out which part is not working. If it's a problem with your data model rather than your user interface, the unit tests will catch it.

Next time I'll be talking about all the different ways of making an interface on the same models.

A bit about data structures

2011-09-14T17:16:00.002-05:00

I wanted to write another HackMaster post, but what I wanted to write about was the way I approached deciphering the data in the tables and converting them into data structures. Then I skimmed through some older posts looking for reference points about data structures, and it occurred to me that I've never written any. In order to provide a foundation for the rest of the HackMaster breakdown, I'll have to digress and talk about structures in the abstract.

Whenever you are presented with a problem of modeling some numbers in conceptual space, the first thing you have to figure out before you write a single line of behavioral code is what kind of data structures you are going to use. Going all the way back to the beginning of this blog, I've emphasized the importance of considering the efficiency of your design and the effect that it has on the Big-O performance of your program. Thinking about proper data structures can buy you a lot of speed, and it can also make it really easy to visualize your program in small chunks as the complexity increases.

So what's a data structure? The first thing programmers learn is how to use variables for individual chunks of information, like this:

int x = 3;
String str = "Hello world.";

(Technically, of course, a String object in Java is a whole bunch of characters, which makes it a data structure in itself. But the nice thing about object-oriented programming is that you don't have to think about it if you want to.)

To understand data structures, consider an array. An array is one of the first slightly more advanced concepts that a beginning programmer will run into. Instead of storing just one integer, it can store several. For example, here's a simple representation of part of the fibonacci sequence:

int[] fib = new int[10];
fib[0] = 1;
fib[1] = 1;
fib[2] = 2;
fib[3] = 3;
fib[4] = 5;
fib[5] = 8;
fib[6] = 13;
fib[7] = 21;
fib[8] = 34;
fib[9] = 55;

When you create a single "int," you're asking the program to set aside a chunk of space in memory, large enough to hold one number. When you create an array like this, you're asking the program instead of set aside a bigger chunk of memory ten times that size, plus (for some languages) a little bit of extra information about size constraints and such.

But arrays can be wasteful. What if you want to set aside space that sometimes houses a hundred numbers, and sometimes houses just a few? You could create an array of size 100, but most of the time that space would be wasted. That's when you want to use a linked list, where you ask for new memory only at the moment that you actually need it.

I'm not dedicating this whole post to the implementation fundamentals of lists, but interested beginners should go check out the Wikipedia article to find out how this works. (Sidebar: While relying on Wikipedia for information about controversial topics is often unwise, most of the technical topics that are covered are really good.)

Besides linked lists, there are lots of other data structures that you can use depending on your situation:

A tree (which may or may not be binary) will hierarchically organize information for you, much like the folder structure on your computer does, shortening the search time as long as you know where you are going.
A hash table or map is a structure which will find a value associated with a key, usually very quickly. An example would be a dictionary search: you supply a word, and the program would retrieve a definition.

You can write your own versions of these structures, or if your language supports it, use predefined classes that create common structures.

Understanding what purpose the various structures serve, and when to use each one, is a very key skill in programming interviews. Often when you are asked "How would you solve this problem?" the best answer is not to blurt the first notion that comes into your head, but to start applying data structures to model the problem space: lists (or specifically, stacks or queues), trees (binary or otherwise), tables (sometimes you can just assume the existence of a database, which is centered around associative tables).

When I hear a problem that lends itself to this, I usually make a beeline to the whiteboard and start thinking out loud: "You're asking about a list of items, so let's describe what's in an item first... then build a linked list out of items..." Then I'll be either writing code to illustrate what I'm thinking, or (if the interview is shorter) just sketch out diagrams so that the interviewer understands the description and will probably accept that I know how to implement it.

Software is built a piece at a time. If you start explaining how you visualize the problem in your head, you can give a much better insight into how you think than if you just start solving the problem directly. In fact, if you start off strong with this approach but then go off on the wrong track, often the interviewer will be eager to guide you towards his concept of the solution because he's being carried along with your thought process. This often changes the dynamic of the interview entirely. Instead of being a room with an interrogator and a suspect, the interviewer may start thinking of himself as your ally and not your judge. And that's exactly where you want to be when you're looking for work.

Digression's over. Next time I'll illustrate this when I get back to decoding HackMaster tables.

Operation HackMaster Crit Tables, episode 1

2011-09-08T19:51:00.000-05:00

This post is about a project I recently did for fun. Although the project itself has extremely limited application, it inspired me to do something I've been meaning to do for a long time, namely upgrade the web server for my apollowebworks.com domain to something which supports Java applications with Tomcat. (I chose a company called Arvixe based on scanning the features they offer and reading a bunch of reviews. Shout out to my boyz at Arvixe!)

Because I'll be touching on a wide range of topics, I'll split them up into multiple posts, and that should keep me from neglecting this blog for a little while. So, partly to tell you what's coming and partly just so I can keep track for myself, here's a road map of the topics I plan to hit with this discussion.

General geekery about using programming to automate complex tasks.
Building a project from the ground up, starting by visualizing the data structures instead of just diving in blindly.
How separating interface from implementation makes it easier to translate your program to multiple platforms.
Good riddance to the bad old days: How the web has made program content delivery easier.
A primer for noobs on what web servers do, and why I bought another one.

First let me explain the problem. My fiancee, Lynnea, has gotten into paper-and-pencil roleplaying games. She has been running a light Dungeons & Dragons campaign occasionally for me and my son Ben over the last few months. She also plays with a group of friends one night a week. For my part, I've played RPGs a few times before but never been a strong part of that scene, so I just listen to the stories of her sessions. Currently they're playing with a rules system called "HackMaster."

As I understand it from skimming a few chapters of the rulebook, HackMaster was written by someone who hates doing things the easy way. When D&D was first published in 1974, it was at first an ever-expanding set of complicated rules involving tons of die-rolling for all kinds of special situations. Or as a German exchange student my family hosted in high school put it, "D&D isn't a role-playing game, it's a roll-playing game." Har. Har. Very droll, those gamers. (Oh hey, how are things going, Max? ;)

Still, as the years went by, D&D started to reverse the trend and become more streamlined, or so I've heard. The latest release, fourth edition rules, was clearly heavily influenced by World of Warcraft, and reduces a lot of the unnecessary choices in favor of more interesting combinations of focused options.

The HackMaster author just hates that. Not that I would recognize the difference, but I have the impression that if anything, he's aggressively chosen to make every little action even more complicated than it would have been under old-school D&D, to the point where a party can spend thirty minutes meticulously checking a single room for traps before seeing any combat. And the critical hit tables are an utter monstrosity.

Critical hits (or "crits") for you non-gamers, means that for every attack there is a chance (1 in 20 under D&D rules) that it will be a super-strong attack which does extra damage. In WoW, this is handled automatically by the game; you can build up gear that will increase your crit chance, but usually there's a flat formula that says "If you crit, your strike does twice as much damage." Rules in 4th edition D&D are pretty close to the same.

Not HackMaster.

In HackMaster, you roll a number between 1 and 10,000 for the body part where your blow lands, and there are all kinds of "realistic" outcomes that result if you land a powerful blow on that body part. Furthermore, rolling a 20 is just your cue to pull out a ginormous, six page tables full of teeny little numbers and two accompanying rules pages. You then roll another number that might range from 1-24 to see just how badly your crit hurt the monster (or the monster's crit hurt you).

For instance, if you get hit on the top of the head, the crit damage can range from "8 extra damage" to "twice normal damage AND you lose some hit accuracy AND you lose some dexterity AND you fall down and drop everything you're carrying"... to "brain goo." Do not pass go.

Each one of those individual clauses, by the way, is represented in the table by a little symbol like "dX" which you have to look up on a smaller table of effects. I think you have to look at a sample to see what I'm talking about.

(Click for a larger image.)

Not to put too fine a point on it, this sounds like a game that I would personally hate playing. But no accounting for taste, you know? Even so, problems of managing huge sets of data are piles of fun to solve with a computer. NO, that's NOT sarcasm, you non-programmers, that's fun. Shut up.

So when the DM tentatively asked if it would be possible to write a program that could handle the die rolls and just spit out some nice, clean output, I said "Piece of cake!" I wouldn't even accept his offer to pay for it. Just like when I wrote a Sudoku solver, sometimes figuring out how to automate gameplay is more fun than actually playing. (Disclaimer: I used to claim that Sudoku is a fun math problem and a crappy game. Now I like playing it. It's my Android Evo's fault, damn it... it's the perfect game for a handheld, and it has built in strategy advice. Once I started improving at harder puzzles, there was no escape.)

And so it began.

To be continued...

Recruitment spam

2011-08-23T17:00:00.001-05:00

A new category of spam has been getting worse and worse. It's recruiters. They are tapping me with impersonal job requests (i.e. "Dear Technology Professional..."). Some of them are even a bit close to my skill set, but the jobs are nothing I would ever accept. Most recent was a six month contract in Kentucky. Honestly, even if I did have any desire to move to Kentucky, I wouldn't pick up my life and move for a six month contract..

This kind of spam is particularly insidious, because I can't just label it as spam and then let the GMail filter handle it... because it kind of resembles message that I would actually like to read in the event that I need to find work again. Honestly though, it's despicably lazy of the recruiters. They're just blasting everyone they can find, probably using a spider to automatically scan resumes and send out the messages without regard for location or a very good match. Argh.

On learning to love your users, who are idiots

2011-08-01T15:40:00.007-05:00

In the process of discussing error checking in the comments section of a recent post, I flippantly remarked that "all users are idiots." This is a sentiment that I expect all veteran programmers will have encountered or stated themselves on some occasion.

From a new programmer struggling with this problem, I hear this: "This would be a heck of a lot easier if users just weren't idiots." And of course, that is something we all wish. But then again, if we didn't have to assume user idiocy, we wouldn't be writing programs.

There's a fundamental difference between constructing a program and writing a novel or painting a picture. For static forms of media, you only have to create one thing from beginning to end. Once you've finished writing your book, it's over. For better or for worse, your characters have finished interacting with each other. They've said what they have to say. People will either like it or not like it; they may debate endlessly about what your words or images "really mean," but they can't affect its behavior.

Unfortunately, programs aren't like that. Once your release your program into the wild, users get to do whatever they want with it. And if they do something utterly crazy and your program breaks, they'll blame you.

Murphy's Law ("Whatever can go wrong, will") was written by an engineer in the 19th century, but it is used most by software engineers. It's not that everything possible will go wrong every single time your program is run. It's just that if you have millions of users (which you will if you are successful) then even a very small chance that one person will do something unexpected, must necessarily magnify into a virtual certainty that somebody, somewhere will find a way to blow up your program.

With that in mind, writing a program is just as much about covering every possible angle of what some idiot user might do to you, as it is about creating a pleasing presentation when the program is Used As Intended.

As a gamer, I have heard several interviews with voice actors who are veterans of film or television, but new to performing voices for video games. The universal sentiment seems to be "This is the craziest thing I've ever had to do. You have to perform a dozen different lines for every single scene, and they're not just different takes for the editor to select from. They're ALL USED in the game. I'll have to perform a scene featuring my dramatic death, and in the very next scene I'm alive again. I'll have to answer the same question five different ways, just in case the player decides to harass me by asking my character over and over again." And so on.

So, because we must cover every possible use of the program, we create elaborate error scenarios and use all kinds of tricks to keep the user on track. One way to handle user error is to simply give the user very strict instructions, like this: "You MUST TYPE A NUMBER from 1-100, and if you do ANYTHING ELSE, then the program WILL CRASH and that is YOUR RESPONSIBILITY." That's not very satisfying, though. People make mistakes, even people who are not idiots. It's much nicer to recover gracefully from an error. At every step, you're asking yourself: "What can go wrong here?" And then you add a clause to your program: "If bad thing xyz occurs, say something polite to guide the user back on track, and try it again."

Often, an even better solution is to tie the user's hands so he can't actually make the mistake in the first place. For example, slider bars and drop boxes exist exactly so that the user can pick an integer from 1-100 without the capability to do something stupid.

Obviously, it takes a lot of work to write a bulletproof program, and the more thoroughly you prepare for bad user behavior, the harder the work is going to be. Often you have to strike a happy medium. The smaller your audience is, the less effort you have to put into mistrusting your users. If you are just writing a program for yourself, it's probably less work to try and give good input than to write error handling routines.

Also, the more general the application, the more you have to just let the errors happen, and your only responsibility becomes to make sure the errors don't cause a crash. For instance, if you're writing a calculator program, you can't just stop all operations that divide by zero. The user might just DECIDE to divide a number by zero. You just have to tell him he made an illegal operation, and move on to the next step.

When you write a program, you're not designing a static thing for people to look at. You're designing a universe of possibilities to cover all uses. The more time you spend thinking about what an idiot might do, the better you can guarantee that you will make it a pleasant experience for those who are not idiots.

Programming puzzle: Testing probability

2011-07-14T17:04:00.004-05:00

I've been using the comments section of the previous post as a sort of impromptu classroom for my friend James to work out simple programming problems. Since I've got nothing else in particular going on with this blog right now, I might as well keep it up and post a more interesting (novice level) problem. So here it is.

One of my favorite puzzle books, "Aha! Gotcha" by Martin Gardner, used the game of "Chuck a Luck" to illustrate some basic probability concepts. You can read the rules and history here.

In a nutshell, the player picks a number from one to six and then places a $1 bet and rolls three dice. If your number doesn't come up, you lose the dollar. If it does come up, you keep your dollar and win $1 for each die that shows your number.

A program which implemented these rules might look like this:

What number do you bet on? 3
You rolled: 4 6 2
You lose $1!

What number do you bet on? 2
You rolled: 2 1 5
You win $1!

What number do you bet on? 1
You rolled: 1 3 1
You win $2!

Gardner concocted a rationalization for a gambler who believed that the game favors the player, and then challenged the reader to show why the argument is faulty. But if you actually write such a program, you could show empirically the the game is stacked against you.

I suggest that you do this in four phases.

Phase one: Implement a program that has output similar to the above.

Phase two: Keep track of how much total money the player has won or lost.

Phase three: Ask the player how many games he wants to play automatically. Like this:

What number do you bet on? 1
How many games do you want to play? 10
[optional: display the outcome of each game]
...You lost a total of $3!

Phase four: Have your program play a very large number of games, and calculate the average amount you lost per game.

Let me know how it goes.

Adventures in junior programming, episode 3

2011-07-07T20:43:00.005-05:00

Haven't been posting on this blog much lately. Since I last posted I got a new full time job at a high tech marketing firm, and also taught myself the fundamentals of both Android and iPhone programming. Interesting stuff, probably good fodder for a future post. But for now, I'd like to go over recent efforts to teach my son more programming.

We let it slip during the school year but we've picked it up again over the summer. We're doing about an hour of work several nights a week. It seems like teaching a nine year old to program irregularly is like pushing the stone of Sisyphus, since every time we take it up again, I have to re-teach concepts that seemed to stick the last time but didn't. Nevertheless, my feeling about programming has always been that you have to learn to "think like a programmer" first, and once you have burned this style into your memory, it becomes much easier to pick up any language or platform in existence.

So what is the core of thinking like a programmer? As far as I can sum up for a kid, it boils down to a few key elements which need to be practiced over and over under a variety of conditions:

Output
Tinkering with variables
Input
Loops
Conditionals
Logical operators
Functions and classes, which fall broadly under the category of "splitting up the work into manageable smaller chunks."

I've fallen into sort of a systematic bootstrapping pattern of teaching, which goes something like this. I have milestones in mind for things Ben should know how to do well, and they should be second nature. The current milestone is: "Write a Python program that counts to ten." Once he can do this without hesitation and without complaining that he needs more hints, we'll bump it up and move on to another milestone.

Each session, I ask him to hit the milestone. If he can't do it well enough, I'll point out what he's missing and go over how it works again. After we get through this, if it's appropriate, I'll introduce a new concept, which we'll drill in the future until that becomes the new milestone.

I've also been making him follow the program logic step by step. It's not as intuitive as you might think. For instance, I ask him to explain HOW the computer goes through the stages of counting to ten, and this is the kind of response I'm looking for:

"First I set the counter to one. One is less than ten, so I enter the loop. I print the counter value. Then I add one to the counter, making it two. Now I return to the beginning of the loop. Two is less than ten, so I enter the loop..."

The kind of response I get takes frequent shortcuts, like "I keep doing that until it's ten." That may be technically correct, but it doesn't capture the essence of thinking through every step, which is critical to catching bugs. If you wind up writing a program that only counts to nine, or goes into an infinite loop, you can keep modifying lines until you get lucky, but if you can see what it's doing at every step, then you're less likely to make mistakes in the first place.

I don't even see the code. All I see is blonde, brunette, red-head...

Programming can seem tedious and repetitive, but at its best you get those "light bulb" moments when it's suddenly crystal clear what you want your program to be doing and how. And sometimes it's even more fun to write the code that solves a puzzle than to grind out the solution on your own.

My very late entry to mobile computing

2011-02-28T11:30:00.009-06:00

I'm starting this post writing on my new Android phone, though I may not have the patience to finish it on this tiny virtual keyboard. (For the record, I'm using Swype to type.)

So I admit, I'm a latecomer to Smart Phone technology, having ignored the iPhone almost completely when it was in the $500 to $600 range (apart from playing with a friend's every so often). I don't much regret waiting. Although I am a geek to the core, and love my techno toys as much as the next 21st century man, I am also a cheapskate at heart and don't like to overpay for the privilege of early adoption. My problem with the phones has been not just the initial cost, but the ongoing charge on the phone bill. In this case though, after developing a healthy case of envy from seeing my dad's Android, as well as plenty of coworkers playing with their phones, I have succumbed. The price has dropped substantially, and some of the early technical problems that were apparent in the iPhone (one unreliable phone carrier, shortage of third party apps, and various other issues that you'd expect with a brand new technology) have ceased to be a concern.

The highest tech handheld device I had before a couple of weeks ago was an iPod Nano that was a few years old, and the main interface was the five button scroll wheel. Many years ago I had a somewhat Palm Pilot with a miniature keyboard and a wifi connection, but it broke too many times and I couldn't justify dumping so much money into it. When my regular phone company offered me a deal on trading in my old (cracked) phone, I realized I could replace both phone and iPod in one shot, for less than an iPod Touch costs, and also get a fully featured GPS system. So I was sold.

So. Welcome, belatedly, to the 21st century. The internet now exists more or less everywhere. This is actually pretty close to the way things were going anyway, with free wifi connections being available in every household and classroom, and more and more public buildings and restaurants. The difference is that if I get lost on the freeway now, or want to look for things in my immediate area, all I have to do is park. I have a full suite of tools and it doesn't require me to go home or carry a laptop in order to access them.

I've been using personal computers since I was eight years old, and developing software for nearly as long (BASIC, then Pascal and C in high school). At that time, everything was pretty much self-contained. Last year I reposted Tim O'Reilly's talk on the "Internet Operating System." Part of what Tim was talking about was the fact that programs now tap into a massive infrastructure of other programs that already do stuff, and that makes it easier to just hook it up into new applications without rewriting everything.

For instance, Google did not have to write a new map program just to get navigation to work on the Android. Due to the success of Google Maps and Google Earth, they've been harvesting information for years already, from satellite photos to detailed street maps to (as I am now seeing) data mined patterns indicating exactly where and when traffic is heaviest on each day of the week. So the Android Navigation program mainly represents a new interface on an existing product.

It is, of course, neat that my Android has lots of local space. Eight gigabytes of memory totally dwarfs the computers we had in the early 80's. Our first computer had no hard drive, and had to read everything off of floppy disks with a capacity of 140 KB. Our first hard drive had, I think somewhere around 10MB of space, which seemed like a huge amount of storage at the time. My Android could host that hard drive's contents 800 times, while fitting comfortably in my pocket, and doesn't make all that noise.

But as cool as that is, it's important not to underestimate the power of having your programs tap into information that's just floating around in the air. The accumulated map and satellite data from Google obviously would not come close to fitting in a phone. But I only need a small amount of local data at any given time to support the navigation system. Everything else is handled by services hosted on web servers that are "out there" somewhere, and supply just as much data as I need to find my way around at the immediate moment.

This technology, which seemed so cutting edge and exotic to me a couple of years ago is now, apparently, a commonplace app. I already downloaded it. You hold a bar code up to the phone, and it scans it, and then in a few moments you can pull up Amazon reviews and comparison shop. This actually makes physical bookstores more interesting again, as one of the main reasons I liked shopping online was the ability to jump to all the associated data that was available.

Anyway, I'm pretty enthusiastic to see the sort of horizons that have opened up now that I've got mobile computing, and I'm already experimenting with the Android SDK to see if I can, for starters, port some of the little Java games I already wrote to a new platform. Hate to sound even more geeky than usual, but it's an exciting time we live in.

(Final note: I did stop Swyping this post about halfway into the second paragraph.)

Retrospective on my first do-it-yourself computer experience

2010-11-29T15:05:00.005-06:00

I've always considered myself a software geek, and in the past I've had no desire to fool around with hardware beyond the occasional RAM upgrade or extra hard drive. However, so many friends have reported positive experiences with building their own computers, that I decided I really needed to try it.

I was pushed to hurry along this path when my old desktop's hard disk got corrupted and I could no longer run Windows. I was planning to pull the data off and reinstall, but I still recognized that it was time to replace the old eight year old system. Since I got a new laptop a year ago, my old computer was mostly sitting dormant, used occasionally to recover documents and sync my iPod with music that I've recorded and rated from my CD collection over the last several years.

A Facebook friend gave me some words of wisdom: You will not save money by building your own computer. Not because the parts won't be cheaper -- they will! But when you buy them individually, it's impossible to resist the siren call of "100 more watts of power couldn't hurt!" or "Gosh, this terrabyte hard drive is not nearly twice as expensive as the 500GB, how can I pass that up?" or "I'm saving money! A little more muscle in the graphics card? Why not?"

So you'll spend just as much as you would for a prefab desktop, but you will get more than you would have for your money. And then there's the "priceless" category, which is pride in creation, as well as a better understanding of what's going on under the hood of all future computers you may work with.

Another friend who used to build and test hardware for Dell pointed out that I was working at a severe disadvantage as a first timer. An experienced or professional builder will have lots of spare parts lying around to swap out and help test the machine. Nothing's on the screen, is the graphics card okay? Put in a different card and find out. Etc. I had to debug all my problems with just one set of parts, as my other PC was much too old to have any compatible bits.

Phase 1: Shopping spree

The first thing I did right was, instead of buying a motherboard, case and power supply online, I went down to the local Fry's and chatted up an extremely knowledgeable clerk. With all the dire warnings I'd heard about messing up compatibility requirements, I just didn't want to take the chance of guesswork. Before I went, I bought a short trade magazine about building a computer by PC Gamer. I read it thoroughly. They of course recommended a ridiculously overpowered and overpriced system, but later in the book they had some recommendations for working on a budget. They came up with something for under $600, but this estimate is a bit deceptive because it doesn't include an OS or any peripherals like a monitor.

Anyway, I read this thoroughly and dog-eared the page full of cheap stuff, figuring this to be a minimum benchmark for what I can buy. Then I brought the list to the Fry's guy, and I said "I am prepared to spend several hundred dollars today. Pay attention to me!" Basically I went through each item on the "cheap" list, and asked the following questions:

Do you have this particular part?
If not, what do you have that's comparable in price and performance?
What would I get by spending more on a better part?
How likely is it that I will need that extra power?
(In some cases) That's more expensive than the guide implies. Can I get it cheaper on New Egg?

Your mileage may vary, but this guy was extremely helpful, and didn't try argue too hard to get me to buy only at Fry's or to buy stuff that was more powerful than I needed. In fact I only wound up buying a motherboard and case that day, and I left armed with a list of precise specs that would be compatible with the mobo, and deals to look for on New Egg. (For example: "That CPU you're looking for is absolutely the best thing in that price range," he said. "In fact it's so popular that it's been out of stock for weeks. Go look for that exact thing on New Egg and see if you can find it at the price you want." And I did.) I was so happy with the experience that I made a point of coming back when I needed some odds and ends, like a keyboard and a replacement hard drive.

It happens to be the holiday season, so it seems like New Egg had even more combo details and discounts than usual, or so they told me via email every single day. You just have to know approximately what you're looking for, and then keep an eye out for discounts with other parts you're looking for. Hard disk may be paired with Windows 7. Graphics card may come along extra RAM. Stuff like that. $10-$20 savings here and there adds up, or as I warned, encourages you to buy slightly more power. :)

Phase 2: Construction

In addition to getting friendly with a retail guy, it's always a good idea to identify a friend or coworker who has done this before and can guide you through it. If your workplace makes this likely, talk to everyone about your intent and see what kind of feedback they get. A guy who works in QA here is my new best friend. :)

Building the computer was both less complicated and more nerve wracking than I expected. I was frankly terrified of making mistakes, and I did make mistakes. I was curious about the CPU connections, and brushed it with my finger before remembering that you NEVER EVER TOUCH THE PINS. Similarly, I couldn't find a tube of thermal grease that my magazine claimed would come with either the CPU or motherboard. It wasn't until I poked the underside of the CPU cooler and came away with sticky fingers that I realized the stuff was pre-applied, and now I was afraid I'd contaminated and ruined it somehow. I forgot to put on my static wrist strap several times. I dropped the graphics card a little too hard as I was pulling it in and out so often. Luckily, the computer parts are considerably less fragile than I had feared. Not that they aren't fragile, but they can take a few knocks. (Except hard drives. The drive I bought from NewEgg made clicking noises and didn't get detected, which is why I wound up returning it and buying a replacement.)

Figuring out how many parts need power was also a challenge. I initially thought my power supply was busted because nothing happened when I simply plugged it in -- no fan action or anything. Turns out it needs to be hooked into the computer's power button or else it doesn't get an "on" signal. Also, count the number of fans and make sure they are ALL running. My case has two built in, with space to install another one. The CPU has its own fan; the graphics card has its own fan; and the power supply has an intake fan. At first I had plugged the fan into the power supply, but my QA friend pointed out that you are supposed to plug them into the motherboard so it can sense the temperature and regulate the fan speed.

The CPU needs power, and the mobo needs two cables plugged in SNUGLY (loose cables were also a hallmark of the experience). Then there are all the little things like LEDs and USB power supplies, which seem intimidating at first (lots of cables!) but the motherboard's manual is very specific about what goes where. It's not so bad. Just don't forget to find the loose parts you need, like a tiny speaker.

Miscellaneous stuff I learned

If you haven't upgraded your system for a while you may be surprised to learn what is built in standard to motherboards these days. You used to need to plug in a sound card and a network card; now you don't. I bought a sound card, and I'm installing it because it's a cheap part that is not much worth returning. But the built in sound works fine for the most part.
The BIOS may take a long time to appear on screen the first time you start it up. Give it a couple of minutes.
If your graphics card has two ports, they are not necessarily interchangeable. One is for the primary monitor, and the other is for a dual setup. Make sure your monitor is plugged into the right one.
The first sign that you are doing something right is if it beeps. Make sure the little internal speaker is set up. Don't put in RAM right away, because when it's out you will hear beeps indicating an error. At that point, you know your motherboard is probably okay.
All you have to do with the new system is drop in a CD for the operating system of your choice and watch it go. There is no other initial prep work (I thought i would have to screw around in the BIOS more).
Don't talk too much about your issues on Facebook, because an army of annoying drones will tell you to switch to Mac. They can STFU if they're not planning to play grown-up games or develop software. :)

Specs

Case: Cooler Master HAF 912
Motherboard: MSI 870-G45
CPU: AMD Phenom II X2 555 Black Edition Callisto 3.2GHz Socket AM3 80W Dual-Core
Power supply: COOLER MASTER Silent Pro M700 RS-700-AMBA-D3 700W
Hard drive: Seagate Barracuda 7200.12 ST31000528AS 1TB (actually that's the one that died and got replaced; the new one is Toshiba or something)
Mouse: RAZER Lachesis Banshee Blue 9 Buttons 1 x Wheel USB Wired Laser Gaming Mouse
RAM: G.SKILL Ripjaws Series 4GB (2 x 2GB) 240-Pin DDR3 SDRAM DDR3 1600 (PC3 12800)
DVD: SAMSUNG CD/DVD Burner Black SATA Model
OS: Windows 7 64 bit Home Premium
Graphics: SAPPHIRE 100284L Radeon HD 5750 1GB 128-bit GDDR5 PCI Express 2.0 x16

The Gaming Experience

Sure, I've installed Eclipse and JBoss on the new box, and I'm enjoying the fact that I won't be coming close to filling up the hard drive for a long time. Compiling programs is nice when it's fast, but don't let me lie to you; the real benefit of a new system is the games.

For a moderate priced system it runs great. I've been playing World of Warcraft at "Ultra" graphics settings with hardly any drop in the full 60 FPS. Of course, WoW is not such a graphics intensive game, but with the new changes in place for Cataclysm, it looks pretty nice: the water has good distortion effects, you can see stuff in the landscape that is a good half a zone away; and the spell effects really sparkle.

With Starcraft II it's hard for people who don't play to notice the difference, since the view is set such a long distance from the action. When playing though, you can see enormous detail in the units, and the glowing effect of workers carrying minerals and gas is a nice bonus. Also, the Machinima in-game cutscenes are noticeably worse than the pre-rendered movies on a slower machine. With higher settings, they are still different but still pretty impressive.

Left 4 Dead 2 looks great and benefits enormously from running quickly.

I'm a pretty satisfied customer of the experience, and again, it's not so much the newness of the machine as the pride of ownership.

The State of the Internet Operating System

2010-05-14T12:00:00.005-05:00

I'm working my way through a couple of long and extremely excellent articles by Tim O'Reilly, about how the operating system of the future is the entire internet.

I haven't got much to add that would improve the articles so far, so I'll just quote an excerpt and get out of the way.

The Internet Operating System is an Information Operating System

The underlying services accessed by applications today are not just device components and operating system features, but data subsystems: locations, social networks, indexes of web sites, speech recognition, image recognition, automated translation. It's easy to think that it's the sensors in your device - the touch screen, the microphone, the GPS, the magnetometer, the accelerometer - that are enabling their cool new functionality. But really, these sensors are just inputs to massive data subsystems living in the cloud.

When, for example, as an iPhone developer, you use the iPhone's Core Location Framework to establish the phone's location, you aren't just querying the sensor, you're doing a cloud data lookup against the results, transforming GPS coordinates into street addresses, or perhaps transforming WiFi signal strength into GPS coordinates, and then into street addresses. When the Amazon app or Google Goggles scans a barcode, or the cover of a book, it isn't just using the camera with onboard image processing, it's passing the image to much more powerful image processing in the cloud, and then doing a database lookup on the results.

Increasingly, application developers don't do low-level image recognition, speech recognition, location lookup, social network management and friend connect. They place high level function calls to data-rich platforms that provide these services.

Wondrous number graph

2010-03-15T18:30:00.002-05:00

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

2010-03-10T19:00:00.000-06:00

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

2010-03-03T19:00:00.005-06:00

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:

"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.
"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.
"(...)": 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.
"void": Some methods return an object type and others don't... you know what? I'll tell you later.
"public": So here we encounter the notion of public and private methods, which is intended to separate interface from implementation. Simple, right?
"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.
"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...
"[]": ...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?
"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".
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:

Was it a mistake to start in Java?
If not, why not?
If you were being introduced to programming for the very first time, which language would you want to be taught first?
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

2010-02-11T12:44:00.005-06:00

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.

Write an expression of the line segment opposite the point being moved.
Find a vector perpendicular to that line.
Project the moved point along that vector to find where it intersects the opposite segment.
Find the actual distance that the point must be from the segment in order to make a 90 degree angle.
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

2010-01-25T10:09:00.001-06:00

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

2010-01-11T13:05:00.003-06:00

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

2009-10-16T15:04:00.007-05:00

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:

Store the number 1 in a set.
Consider the smallest item, "n" in the set. That is counted as the next ugly number.
Add the numbers n*2, n*3, and n*5 to the set.
Remove n from the set.
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:

Write your own min-heap class, which is the fun part. ;)
Add the number 1 to the heap.
Inspect the root of the heap, and count that number ("r") as ugly.
Add 2r, 3r, and 5r to the heap.
Delete the root.
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

2009-10-16T11:38:00.004-05:00

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

2009-10-16T10:12:00.005-05:00

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.

Divide and conquer your project, part 1

2009-08-28T18:00:00.003-05:00

James, who is a regular commenter, is a programmer looking for more experience. James has studied a few languages and probably has a decent grasp on the basic logic that it takes to write a program, but he wants to work on a personal project because he doesn't get enough variety of practical applications at work.

This is an admirable goal, first because developing your programming skills requires constant practice, and second because personal projects can make good resume padding. Potential employers like to hear that you program for fun, because it will make you more likely to throw yourself into your work. Also, if they ask "Have you worked with technology X?" you can say "Not professionally, but let me show you this project that I posted on my web page." It gives you the opportunity to talk intelligently about the technology.

However, starting a new project can be overwhelming, and it's hard to know where to start. You have all these things in your head that you would like the program to do, but you can't see how to get from what you have now (a blank screen) to what you would like to have (an awesome program with flawless logic and a clean interface). What do you do first?

I spent a few posts discussing the technique of "divide and conquer." As it turns out, that is also an excellent plan for approaching your programming projects. Here's a little secret of programming: you won't get it right the first time. Fuhgeddaboutit. Don't try. If you sit down for a couple of hours and try to write an enormous, complex program in one shot, and only after you think it is done do you compile it for the first time, you will be confronted by a screen full of errors and another few hours of headache, tracing back through what you did to figure out where each of numerous bugs exists in your thousand line program.

Actually, my proudest moment as an undergrad was writing a single assembly language module that executed perfectly with no debugging on my first try. But that's not something you should count on, and in any case, this was one line in a much larger program.

When you are building a castle of air, you do it brick by brick. Except they're, you know, wind bricks. You don't wave your hands and get a fully formed castle. You break down the project in your mind into easily manageable pieces, and at each step you (1) Look at that step to determine whether you should break it down even further before proceeding, (2) Write complete code that does something visible, and (3) test that component thoroughly.

That third step is crucial, and it's a hallmark of a solid programmer that they develop testable and tested code at every step. When you test a piece of your code until you know it's solid, you will save yourself a lot of time later that would have been spent backtracking to figure out where your code is going wrong.

How do you break it down? Let's consider the project that James set for himself.

One idea I've had is a program that accepts inputs on your credit card balances, minimum payments, etc, and calculates the most efficient payment plan to snowball. I've got a spreadsheet I downloaded from somewhere that I'd model, but the spreadsheet can't jigger your payments to determine the best way to pay off the balances the soonest, or with the least amount of interest. I envision it as an Iphone App, although I learned that without a Mac I can't write it that way.

Actually a spreadsheet probably can do that, but writing a full featured program would be cooler. So let's consider what components this program has.

A popular way of dividing up pieces of a program is to start by splitting it into three layers: a presentation layer (the way your program handles input and output); a data layer (the information that your program will be manipulating); and a business layer (the program logic that figures out what to do). If you split your program up into pieces this way, then you can hopefully change up the pieces at any stage without risking ruining your entire program.

How you start your problem will largely depending on which component is most interesting to you personally. In many projects, the graphics are the most interesting thing. In that case, your top priority would be to get something, anything to display on the screen.

For example: My first real programming job was modeling equations for scientists. There was an eccentric old physicist who wanted me to graph some of the equations he wrote for me, using Fortran on a green and black terminal. As I progressed on getting the equations to display the right answer, he seemed distinctly bored with hearing about the programming details. But then I figured out how to generate a line diagram. It excited the hell out of him, and suddenly he couldn't stop talking about his ideas for what we could do with this.

The diagram, of course, bore almost no relation to the actual equations he had described. But it didn't matter. It was a launching point for his concept of the program. Similarly, as you write your own programs, hopefully you will keep on continually inspiring yourself by producing code that does something that will tickle your interest in the next phase of your project.

Now, in James' case, the interesting part of the project is probably not the graphics. It's the business logic. After all, the ultimate objective is not to create something that looks cool, but something that provides useful information. Since this is a program that you will be using yourself, the inspiration will come from your feeling that "Wow! This is really telling me some valuable stuff! But I bet it would be even more useful if..." And then whatever comes after "if" will determine which piece of the program you conquer next.

So the business layer is the most important part of your program. Therefore, I would recommend that you pick a language, and start with an extremely simple presentation layer and data layer. So for presentation, let's say you'll use plain text input and output. For data, let's say that you'll write a module or an object that hard codes the value of your credit card balances, and then you can tweak the code to change the values.

These aren't good solutions, but they are stepping stones for the program you really want to build. Write good business logic first, using crude presentation and data models, and then make it better later. How will you make it better? Well, you might decide to turn your text input into a web form interface, and perhaps add graphs. You might change your data from hard-coded values, to a separate text file that you will edit by hand, to a database table. As long as you keep these parts of the program reasonably well separated, you can build them up a bit at a time, focusing on the parts that strike your fancy.

Whew, that was a mouthful. Pausing for feedback now. James, do you think this is enough to get you started? Do you have an idea which language you'll start in? Any thoughts or questions?

Q&A open thread

2009-08-17T07:58:00.000-05:00

After a two month spell without posting, I'd like to get more out of this blog again, but I don't have any pressing topics that I feel I need to write about. So I'd like to invite questions in the comments section of this post in order to inspire new topics that we could explore. Any pressing questions about software development that need some discussion? Have I posted anything in the past that I ought to expand on? Is anyone anxiously awaiting a continuation of the chess series of posts?

I haven't spoken at all about my current position, which is a lot different from past jobs I've had. I'm currently doing contract work on a product that helps people to automatically activate and configure their high speed internet connections. The work is all done through customized web pages that use ActiveX to deal with low level PC operations. As you may have already noticed if you've been following either my Twitter or Facebook feeds, I spend a lot of time in a computer lab working with custom configurations for a like DSL modem on various configurations, including released candidates of Windows 7. I've never really been a fan of hardware, but this involves a lot of interesting network puzzles and some really advanced ways to use JavaScript.

Anyway, if you've got any questions, other commenters may answer you before I get to it, at least it will help me feel out some directions to take potential upcoming posts.

Question about web security

2009-08-14T11:26:00.004-05:00

Wanted to put out a question to readers. I recently happened to tune in to the Kim Komando show and heard something that sounded like a mistake. However, I'm not a security expert, so I'd like to find out more.

A caller had been making use of his neighbor's unsecured wireless connection when his own internet was down. He was wondering about the security hazards of doing this.

Kim's answer was mostly correct, which was to say that anything you transmit or receive over the web is visible across the entire network. By using freely available software, your neighbor could potentially steal your information. He could have a packet sniffer and log the information on his computer, or even in the router.

Kim then went on to say "So obviously you wouldn't want to do any banking over the unsecured line, because you don't know who's looking at your data."

These struck me as solid words of caution, but potentially incomplete. Presumably your bank would make you log in over an SSL connection. My own understanding is fuzzy, but I believe this means that the data gets encrypted at each end before being sent over the network, and only your client and their server have the information necessary to decrypt the data.

Can anybody confirm or deny that my understanding is correct? Is there some way you know of where the neighbor could read your secure data as plain text? If not, what information is your neighbor lacking that would allow him to see it?

Artificial intelligence in games, part 3

2009-05-31T08:30:00.001-05:00

As I warned when I started this blog, I've allowed it to lie dormant for a while, but I feel like it's high time to pick up where I left off and finish the series about playing chess by look-ahead.

So to review the posts that led up to this one:

Now we're going to turn our attention to chess.

Although chess is a much more complex game than tic-tac-toe, it's easy to see that you can apply the same tactics to systematically list all possible games of chess, in theory. Of course I'm not going to attempt to diagram them, but there's definitely a finite number of things you can do on each move. If you're the white player, on your first turn you have eight pawns that you can move forward one or two spaces, and then you have two knights that can move to two spots (forward two, left or right one). So the total possible moves on the first turn is (8*2)+(2*2), or 20.

Then it gets a little more complicated. Black has the same choices, but he has the same 20 choices for each of the 20 possible moves that white could make. So after each player has made one move, there are 20*20=400 possible states the board could be in. It only gets worse from there.

For instance, if white performed the traditional P-K4 opening, on the second move he has nearly all the other choices remaining (7 pawns to move one or two squares, plus two knights two ways, 18 moves) but he also has a whole lot of new choices. The king's knight may move into the spot occupied by the pawn (19). If the black king's pawn doesn't block it, the white king's pawn may advance one space (20) or, depending on what black did, capture an enemy pawn.

Also, the white king's bishop is now free to move to any of 5 spaces toward the upper left (25) and the queen can move to any of 4 spaces toward the upper right (29). So the number of possible moves keeps increasing as the board opens up, and so does the complexity of the tree. Now it looks like by the time white has moved twice, there are about (20*20*29) possible states the board could be in. (Some starters obviously make less than 29 moves possible, and there is more than one way to get to the same state; i.e., P-K4 followed by P-Q4 has the same result as P-Q4 followed by P-K4).

As we observed in the tic-tac-toe problem, you can calculate roughly how many possible games there are in two ways: by multiplying out the possibilities for all moves, or by figuring out every possible state of the board. The second method tends to be smaller because it eliminates various ways of GETTING to those states. However, in the case of chess, figuring out how many moves are possible from each state is massively complicated, so will go with the second approach.

Each side has 16 pieces. The pieces are not unique; for instance, the eight pawns are interchangeable with each other and so are the two rooks . However, to simplify the calculations we'll assume that all pieces are unique. So there are 32 pieces on the board, and 64 squares where they could be located. The first piece could be on any of the 64 squares, the second on any of the remaining 63, the third on any of the remaining 62, and so on. So as a rough guess, the number of board configurations is (64*63*62*...*35*34*33) and then the remaining 32 squares are blank. That is to say, the answer is "64 choose 32", or (64!/(32!*32!))

Side note: Cool feature of Google. Type "64 choose 32" into the search bar and it will answer the question for you. It's 1.83*10¹⁸.

Is this number an accurate portrayal of all chess boards? Not exactly. In the first place, many of the moves are not legal. This set of all possible boards includes boards where the two kings are next to each other, or in an impossible multiple check; it includes pawns on the first row, and positions where all eight pawns are on their home squares, but the king and queen are not.

On the other hand, it does not include any position where one or more pieces have been captured, nor does it include positions with two or more queens due to promotion. So there may be more games that are truly possibly, or there may be fewer, but on the order of 10¹⁸ possibilities is a fair guess.

Now, 10¹⁸ is a very large number. In point of fact, it is larger than the number of seconds since the universe began (about 4.4*10¹⁷... although it's only 189 billion if you're a creationist. Har har.) It's close to the number of grains of sand on earth, and much larger than the number of stars in the milky way.

In theory, you could have a computer run through the win/loss state of every one of those games, but not in a reasonable amount of time. If you could analyze one game a second, it would of course take longer than the universe has been around to decide on one move. Computers can do much better than that, of course. Currently the world's fastest supercomputer can perform 596 TeraFLOPs -- 596 trillion floating point operations per second. That means that if you were so incredibly optimistic that you believed that analyzing one board position could be done in a single operation (believe me, it can't), the world's fastest supercomputer would still take 40 minutes to analyze the outcome for a single move. And that level of optimism is ridiculous.

Granted, computers have become a lot more powerful since this topic was discussed in the 1970's, but it's still fairly impractical to play a decent game of perfect chess, unless you have several supercomputers lying around doing parallel computations. Your desktop PC would take years. More realistically, thousands of years. Needless to say, no computer plays chess based on the tic-tac-toe strategy of exploring every possible move.

Next time: What's a heuristic, and how come a computer can beat the human chess champion of the world?

Random numbers aren't random

2009-04-13T05:37:00.019-05:00

In a previous post, I mentioned that you can add the appearance of intelligence to a game playing script by throwing in a random component. While the computer can always win tic-tac-toe by playing the same sequence of moves, it looks much less boring if the computer picks different winning moves in each game.

Following up on this, I got a special request to explain how random number generators work. I happen to know that the person who asked for this information is sort of a logical determinist, so she'll be delighted to hear that random numbers are not random at all, but generated by a very specific script.

When we think about random numbers, what we generally want is an unpredictable number in a range, with 0 or 1 at the low end, and some number "m" at the high end. How big m is depends on the application. For instance, to simulate a die roll, we want a random number from 1 to 6. To simulate drawing a card, we need a number from 1 to 52. For a roulette wheel, 1 to 38. For a game with two dice, like monopoly, we need to generate two random numbers and add them together. The rules for a role-playing game such as Dungeons & Dragons will often instruct you to roll 1d20 (roll a 20 sided die, i.e., generate a random from 1-20) or 3d4 (roll three four sided dice) to determine a monster's health, or whether they hit you on a particular round. Games like World of Warcraft have borrowed heavily from tabletop gaming rules in order to come up with event odds in the range that make sense for the game balance.

It's hard to generate a truly random number, since computer programs are fundamentally deterministic in the way they follow algorithms. So they do something slightly easier. Once we have one random number (or pseudo-random), we generate a sequence of randoms after that, where each one is based on the number before it.

There are many functions which can generate this sequence; one common example is this:

X_n+1 = (a*X_n+b) mod m

In this case, a and b are constants that you can pick, often large prime numbers. "m" is a maximum value for the resulting number.

Let's try a few examples. I'll pick arbitrary values a=107, b = 23, and m=101.

1 (This comes before the first number. It's called the "seed," as it helps to determine which numbers will come up in the pattern.)
107*1+23 = 130; 130 % 101 = 29
107*29+23 = 3126; 3126 % 101 = 96
107*96+23 = 10295; 10295 % 101 = 94
107*94+23 = 10081; 10081 % 101 = 82
107*82+23 = 8797; 8797 % 101 = 10
107*10+23 = 1093; 1093 % 101 = 83

As you can see, this function produces a string of seemingly unconnected numbers from 0 to 100. However, they aren't unpredictable. If you know the formula, and the current number is 29, then you know the next number is always going to be 96.

Because of this, you wouldn't want to use 101 as your "m" value, if you were actually looking for a random number in the range of 0 to 100. You could always predict the next number in the sequence. If you're a company that writes video poker machines, and your random number generator is easy to reverse engineer in this way, you'd be in very big trouble.

So instead, you'd make all your constants, m, a, and b, much larger. Then you'd take the resulting random numbers and mod them by a smaller number to get program data, but you'd still retain the larger number to generate the sequence. That way, if people see the number "3", they have no way of knowing that the real number in your random sequence was generated by 5,495,110 mod 6 plus one, and therefore they can't deduce what the next number is going to be, even if they know the algorithm.

So the random sequence is masked from the program's end user by not telling them what the formula is. Nevertheless, a random number generator is still predictable based on the seed. If you start with a fixed seed number of 1, and you get the sequence of die rolls 4, 2, 6, 1, 3, then you will always get the same sequence after you shut down the program and restart it.

If an enterprising gambler were to discover that his video poker machine was programmed so foolishly, he could take advantage of it in the following way: First, unplug the machine and plug it back in to reset it. Then, bet small amounts of money while writing down the card sequences that you get. Then, reset the machine again, and bet large amounts of money against the cards that you know will turn up.

So predictability is the bane of random number generators. Clearly, it's important not only to have a disguised algorithm, but an unpredictable seed set at the beginning of your program.

How can you set the seed? It doesn't really matter, as long as it's not based on a known quantity. It needs to be a truly random number, but again, there is no such thing as a truly random number to a computer.

One approach is to use the internal clock, including milliseconds. A human can't really control the precise millisecond at which the program starts, so there's no way to predict what the seed will be.

There are wackier ways to handle it. For instance, an algorithm called "lavarand" operated by pointing a camera at a lava lamp, taking a digitized picture, and creating a hash from the bits. This is chaotic enough to provide something that appears to be truly random.

So to recap, in order to generate random numbers, you need

An algorithm that is deterministic but unpredictable
A random seed that is preferably discovered through some (also unpredictable) aspect of the external world.

There are, of course, also advantages to using predictable seeds. If you always use the same seed, then you can test the same set of data repeatedly, which you sometimes must do if you don't want to tear your hair out trying to nail down a problem with the algorithm that actually does something with the numbers. But in a real world environment, you need some kind of outside information in order to randomize the results and stymie the users.

Artificial intelligence in games, part 2

2009-04-06T08:17:00.007-05:00

In the previous post, we discussed the fact that tic-tac-toe is finite game, and you can even calculate all the possible states of the board: it's 19,683, with 362,880 different ways to get to the legal states. Now we can talk about how to take advantage of this calculation to always win the game.

Let's imagine that we pit two perfect computer opponents against each other. The first opponent, playing as "X", will want to evaluate each of the nine possible moves on a blank board. How does it know which is best?

Well, starting in the corner, the question is: "Do I have a sure win on this path? If so, then I will definitely make this move. If not, then does my opponent have a sure win? If so, then I will definitely not make this move."

But how do you know if you or the opponent has a sure win? Simple: Imagine that you already made this move, and then try to make the best move for the opponent.

You can easily see that this is a recursive process. It has a recursive step ("Let me try this move") and it definitely has a terminating condition. After all, if you come to a step where (a) the board is full, (b) X has won, or (c) O has won, you don't need to look ahead to any other moves.

Here's an example of how the computer would evaluate the first possible path.

|  X |   |       X | O |       X | O | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|  X | O | X     X | O | X     X | O | X
| ---+---+---   ---+---+---   ---+---+---
|  O |   |       O | X |       O | X | O
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|  X | O | X
| ---+---+---
|  O | X | O
| ---+---+---
|  X |   |

This game ends in a win for the X player. So if you are the X player, you like this game. If you are the O player, you do not like this game. So the computer then backs up by two moves ("waking up," in the dream analogy) and assumes that O would not go there, but would instead do this:

|  X | O | X
| ---+---+---
|  O | X |
| ---+---+---
|  O |   |

Of course, this game will also result in a win for X if you follow it to the conclusion, which is this:

|  X | O | X
| ---+---+---
|  O | X | X
| ---+---+---
|  O | O | X

You get the idea. The computer will play every game to its ending, at which point it will know exactly which games guarantee a win for one player or the other.

Now the pruning begins. The X-playing intelligence will try to reach one of the game states that guarantees a win for X. If it cannot, it will at least avoid reaching any game state that guarantees a win for O.

Writing an unbeatable tic-tac-toe opponent in this way is actually pretty straightforward. You can write it to pick the first "good" move, where "good" means "First try to pick a move that guarantees a win; then try to pick a move that doesn't guarantee a loss." If you do this, you'll find that your tic-tac-toe game will always play in the same way. For instance, in the first move, the upper left corner is as good a move as any (the O play can never force a win). So your program may well always start in the upper left. This program will not appear to be intelligent. But it will never lose.

If you want your program to be more interesting, throw in a randomizer. If there are multiple moves that guarantee a win, then pick one at random. Otherwise, if there are multiple moves that don't guarantee a loss, pick one of those. Then you'll have a program that never loses, and also it will make moves that appear unpredictable.

Even though tic-tac-toe is an unwinnable game with two perfect players, some moves are better than others. Against novice opponents, there are tricks you can use to moderately increase the likelihood that your opponent will make a mistake and lose. This program doesn't know that. It doesn't evaluate different positions as tactically stronger. It just knows whether or not one player is guaranteed to win.

By the way, needless to say, this tic-tac-toe program does not have sufficient reasoning capacity to prevent it from launching a global thermonuclear war. ;) The computer doesn't have abstract thoughts; it's just following instructions. Completely deterministic instructions for winning if it can.

Next time: Chess as a deterministic game.

Separating form from content

2009-04-04T09:00:00.003-05:00

In a previous post I highlighted a video showcasing some experimental wearable Technology. One of the features in this video was that a person picked up a product from the shelf, scanned it, and received some information (green, yellow, or right lights) indicating whether the product was environmentally friendly.

A friend asked:

The thing that interests me the most about this is the impact it will claim to have on shoppers' ability to make more eco-friendly purchasing decisions. Where will the database be kept? Does it already exist? Also wondering how companies would be held to objective standards about the environmentally friendly nature of their products. Are there standards already in place? Will the database include packaging environmental impacts?

The important thing to recognize about the gizmo in the video is that it is not an information creator. It is simply a display device. In the current web 2.0 world, it's important to recognize the separation of form and content.

Essentially, the device consists of a wireless receiver, a camera, and a projected screen. All computers and computer-like devices require three basic components: input, output, and data. They've gotten more complicated over time, but they can still be best understood as variations on those basic components.

As a kid in 1982, I had an IBM PC 8086. For output, it had a screen that would display only four colors (red, green, blue, and of course black), and it had a speaker that could generate various pitches of annoying beeps. For input, it had a keyboard that made loud solid clicky noises; no mouse. It also had no hard drive. All data was stored to 5-1/4" floppy disks, which would turn on a red light when writing and produce an audible "kachunk kachunk" noise.

Many of my friends had Atari 2600s. Ataris didn't come with their own screen or speakers of course; instead, they had a dongle thingy that would plug into a standard TV and provide output. Input was limited to a joystick that had one button and four directions, which are not sensitive to the level of force you apply. Data was in the form of interchangeable cartridges. You could not save the state of your games; your progress only existed in memory while the console was on.

Now the components for a high end gaming system are getting more and more elaborate, especially with high end games: output includes complex 3D graphics and digitized sound, while input may include mouse, keyboard, camera, gamepad, and a microphone. Game files (data) take up several gigabytes, sometimes read from your hard disk and sometimes directly from a CD. Saved games may take several megabytes.

But something else is happening too.

The most important aspect of this is the internet. Thanks to the internet, the data component has shifted away from individual computers and onto servers that can be accessed from anywhere in the world. I don't have to be actually at my home computer anymore to look up some important information that's saved in an email. I don't have to be holding a physical copy of "Consumer Reports" in my hand to check out a product rating.

At the same time, wireless devices -- basically a fancy method of receiving additional input -- are infiltrating everything. We've got wi-fi hubs popping up all over the place, in coffee shops and restaurants and airports and malls. If you're not near a hub and you're willing to pay extra (I'm not yet), your cell phone will pull down an internet connection from satellite. And they're coming up with new methods to connect people, like Mobile Ad Hoc Networks, which can turn a room full of people with wireless devices into a grid of amplified signals.

So, how does the device in the video generate the information about environmental products? It doesn't. It doesn't take up space in the device's memory. It comes from the internet, from sites that are maintained by someone else.

As I envision the guts of this device, you probably install a minimal amount of middleware -- software which "knows" where to get raw data from and what is the best way to display it. The database that keeps track of individual products would probably be very large, but that needn't concern you, any more than the inner workings of your favorite web pages concerns you. You ask for a specific piece of information -- what is THIS product? -- and that gets interpreted into a web request, and the server sends it back as a stream of formatted information, to which the middleware then adds some graphical bells and whistles, for the display.

So then the question is, where does the environmental information come from? Does it already exist now, or is it just a fantasy from the video?

Well, yes it does, I think. I'm not real up on this stuff, but I googled around and came up with this and this. The data may not yet be formatted in a way that is useful to a mobile device, but the information exists in some format. If nothing else, somebody could easily write a program to scan the web page and throw out most of the HTML, pulling out only relevant information and turning it into a graphical display.

So the remaining question is: what is the standard for this information? Are these sites reliable? Well, that's up to you to decide. The main thing that has been accomplished by web 2.0 is that many competing organizations can generate this sort of content in a standardized format. Whether you trust the information depends on whether you trust the organization that generated it.

I can understand the suspicion if it is, for instance, a government agency that is known to have been strongly influenced by a political agenda. Likewise, if it's a corporate site, and the corporation is influenced by advertising dollars. But there are also consumer advocacy groups with a reputation to uphold. And while I am not a pure capitalist by any means, this really is a case where if there's a strong enough demand, the market provides what you want. "The market" in this case may be profit driven, or it may just be a bunch of activists who want to make this data available to further their agenda. Whatever the case, it's likely that you can find the data you're looking for.

The bottom line is that technology is a tool for getting at the information that already exists, or can be created. It gives you quick access to the same data from anywhere in the world.

I don't think the device shown in the video is perfect. After having some discussions about it, I think that waving your arms around is a clunky and tiring way to interact. I bet the screen is hard to read in a brightly lit area. That's not the point, though. The point is that it's becoming easier to apply technological solutions to pull in information about the world around you, and get back useful background information that's not immediately obvious to your senses.

Wearable technology

2009-03-27T14:23:00.001-05:00

I want one of these setups. NOW.

Artificial intelligence in games, part 1

2009-03-20T16:58:00.010-05:00

"Chess is not a game. Chess is a well-defined form of computation. You may not be able to work out the answers, but in theory there must be a solution."

- John von Neumann

I'd like to talk about some basic concepts of Artificial Intelligence, by talking about games. In a few posts I'm going to tell you how to play a perfect game of chess. Not just a good strategy, but a perfect strategy. With this strategy, you will always beat a non-perfect opponent. If no win is possible, you will most likely be able to end the game in a draw.

Unfortunately, once I've explained this strategy, you will realize that you can't actually use it. So before I talk about that, I'm going to try something less ambitious. I'll tell you how to teach your computer to play a perfect game of tic-tac-toe, also known as "noughts and crosses" in England.

Here's some quick background for those who don't know how to play. Tic-tac-toe is played on a three-by-three grid. Two players mark their squares, one with the letter "X", the other with the letter "O". Traditionally the X player goes first, and may place a mark on any open square. The players continue to alternate marks until one of two conditions is met. A player can win by placing three of his or her marks in a row -- either horizontally, vertically, or on a diagonal. Much more commonly if the players are experienced, the board will fill up, no player will get three in a row, and the game ends in a draw.

Complexity of tic-tac-toe

How many possible games of tic-tac-toe are there? One way to do it might be to count all possible sequences of moves. The first player has nine possible moves to make. The second player can only go in an unoccupied square, so that's eight moves left. The first player can then go in any of seven remaining squares. And so on, so the number of possible games is at most 9*8*7*6*5*4*3*2*1.

This is a common mathematical operation called a factorial. "9 factorial" is abbreviated as "9!" Factorials are very big. Some algorithms have a running time of O(n!), which can be extremely dangerous -- but I'll get back to that in another post. Luckily, in this case n is only 9, and 9! is a fairly manageable number: It's 362,880.

That seems like a big number to people who are good at thinking in the abstract but bad at storing large amounts of information. However, computers are the opposite, and 362,880 is a very small, manageable number of objects to explore.

It is also an upper bound. We know that there are no MORE than 362,880 possible games of tic-tac-toe, but most of the games resemble each other. Another trick we could apply is to calculate possible states of the board without thinking of moves. Each square can be in one of three states. Either it is empty, or it has an X, or it has an O. Thus, the total number of possible states of the board (legal or not) is 3^9, which is 19,683. So actually, there are no more than this many different ways to set up the board.

In fact, there are even fewer possible states, because many of them aren't legal. For instance, the board could contain all X's, but that's not the state of a real game, because the "O" player never got to move. So there are actually far less than 19,683 states, but all we need is a rough order of magnitude estimate to see how big a problem we have ahead of us.

Calculating all possible games of tic-tac-toe

If you go first in a game of tic-tac-toe, there are nine moves that you can make. The possibilities break down like this:

|  X |   |         | X |         |   | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|  X |   |         | X |         |   | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |

|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|  X |   |         | X |         |   | X

Actually, these nine positions do not really represent unique games. Really, there are three unique moves that you can make: Go in the center, go in a corner, and go on an edge. The rest of the moves simply lead to rotated or mirrored versions of the same games. Some algorithms might take advantage of this similarity and reduce the search space, but for our purposes, it still doesn't take too long to treat all combinations as unique.

Now, if you go in the upper left corner, there are eight moves that the "O" player could make. Here are a few.

|  X | O |       X |   | O     X |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |       O |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |

Again, these do not represent unique games. For all practical purposes, the first move and the third move are the same game. But it's easier to program (though slower to run) if you don't bother trying to analyze the games.

In the next post, I'll explain how we can use this system for categorizing every possible game to write an unbeatable opponent.

Recursive sorting 2: QuickSort

2009-03-18T07:00:00.005-05:00

I got good feedback from my last post about recursive sorting, some of it by email and in person. I also heard some serious concerns about my world domination scheme. You can all relax, because my Evil Generals are all away on extended vacation for the foreseeable future. This post probably won't be as amusing as the last one, as I've already explained the basic groundwork. But I'll try to give you the basics so you can do QuickSorting yourself.

Here are the fundamentals of how QuickSort works. In Merge Sort, we split up two decks of cards by size, and then sorted each half. How exactly you "sort each half" is up to you. If the remaining divided up decks are still large, you can just divide them in half again and run two more Merge Sorts. But if the decks are small, you can sort them in another way. Even Selection Sort might be a good choice if you have no more than, let's say 10 cards. OR, you can just keep dividing and dividing until you get down to two or three cards, and then perform a couple of swaps to get the cards in order.

QuickSort is similar, but a little different. We still split up the cards, but in this case we split them around a card value instead of a specific deck size. Here's an example. Start with unsorted card:

8, 4, K, A, J, 5, 9

In QuickSort our plan is to start with the first card (8) and put it in the correct place. You remember that in Merge Sort we did the recursive step -- the splitting up into smaller problems -- first, and then the action of actually moving cards around was saved until we reached the lowest level (merging the cards). That's when we actually do something constructive... like telling an evil private "Go kill that guy." In this one, we do the reverse. The action step comes first, and then the recursive step second. After the 8 is in the right place, we'll sort the cards around it, using another call to QuickSort.

When I say we want the 8 in "the right place," what I mean is that we want all the cards that are less than 8 to be on the left side of the 8, and we want all the cards that are greater than 8 on the right side.

How do we get there? The 8 starts in the low position, so put your left hand on the 8, then put your right hand on the right side of the list. That's 9. 9 is bigger than 8. No switch is necessary yet, so move your right hand one space to the left, toward the 8. You're now on 5. 5 is smaller than 8, so it's in the wrong position. Do a swap and you get this:

5, 4, K, A, J, 8, 9

So now the 8 is on the high side. It is correctly positioned with respect to some of the cards: it is between 5 and 9, which is where it should be. But you're not done yet. Now you have your left hand on 5, right hand on 8. Move your left hand up one space, to the 4.

4 is less than 8. Keep going.

King is more than 8. It's in the wrong place. Time to swap.

5, 4, 8, A, J, K, 9

Now the 8 is correctly sorted with respect to the cards you already looked at. It is more than 5 and 4, but less than king and 9. Nearly done.

The 8 is now on the low side. With your right hand on the king, move backwards. The jack is in the right place. The ace is smaller than the 8. Swap.

5, 4, A, 8, J, K, 9

...your hands now meet in the middle, and you're done. The 8 is in the precise position where it should be.

Now what? Here's the recursive step. You have the 8 in the right place, but you have three cards on the left that are totally scrambled, and three cards on the right that are also scrambled. How do you unscramble them? You QuickSort them, of course.

First you sort this array:

5, 4, A

Then you sort this array:

J, K, 9

Do it in the same way as before. For the first set of three cards, put your left hand on the 5, and move it to the proper place (the third position). For the second set, put your left hand on the jack, and move it to the proper place (second position, between J and K). By the time you've finished, we discover that all the cards are sorted. Quick, wasn't it?

Seriously, get your own deck and try this on 20 cards. It's easy and fun once you get the hang of it. Lay them out in a line. As you work, you'll put a card at a time in its final location. When you do this, push the card up slightly so it will stand out from the others. Then work on the unsorted cards from left to right until you're finished.

Complexity of QuickSort

Starting with the first card, you made one complete pass through the array in order to put it in the right place. So this algorithm is at least O(n). Then you performed this pass through the array multiple times. How many?

In the best case, QuickSort does the same thing as Merge Sort: it splits the array almost exactly in half. (In the above case, our first number, 8, landed smack in the middle of the array, with three numbers on each side. That's a perfect split.) So basically, you're dividing by two each time, and after (log₂ n) divisions, you're down to sorting one card -- just like what we did in a binary search. So we simplify this and say we examined "n" cards approximately "log n" times, so as I indicated earlier, this algorithm is O(n*log n).

If you're lucky!

But what happens if you start with an array that's already sorted?

A, 4, 5, 8, 9, J, K

Well, the first card is already the lowest. So you'll start from the king and start moving left, but eventually you'll get to the ace, having examined all the cards but not moved any.

Then you'll "split" around the ace... but there are no cards at all on the left, and (n-1) cards on the right. So you'll do almost as many comparisons as before against the 4. Then against the 5. And so on, until you've compared every card to every other card. This takes O(n²) time. Needless to say, that's bad.

So what we see here is that there's a difference between the complexity of a typical execution of an algorithm and the worst case scenario. Knowing that, we can do things to plan for the worst case.

Unfortunately, sooner or later it's highly likely that you will accidentally try to sort an array that is already sorted. So although it is counter-intuitive, we can guard against this by scrambling the array first and then sorting it. Scrambling is easy... all you do is go through the entire array (n operations), pick a random number (picking random numbers takes constant time, so it's O(1)), and swap the current number with the one at the random location.

This takes 1*n moves, so it's O(n) time. Then "scramble + sort" would take O(n log n + n) time But n is of lower complexity than n log n, and at high numbers it will be trivially small in comparison. So the "scramble + sort" routine is simply expressed as O(n log n).

Of course, you could be super unlucky and wind up with a scrambled array that happens to be perfectly sorted. But as you get a very large number for n, the chances of that happening become extremely small.

Another way to randomize this thing is by picking random pivot point. Instead of always trying to position the first card, pick a RANDOM card, move it to the leftmost location, and put that one in position. This way you fix the problem of potentially starting with the smallest card every time.

Recursive sorting, part 1

2009-03-14T07:00:00.008-05:00

I thought I could get away with just a brief mention of QuickSort, but apparently some people really want to hear details. So here you go. Today I'm going to talk about something that is not QuickSort, but it is a closely related technique called a Merge Sort. This is tangentially related to the discussion about Big O notation, but it's not really my main focus here. I'll just tell you in advance that, like QuickSort, this takes a time of O(n log n).

Along the way, I'm going to have to explain the basics of recursion to the novices, who may have been a little uncertain about what to make of the story about my dream.

Understanding recursion

Imagine that I am playing the board game "Risk" and I have an objective to take over the world. No wait, better idea. Imagine that I am an Evil Genius, and my actual objective is to take over the world.

The world is a big place. Too big to plan my attack in every minute detail by myself. How am I going to go about this?

Presumably I need military commanders, so I'll assume that I have a number of Evil Generals at my Evil Headquarters, who are expert military strategists. Luckily, the world is already divided up into several logical categories, known as continents. So I formulate a plan. First I'll conquer Europe. Then I'll conquer Asia. Then Africa. Then Australia. Then North America. Then South America. Conquering each region will help me gain additional bases, which will aid me in the remainder of my nefarious plans.

So I pick my six finest generals, and I say "Okay, listen up minions! YOU. Conquer Europe. I don't care how you do it, just get the job done and report back to me. YOU. Conquer Asia." And so on. I assign one continent to each general. Then I sit back and relax, confident that my brilliant generals will each do their job thoroughly and well. My part in the plan is finished.

But continents are still big places, so my Generals now have quite a job in front of them. Consider the poor General whose job it is to conquer Europe. Where does he start? Well, like me, the logical thing to do is divide up the work, and the way to do that is country by country. "First I'll conquer France," he says. (Ha ha, get it? That's apparently screamingly funny if you're a neoconservative. I aim to please a wide audience.) "Then I'll conquer England. Then Germany." Etc.

So my Evil General calls in all of his Evil Colonels, and he says "Okay, you get France, you get England, you get Germany," etc.

The Colonel in charge of conquering England then calls all his Evil Majors and explains "You conquer London, you get Southampton, you get Lancashire," etc.

You can expect this process to trickle down through several more layers of authority, but here's the thing: you can't go on subdividing the territories forever. You can't run an organization with only a bunch of managers, because sooner or later somebody has to do the actual work. You can't have some little underling running around saying "Okay, you conquer this microbe, and you conquer that microbe."

What you need is a terminating condition. On some level, you simply have to have a whole lot of Evil Privates, and the Evil Sergeants will point at the enemy and say "Go now and kill that guy over there." Privates don't get to delegate.

So my Privates kill people, which is something that is in some way completely different from what everyone else is doing, which is just splitting up the territories and telling somebody else to do the work.

Eventually, all my Privates report to all my Sergeants, announcing "Territory secured, sir!" Then all the Sergeants report to their respective Evil Lieutenants, and so it goes. Up the chain, eventually reaching my Colonels, who say "Country secured!" and my Generals then come to me and say "Continent secured!" and then I chortle with glee in my Evil Lair. "I've done it!" I say. "I own all the continents, and the world is now mine. MINE! Mooha, mooha, mwahahahahaha haaaaaaaaaaa!!!"

Or words to that effect. I'll work on my speech when the time comes.

Today, Merge Sort. Tomorrow, the world

We've just covered a fundamental principle of recursion, known as "divide and conquer." In this case, we talked about literally dividing and conquering territories of the world. Now we're going to bring it back to the domain of sorting cards.

I give you an entire deck of cards to sort, and I say "Put these cards in order. You have three minutes." I know, those instructions are a little unclear because the suits can come in any order. Typically in a new, unshuffled deck, all the spades come first, then the hearts, then diamonds, then clubs; and then within the suits, the cards are ordered from Ace to King. We'll assume that you and I both know and agree on the order of a "correctly" shuffled deck.

So you have three minutes to sort the cards. Now, you know your card-sorting abilities really well, and you think to yourself, "Hmmm, I know how fast I can work. I can finish about half a deck in two minutes. If I do that I'll finish almost all the work, but not quite. I'm gonna need some help."

So you call in a friend, who also knows everything there is to know about correctly sorted decks, and works just as fast as you do. You say to your friend "Hey, glad you're here. Here's what I want you to do. I'm going to split these cards in half, and give half to you. You sort your half, I'll sort my half. Then when I'm done, we'll deal out our two sorted half-decks into one pile, or 'merge' them, and we'll have a whole sorted deck."

So you divide up the deck into two. You have 26 cards, which you sort using your favorite technique (you can use selection sort if you want). Your friend sorts his pack of 26 cards, and then you get together.

You have the ace of spades. You lay it face up on the table. Your friend has the two of spades. He lays his down. Your friend also has the three, so he lays another one down. You have the four, so you lay it down. You continue until the whole pack is done; flip the pack and you can deal them out in perfect order, ace first.

You finished your deck in two minutes, and your friend finished his deck in two minutes. Both of you worked in parallel, so the two of you were done in just two minutes, not four. Merging your decks goes pretty quickly, only taking up another minute. Three minutes have elapsed, and you're done.

Double your fun

I tell you: "Great job sorting that pack, now I've got more for you to do. I have two different packs of cards this time, all mixed together. I want you to sort them out into two piles, one with blue backs and one with green backs. I know this will take more time... I'll give you five minutes."

How long does it take to sort a whole deck? From the last job, we know it takes three minutes. Clearly five minutes won't be enough for two decks, so we're going to need more friends.

So we get two more people in on the action. You tell your friend: "I'm going to split up these 104 cards into two piles of about 52 cards each. You get your half sorted, and I'll get my half sorted. Sort them the same way you did before, but this time always put blue cards before green cards."

But selection sort is way too slow, so you then take your 52 cards and turn to another friend. You say "Now I have 52 cards. You take 26 and I'll take 26, and we'll each sort them in two minutes."

Two minutes later, you're both done. You take another minute to merge the decks. Now you have 52 sorted cards. It's been 3 minutes.

You turn to your friend and discover that, with the help of the fourth guy, he also has a sorted pack of 52. You merge the cards -- there are more than before, but you finish dealing them together in another 2 minutes. Five minutes are now up, and you have a single pile of perfectly sorted cards. Then all you have to do is separate them in the middle, to get two decks.

Generalizing the solution to "n"

By now I'm sure you've got the idea. I can sort four decks, or eight decks, or any number of cards I want. All I need is more friends. Your friends aren't "free" -- they take up a lot of space, demand lunch breaks, and if you're asking for a lot of work they might want to get paid. If you don't like that, then you're free to go back to selection sorting the whole deck. But with one person performing an O(n²) algorithm, the job will take hours if you have a lot of cards. Much better to keep dividing and subdividing your packs until you have a manageable little pile, and then it gets easier to merge a few piles at a time.

The analogy to taking over the world should be clear. "Divide and conquer" is in fact a well known program-writing technique. Splitting the deck and handing the job to friends is directly analogous to filtering the world by smaller pieces of land, and then handing them to lower ranking underlings.

Another point this illustrates is the frequently recurring theme of trading space for time. As I said before, the more friends you have sorting cards, the more costly the job is. Inside the guts of your computer, what this means is that using a recursive algorithm eats up more of your computer's memory. This can cause everything else in your operating system to run slower, if you start using up too much memory.

On the other hand, computers these days have a lot of memory, and unless you're trying to run World of Warcraft while you're computing, most of your memory is often sitting idle. Why not throw more storage at the problem, if the time saved is so great?

Better yet, thanks to advances in parallel computing, it's now possible to actually physically divide up the work among multiple machines. You order one computer to sort half the cards, and another computer to sort the other half. Then you just take up a little network traffic to have them report to a master server, which consolidates the information.

One example of a popular program that takes this approach is the SETI@home project. We may never discover intelligent life elsewhere in the universe. But if we want to try, we've got massive task collecting readings from different areas of space. SETI takes advantage of the idle time on computers whose owners have voluntarily installed their program. Your desktop runs the program when you enter screen saver mode, analyzing different areas of space, and the SETI server gathers whatever interesting information that you discover.

Now that everyone's up to speed on the basics of divide-and-conquer, I'll go over QuickSort next time.

Big-O Notation 3: Showing off how you think

2009-03-12T07:00:00.005-05:00

Some job interviewers ask you to describe your career history in great detail. Some want you to to explain the most obscure facets of the language you'll be working with. And some will give you a puzzle and ask you to design a program that solves it.

This last category is by far my favorite sort of opportunity in an interview. I'm a programmer because I love solving puzzles, so showing off that love is far more likely to make me look good than struggling under pressure to remember whether it's ArrayList or Vector that is thread-safe. (Tip: It's Vector.)

When you get asked a puzzle problem, remember above all else that the interviewer is much more keen to know how you think than whether you get the "right" answer. There may be some specific technique that they are hoping you know. But even if the answer is not immediately obvious, don't panic. If you sit there and explain your reasoning, refining your technique out loud, you can make up a lot of ground by showing that you can think on your feet.

A good example is the question I got from the Director of Engineering at Digital Motorworks. Not only did I get the job, but that portion of the interview went so smoothly that I wrote down the question, my answer, and his reaction to save for posterity. Here is a recap of the problem:

You're responsible for implementing a method called "sumExists." This method should read two arguments: an integer, and an array of integers. The return value will be a boolean, which is true if and only if there exists some combination of two distinct elements in the array that sum to the original integer.

For instance, suppose you call the method in this way:
sumExists(5, [7, 1, 2, 6, 4])
The array contains the elements 1 and 4, and 1+4 = 5, so the method should return true.

I immediately jumped to the most obvious solution -- not because I expected it to be right, but because I wanted to find some answer quickly and then improve it. I said:

"If you wanted to use brute force, you could just inspect every element of the array, and compare it to every other element of the array, and see if they sum to the first number. But that would require you to perform O(n²) operations, which is dumb. So I would like to find a better solution.

"Suppose that we sort the array. That would take O(n*log n) time (QuickSort, remember?) to complete. Where does that get us? Well, then we could quickly find the largest number and the smallest number of the array and compare them to each other. We'll put counters on the left and right ends of the array, and add those values. If they add up to the target, then we're done. (Note: in the example, the sorted array is [1, 2, 4, 6, 7]. The high and low numbers are 1 and 7, which add up to 8. Too high.)

"If the resulting number is too high, then the biggest number must be too big. So we'll move the right hand counter to the left and try adding a smaller number to the smallest. On the other hand, if the sum is too low, then the smallest number must be too small. So we'll move the left hand counter to the right and try again.

"By doing this we'll be able to test pairs of high and low numbers until either we find the sum we need, or the counters meet in the middle. If the sum is correct then we return true. Otherwise, return false.

"Scanning the list in this way requires only one pass, which takes O(n) time. But the sort was already longer, it takes O(n*log n) time. The time to scan a large array once would be much smaller than the time to sort, so we ignore that factor. This solution takes O(n*log n) time."

As I said, I wrote down the response and saved it. So this is more or less a direct quote: "I've been doing this for a long time, and there is not one person in a hundred who has given as thorough and correct an answer as you just did."

There were other difficulties with getting this job, based on my short experience with specific technologies. I'm convinced, though, that this was the best part of my series of interviews, and it got my foot wedged pretty firmly in the door.

Writing software is fundamentally different from working on an assembly line. You don't solve the same problem twice. You don't write the same code twice. If you are repeating yourself, then you are in some way failing to leverage past experience. You should be moving the duplicated code into a common function, or a common library, or something, so you can stop working on problems that have already been solved, and get the business of making your program do something new and interesting.

Because of this non-repetitive approach, it's important to be able to think about every problem from multiple angles, to try and relate it to past experience and evaluate different kinds of solutions. Big O Notation is one tool for being able to evaluate how you're doing.

Count on this

2009-03-11T07:00:00.005-05:00

Let's switch things up a bit and just do something for fun. How high can you count on your fingers? Ten, you say? Amateurs. I'm going to teach you how to count much, much higher... without even taking your shoes off.

However, you're going to have to learn to count in binary first. Again, this is a very basic topic to computer science students, but I hear that there are plenty of non-programmers who read this blog. For their benefit, I'm going to give a primer. If you already know binary, feel free to skip down to the next bold header.

How to count in binary

When you count by tens, the digits can be represented as wheels on the odometer of your car. The right-most wheel goes:

1, 2, 3, 4, 5, 6, 7, 8, 9…

Then what happens? There is no "10" printed on the wheel. So where do we go next? The rightmost wheel flips from "9" back to "0", and as that happens, it also pushes the next wheel up by 1. So you have a 1 and a 0, and that's ten.

11, 12, 13, 14, 15, 16, 17, 18, 19…

Then the first wheel again flips over from 9 to 0, which in turn advances the second wheel from 1 to 2. Twenty. Right? Don't tell me this is hard, my son Ben understands this and he's in first grade.

So anyway, things are pretty much the same from here on out, until we get up to:

97, 98, 99…

And now? Well, the first wheel flips to zero, which in turn advances the second wheel. But the second wheel is already maxed out at nine, so it flips to zero, which also advances the third wheel, so now that wheel reads "1". 1, 0, 0. A hundred. Got it?

Okay, that's base 10. Binary is a similar system, except that it's got a severe shortage of numerals. Whereas we were using all the numbers from zero to nine, in binary you only have two possible values: one, and zero. Like a light switch: on, or off. Circuit open, or circuit closed. That's how a computer works. But with just ones and zeroes, you can represent every positive integer if you have the patience.

Let's imagine we have an odometer like before, but this one has very small wheels. They flip from 0 to 1. Then they flip from 1 back to 0. When they flip to 0, they advance the next wheel. Okay?

So your odometer reads:

0: 00000

Advance the rightmost counter by one:

1: 00001

Advance the counter again, and it flips to zero while dragging the second wheel along:

2: 00010

So that's two. Ten is two, in binary. Makes perfect sense, right? Advance the right hand wheel one more.

3: 00011

Next time we advance, both of the first two wheels will advance the next one over.

4: 00100

One hundred is four. I think you can take it from here.

In base ten, every digit represents a value that is ten times the previous digit. So the first digit is worth one, the second digit is worth ten, the third digit is worth a hundred, the fourth is worth a thousand, and so on.

Similarly, in base two, every digit represents a value that is two times the previous digit.

1 -> 1
10 -> 2
100 -> 4
1000 -> 8
10000 -> 16

Makes sense, right? You can write out any string of ones and zeroes and figure out what number they represent in binary by adding up the digits. For example,

10110 = 16 + 4 + 2 = 22

Okay, here's the fun part.

How to count to 1,023 on your fingers

Hold out your hands, palms upward. Now make them fists. No fingers are extended. That's zero.
Extend your right thumb. The right-most digit is now set to "on". That's one.
Close up your thumb, but extend your right index finger. That's two.
Extend your thumb again, and also leave your index finger out. Three.
Close up your thumb and index fingers, but then extend your middle finger. That's four. It is also an obscene gesture to most people, so if you're in public, make sure your hands are under a desk or something.

That's really all there is to it. The highest you can go with this system is 1111111111 in binary, which is 1,023 in regular counting (2¹⁰ - 1).

Other numbers that form obscene gestures to Americans: 128; 132

Numbers that may be obscene to Europeans: 6; 384; 390. They may also be interpreted as peace signs or a Richard Nixon impression.

What can you do with this? Not much. You can kill about ten to twenty minutes. You can also probably perform a cheap mind-reading trick if you have an accomplice who can also do it. ("I'm thinking of a number from one to a thousand." "583. I certainly wasn't paying attention to the funny way you're holding your hands.") And finally, you can waste a perfectly good afternoon writing a silly blog post.

By the way... if you DID take your shoes off, you could count to 1,048,575.

Big O Notation 2: Sorting

2009-03-10T07:00:00.010-05:00

As a Card-Carrying Nerd (you have to mail away exactly 314 cereal box tops for your card) I find entertainment in some very unusual activities. For example, I like to execute algorithms by hand. When I find a pack of cards lying around, I often find myself shuffling them, dealing out about 10-20, and operating a QuickSort on them. Sometimes when I have a stack of old bills and I want to eliminate duplicates while retaining the latest copy for my records, I'll even lay them out in a grid on the floor and perform a bucket sort.

Sorting algorithms are material from Intro to Computer Science 1, but I'm going to give a very condensed overview of the topic as background material to what I'm going to go over in a future post. If you're already rock solid on sorting algorithms, I suggest you skip or skim this one, and I promise I'll get to more practical discussions later.

You'll remember that in the last post on Big O, I explained that a "dumb dictionary search" (just viewing each word one at a time) requires O(n) time, while a more efficient search (which is also known as a "binary search") requires only O(log n) time, which is a lot shorter. But the binary search only works if the words are in some kind order already. If they're all scrambled up -- if "xylophone" comes before "cereal" comes before "pheasant" -- then you have no choice but to execute a dumb search. There's no other way to find your word besides looking at every entry to make sure you didn't miss any.

Therefore, it's often helpful to sort a list of things (such as dictionary words). Of course, sorting a dictionary might take longer than actually searching it. But if you have to search the dictionary multiple times, it's worth it. You eat the cost of sorting only once, but you get to do binary searches as many times as you want after that.

Suppose we take a pack of cards and deal out "n" cards at random. Let's make this quick and pick 5. I'll imagine they came out like this:

5, A, 7, K, 3

How long will it take to put these cards in the correct order? Well, naturally it can't take less than O(n) time. It's easy to see why. Suppose you had a magic function which automatically skimmed the entire list in no time at all to find the smallest number remaining. Then you could scan these cards and find the Ace first, and put it in the first spot. Then you find the 3, and put it in the second spot. And so on. Then the sequence of events would look like this:

A, 5, 7, K, 3 (we put the ace in the first spot, but we needed to move the 5 out of the way, so we just swap their positions)
A, 3, 7, K, 5 (3 swapped with 5)
A, 3, 5, K, 7
A, 3, 5, 7, K (sorted!)

This is the most efficient sort possible, but even with our magic function you still have to move each card to the correct location. There are n cards, so it takes n moves. So no matter what happens, we can't do better than O(n). (Technically, it took "n-1" moves to finish, because once the first four cards are sorted, the king MUST be in the right place. There's nothing to swap with. But remember how I said before that constant multipliers don't matter? Subtracting a 1 definitely doesn't matter. In fact, we ignore any constants that are added to or subtracted from the outcome. Order of magnitude is all that counts.)

Unfortunately, we don't have a magic function that takes no time to find the Ace, so we actually have to read the cards in order to find it. How do we do this? Well, we could read the entire list manually, finding the Ace by inspecting every card. This is a technique known as a "selection sort," for the obvious reason that we are looking through the unsorted list to select the smallest number. Like in the dumb dictionary search, that would take O(n) reads to accomplish (technically n/2 on average, but constant multipliers don't matter).

But it's worse than that. Because we have to move n cards, AND we have to read n cards each time we move one. So we do n*n things, which means that this sort is O(n²).

Terrible. Remember, our dictionary had 170,000 words. You square that, and you're doing almost thirty billion operations. There must be a better way.

There is, and one example is QuickSort. QuickSort is a recursive algorithm that is a little bit tedious to explain in a blog post, but it's so successful that it is implemented as a standard feature of many languages. If you type "sort @mylist" in Perl, you are instructing Perl to perform a QuickSort in most cases. If you have some time to kill, I recommend that you look up QuickSort on Wikipedia, lay out some cards, and try to figure out how it works. It's kind of cool.

QuickSort usually requires a time of O(n*log n), and you can't do much better than that. Well, there are some tricks you can use to speed it up if you know exactly what sort of data you're dealing with, even getting pretty close to O(n) in some cases. But for the most part, you're stuck with n*log n. And this makes sense: In the dictionary example we discovered that you can find a word in O(log n) time, and it takes O(n) time to move all the numbers, so in the best case we are going to find a number as quick as possible and then move it.

If you sort a 170,000 word dictionary in O(n*log n) time, how long will it take? Log 170,000 is about 5, and multiplied by 170,000 itself is about 900,000. That's not fast, but it's nowhere near as bad as 30 billion.

This is the last purely academic post I'm going to write about Big O notation. By now, I'm sure some readers are asking "What's with all this theory? Am I ever going to use this professionally?" My answer is: "You might. For one thing, you can use it to show off in job interviews." Next time I post about Big O, I'll explain how.

Y2K supplemental

2009-03-05T14:20:00.004-06:00

I was looking for a good article that explained Y2K from all angles -- how the problem arose, and an why it ultimately wasn't as serious as people thought. I couldn't find it before posting, but I like this 1999 article by Tom Christiansen, a major contributor to the Perl programming language. Not only is Tom an excellent writer, but he accurately dismissed Y2K concerns as overblown before it hit. You gotta respect a guy with that kind of clear thinking, as well as the courage to voice an unpopular opinion.

A retrospective on the terrifying millenium bug

2009-03-05T08:00:00.007-06:00

It's December 31, 1999. I've got some neighbors over at my house watching movies, and we're all waiting for the rollover. One of them asks me what time it is. I check my watch. "11:58," I say. "I guess it's time for the world to end. Want to go outside and watch the fireworks?" Everybody agrees.

We go outside, and there are fireworks, all right. My neighborhood is full of people who love fireworks, and they never fail to put on a good show twice a year, on New Year's Eve and Independent Day.

Glancing up, I wryly remark: "The street lights are still on. Maybe it has to be Pacific Time."

It's the end of the world as we know it

For those of you who are too young to remember or who didn't pay attention to the news from about 1997 onward, January 1, 2000 was the day that civilization as we know it was supposed to collapse. You see, many computer programs at that time stored information about dates as two digits numbers, which would confuse many computer systems at rollover. A year of "00" could just as easily mean "1900" as "2000."

Therefore, it was theoretically possible that numerous programs would break in a spectacular fashion, causing bills due in 2000 to be flagged as 100 years overdue. With interest. People spent several of the preceding years gloomily talking about how all the computers of the world were completely interconnected, and therefore any systems that did not address this problem might somehow corrupt all the other systems they were connected to. The Simpsons even devoted a hilarious segment of their annual Halloween special to Y2K in 1999.

Here's what one high profile Y2K alarmist, Gary North, had to say about Y2K (emphasis added):

Who knows where it will start? Only one thing seems certain: it WILL start. And when it does, every market institution and every government will suffer enormous setbacks. ...

Banking is the obvious domino. Here's another: shipping. What happens to cities if gasoline is unavailable to truckers? If the computers that control train schedules break down? If rail freight cars cannot be located by defective computers? Think about your supermarket's shelves.

What happens to production when "just in time production" becomes "bottleneck production"?

Here's another: farming. Modern commercial farming is tied to hybrid seeds. The plants produced by hybrid seeds produce seeds that will not produce healthy plants if planted. Every year, almost every large farm on earth must re-order another batch of hybrid seeds. If, for any reason, the seed companies fail, or the banks fail, farmers will not be able to plant anything. This will lead to a famine. Let's not hedge our words: FAMINE. There is no way today to get enough non-hybrid seeds into production in order to avoid this problem. If this is one of the dominoes, the result will be widespread starvation.

Hey, everyone! Remember that one time when the banks failed, governments collapsed, truckers were immobilized, people everywhere were starving, and civilization as we know it ended? Good times, good times.

In the immortal words of John Cleese, "I got better..."

Disclosure: Gary North was and is an extremely weird dude. He's a dominionist -- a very special strain of religious zealot who believes that Democracy should be eliminated in favor of a Biblical variety of sharia law. Complete with public stonings. North has made a career out of predicting the end of the world at regular intervals, and in the late 90's he just happened to get more traction than usual.

Even so, panic over Y2K was widespread. I was teaching programming classes at that time, and the course requirements forced me to give students an essay and presentation assignment. Y2K was one of the possible topics I assigned. Three or four students chose to write about it, and every single one of their papers unambiguously predicted doom. Sometime in January 2000, I wrote a mass email to all the former students whose addresses I had, joking "Everyone who wrote about Y2K last year will now retroactively fail the class."

Funnily enough, I personally fixed a Y2K bug. I was working at the time for Bike.com, one of those multitudes of "dot com" companies that was ultimately doomed to fail, but hadn't gotten the memo yet. I wasn't a full-time employee; I worked for Compuware, a development shop that farmed me and many other mercenaries out to various little companies for a limited time. As such, I had a grand view of many such companies during the infamous tech industry crash, but I didn't go down with any of those ships -- at least not until Compuware ran out of work for me and then folded their Austin branch entirely.

Anyway, January 1 fell on a Saturday, so I didn't get back to work until the third. "We have a problem," my supervisor told me. "Some of the dates in the bike sales page say that they went online in the year 19100."

I hunted through the code for the offending page, and quickly figured out what was going on. The code was written in Perl. Dates in that language represent the year as an integer counting up from 1900. So the year "1998" is represented as "98," and so on. Some bright developer who came before me had decided that the proper way to write the full year was "19 . $year". The period is a concatenate operator, so this bit of code translates to "write the number 19 and then write the year." Obviously, when the year became "100" the long text representation became 19 followed by 100, or 19100.

That was easy to fix. I replaced the period with two zeroes and a plus sign, making it display "1900 + $year", because 1900 + 100 = 2000. I searched all the code for variations of the string "19 ." and performed the same trick everywhere. The whole operation took less than 20 minutes. Then I went to my supervisor and announced "Your Y2K problems are all fixed. That will be ten million dollars. In tens and twenties, please."

...And I feel fine

If there's a lesson to be drawn here, my take is that software systems are way more resilient than we give them credit for. People tend to have a certain degree of unreasoning superstition about computer programs. They are these mysterious and terrifying black boxes that are supposed to serve us, but occasionally fail in inscrutable ways for their own malicious reasons.

Minor tangent: Many people I talk to seem genuinely fearful that the scenario in Terminator or The Matrix really will play out someday; we'll wake up and discover that SkyNet has become intelligent, and also mad as hell at the human race, not to mention being a super-genius planner that can outsmart everyone on Earth. I always have to point out to these people that it took human beings two billion years of evolution to become as smart as they are. Even with the benefit of all that complex software in their brains, it takes every human child some eighteen years to explore the world, form up connections and memories, and become a fully functioning adult.

I kind of think we'll notice robots becoming self-aware pretty far in advance, and it will probably be on purpose. Plus, there's no reason to assume that the intelligent robots will naturally turn on their creators, just as we don't assume that every child will eventually desire to kill his parents. There are some outliers who become sociopaths and go on a mass murder spree, but most kids do actually grow up to be non-maniacs.

For the time being, all our efforts at what we laughably call "Artificial Intelligence" still result in programs that are fairly dumb, and extremely narrow in their scope. Computers actually do what we tell them to do. We programmers frequently tell computers to do the wrong things, in the wrong ways, or fail to be sufficiently precise. But robust systems like banking are generally written in such a way as to be extremely modular, so that failures are local problems that don't destroy all the data, or accidentally transfer millions of dollars into your bank account. (Sorry, fans of Office Space... it's really not that easy to rip off a bank. They wouldn't stay in business very long if it were.)

Certainly there are cases where a misapplication of computers can do something so dangerous that it jeopardizes national security. Here's an interesting recent story of government secrets being sent to Iran via BitTorrent. But as you might expect, the computer itself is not the villain: like deliberately written viruses, stealing files in this manner is a deliberately designed spy technique that is executed to take advantage of existing software. It takes an intelligent agent to make computers do something harmful in a creative way.

So I remain highly skeptical of a catastrophic bug that will magically, accidentally, without deliberate effort, somehow cause a simultaneous collapse of millions of computer system worldwide. In the Simpsons episode I mentioned, all the computers in the world are fixed, but because Homer fails to fix his own particular system, that one failure somehow "infects" the rest of the internet. Comedy!

But the truth is a lot more mundane: individual programs screw up all the time. The better ones are written in a way to isolate and localize the errors. The worse ones either fix their problems or go obsolete.

Many companies were destroyed in the aftermath of 2000, but it wasn't the fault of the milennium bug; it was just another example of human error. In this case, it was poor business planning. Go to bike.com now if you want. There's no impressive web site with a massive database of bicycle sales. Instead, it's a small shell of a site that hosts a few third-party ads. This isn't the company I worked for; those guys probably went bankrupt long ago because very few people actually want to buy bikes on the internet. The domain has been taken over by a company whose business strategy is barely more ambitious than cybersquatting web sites.

So worry about failures due to ordinary hubris, sure. But don't worry about a massive robot uprising, or a simultaneous failure of all the world's software. And if you want to rip off investors, there's no need to count on obscure computer glitches, just do it the old-fashioned way: lobby to roll back industry regulations, invest in super-risky schemes, and then push your losses on the taxpayers on the grounds that your company is too big to fail.

Speed up your programs with Big O (part 1)

2009-03-03T07:10:00.003-06:00

Part of what inspired me to do this blog was that I found myself explaining "Big O Notation" to two coworkers this week. My coworkers are smart people, but I was a little surprised to find that some aspects of computer science aren't common knowledge.

My intent is to make this blog accessible to software amateurs, but many readers will probably have heard this stuff before. Hopefully I can at least make the description entertaining, because I think it's an important one to be familiar with. If you happen to be one of those people who dimly remembers this topic from your "Intro to Computer Science" class, but forgot it promptly, it's time to learn it again. It matters.

Job interviewers often ask questions where they require you to make up a program that solves a programming puzzle. I have impressed the hell out of numerous interviewers by making up a solution, analyzing the solution in Big O, and then coming up with a more efficient solution. I didn't always get those jobs, but the feedback was always "You seem like an excellent candidate, very solid on the fundamentals, but you don't know enough of the specific technologies we work with." When I got the job at Digital Motorworks last year, the director of engineering flat-out told me that mine was the best answer he ever heard to his question. So pay attention!

A "dumb" dictionary search

Suppose you are looking for a word in a printed dictionary. There are two ways you can do it, a dumb way and a smart way. The dumb way is: read the first word. Is that the word you want? No. Go to the next word. Is that the word you want? No. Go to the next word. And so on.

I just looked up how many words are in a typical dictionary. It's about 170,000. So how long will it take you to find the word you want? Well, it depends, of course. If you are looking for "aardvark," then you will have to look at only one word, or just a few. If you are looking for "zymurgy," then you will have to look at nearly all 170,000. On average, you can expect to read through 85,000 words: half of 170,000.

Get Smart

Nobody reads the dictionary that way, of course. Think about how you would really look up a word, such as "program." Open the book to the middle. You find the word "mouse." That is before the word you want, so divide the right side of the dictionary in half, pick another page, and look again. "Teacher." That is after the word you want, so divide the space between "mouse" and "teacher" in half and look again. And so on.

This technique is much more efficient than the dumb search, because it takes advantage of the fact that the dictionary is sorted for you. How long does it take? When you first open the dictionary, you are splitting the search space in half: instead of 170,000 words, you now have 85,000 words to look at. Then you split the search space in half again. With each page turn, you divide the number of words remaining for you to look at. So here's how it goes:

170,000
85,000
42,500
21,250
10,625
5,312
2,656
1,328
664
332
166
83
41
20
10
5
2
1

18 Words we looked at. Instead of 85,000. Much better, right?

170,000 is a very specific number of words for a dictionary to have, so let's generalize this. The number of words in the dictionary is "n". How long did the dumb search take? We read on the order of n/2 words. Therefore, we say that solution took O(n/2) operations. That's all "Big O" means: "O" stands for "Order of." Nothing magical here, right?

How about the smart search? It took 18 searches, because
2¹⁸ > 170,000
(17 wouldn't be enough. Check.) If you fiddle with that equation, you'll find that
18 > log₂ 170,000

So, to speak more generally, the smart dictionary search is O(log₂ n).

With me so far? Now I'm going to get slightly tricky.

When I said the dumb search was O(n/2), the "/2" part is a constant multiplier: it represents the number 1/2, which is always the same. You take O(n) and you multiply it by one half. But really, we don't need to be that specific. We don't know exactly how long each of the operations will take, so when we are estimating compute time, it's pointless to factor in a constant. For instance, if you do 100 operations that each take half a second, or you do 50 operations that each take a whole second, it amounts to the same thing.

So, by convention, we ignore constant multipliers and don't include them. Instead of saying that the dumb search is O(n/2), let's just say that it takes O(n); all we care about is finding the right order of magnitude anyway.

Similarly, I said the smart search takes O(log₂ n). But the "2" subscript in "log₂" is unnecessarily specific too; all we care about is that it's a log. So the smart search is O(log n) time.

Why should you care?

Let's consider some specific values of "n" and see how much time we save by using an O(log n) search instead of an O(n) search.

n=10 -> log n=1

n=100 -> log n=2

n=1,000 -> log n=3

n=10,000 -> log n=4

n=100,000 -> log n = 5

n=1,000,000 -> log n = 6

Obviously, if you are searching ten values, you can probably get away with scanning the entire list, but if you are searching a million values, you would rather have it take about 6 reads instead of a million.

As obvious as that is when I put it like that, I can tell you that there are a distressingly high number of times when I've sat down and analyzed code to discover that something which should easily take O(log n) time is written in such a way that it takes O(n) or even O(n²). The reason for this is that the guy who came before me started out with a small list of items, and then failed to plan for a time when the data would grow out of control to a thousand items or more.

You should be planning for this stuff up front. You should be asking yourself "How many values am I dealing with now? How many values can I imagine dealing with in the future?" If your program is dealing with information about cars, for example, you should think about how many cars there are in the world, and what fraction of those cars will eventually be in your database if you're a big success.

Remember that if you don't plan for this, you will have to put in the effort to change it. But also, by the time it gets to that point, you will have forgotten where the O(n²) function is, so you'll have to put in the effort of finding it and decoding the logic too. That's why you want to be mindful of future bottlenecks for your code as early as possible.

Next time I get around to posting about Big O, I'll be writing a little about sorting routines, interview challenges, and strategies to make basic logic more efficient -- some or all of those, as time and post length allow.

I dream of recursion

2009-03-02T06:18:00.004-06:00

This is a true story. I have told it to my programming classes every time I introduced the topic of recursion.

When I was a little kid, there was a toy that I desperately wanted. We'll just gloss over what it was because it's not in any way important to the story. So one night --

All right, all right, stop whining. I'll tell you. It was... a Ronald McDonald doll. That whistled. Yes, it had a little plastic whistle, and if you squeezed it then it would whistle. As seen on TV. Why in the world would I want that? I have no idea. I just remember that it seemed very important at the time.

So I wanted this Ronald McDonald doll. Very much. But I knew that my dad, who has always been a practical minded guy, would find this toy, well, stupid. So I didn't have the courage to ask him for it. But then to my surprise, one evening I came home from school, and my dad said, "Russell, today we're going to Toys R Us to pick up that Ronald McDonald you've been wanting."

Needless to say, I was ecstatic. We got in the car, drove to the store at the mall, picked up that toy, brought it home, and...

...Then I woke up.

As bitterly disappointed as I was to learn that it was all just a dream, I was filled with a new confidence. I just knew that my dad was going to buy that toy for me, because the dream had so foretold. So I went into the breakfast nook, where I found my dad waiting. I asked him if he would get me the Ronald McDonald doll that whistles, and he says "Surprise! I already got it for you! There it is!"

...And I woke up.

But after having been through this experience twice, I was more certain than ever that I would be getting my toy. Sure enough, I went to find my dad, asking "Did you REALLY get me that toy?" He said "I sure did! Look!" I actually got to play with the thing for a while, and then -- all together now,

...I woke up.

I think you get the idea. It feels like the sequence repeated itself about ten times or so, although of course there's no way to tell. Each time the details of the nested dream were a little different, but the end result was always the same: I was confident that I'd get the toy, I did get the toy, and I woke up. And each time I woke up, the world seemed a little more "real" to me than the one in the previous dream.

Except for the last time. When I really woke up, I knew I was really awake. I didn't even need to bother asking my dad about it in the real world. I know reality.

I never did get that toy. That probably explains exactly why I am the bitter cynic I am today.

The tricky part about this story is still how to translate it from amusing anecdote to actual concept of computer science. If this were true recursion, I would probably remember going to sleep ten times in a row at the beginning, then getting the toy for the first time, and so on. Instead, I started in mid-dream. But nobody ever remembers going to sleep anyway, so we can assume that happened in there somewhere. So if I had to pseudo-code this story, it would look like this:

class YoungRussell {
    void sleep () {
        lieDown(bed);
        fallAsleep();
        dream();

        // perform operations associated with
        // waking up here
    }

    void dream () {
        if(someTerminatingCondition() == false) {
            // no actions before falling asleep
            // again in the dream
            sleep();
        }
        StupidToy ronald = new StupidToy();
        obtain(ronald);
        playWith(ronald);
    }

    // ...
    // auxiliary methods here
}

Wait... where's the actual waking up routine, you ask? Well, you don't need one. Reaching the end of the "dream" routine automatically drops you back into the conclusion of the "sleep" routine, and when "sleep" ends, you just wake up.

I have always found this the hardest thing for people to understand about recursion.

Search and destroy missions for your bugs

2009-02-27T10:59:00.009-06:00

Pop quiz, hotshot. You're new on the job, you have a million lines of code that you've never looked at before, and there's a bug. It's doing something really bad, like taking five minutes to load and then displaying a blank screen. Your boss has some vague idea of what the program should show, or used to show, but it's not doing that. The most specific instruction you can get is "make it look like this" or worse, "just fix it." What do you do??

Take a deep breath. First of all, don't be intimidated by the size of the code. It really doesn't matter. The whole program may have a million lines, but you can be sure it's not actually doing a million things when it tries to run your specific command. Think of the million lines of code as locations on an extremely detailed map. If you want to find a street in Austin, you won't get very far by carefully reading every street name on the whole Austin map. Instead, you want to narrowly focus on the specific path your program takes when you execute your command.

In a nutshell, you are a detective. A crime has been committed: a bug has murdered the effective execution of your program. You know that the perpetrator went from point A (the beginning of the program) to point B (the place where the program is misbehaving). Your first task is to follow a trail of clues and find the suspect. After you know where the error occurred, the last part of your job -- move the suspect into custody by making your program do what it's supposed to -- is relatively easy.

Let me talk math for a minute. I'm going to solve a puzzle live in this post. I have a large number: let's pick 987,654. I want to know what is the square root of this number to the nearest integer, but I'm not allowed to just hit the square root buttonon my calculator. Instead, I can only pick a number and multiply it to see if my answer is right. How will I find the answer?

I'll indent my solution in the next several paragraphs so you can see where the rest of the post continues. Think of how you might solve it before reading on.

We could brute-force it with trial and error. 1*1 = 1. Nope. 2*2 = 4. Nope. 3*3 = 9. Nope. And so on. This could take a while.

Let's be smarter about this. We want to get CLOSE to the number and then home in from there. So let's start with an educated guess. About what order of magnitude is my number? 987654 is pretty close to a million, and it's easy to figure out the square root of 1000000: it's 1000. (Just cut the number of decimal places in half.) So we know the answer is less than 1000.

Is it 900? 900*900 = 810,000. Too small. Let's pick a bigger number. Go halfway up, we get 950.

950*950 = 902,500. Still too small. Let's try 990.

990*990 = 980100. Hey, we're getting closer! But it's still too small. How about 995?

995*995 = 990025. Now it's too big, but just a little bit.

At this point we know that it's between 990 and 995, so let's just step backwards from 995 until we find it.

994*994 = 988036. Too big.
993*993 = 986049. Too small.

Ah ha! We've found the answer! We know that the square root of 987654 is more than 993 and less than 994. In other words, it's 993 point something. If we wanted to, we could keep playing this game to guess more places after the decimal. But I said that we'd only go to the nearest integer, so "993 point something" is good enough.

Let me check with the calculator now that we've settled on an answer:
sqrt(987654) = 993.808. See? I was right.

I've just demonstrated something very much like Newton's Method of approximation. Instead of brute forcing the solution by walking through every possible number, we started in a likely spot and quickly converged on an answer. Now, what insight does this give into debugging?

Figure out a likely entry point for your code. For instance, if your program errors out when you click the button that says "Display all prices" then search all your files for the exact string "Display all prices". If it only exists in one place, you've got a location to start looking, and you're off.

Quick sanity check. Once you've found this spot in the code, you might want to temporarily change the text to "Display all prices!!!" Then reload the program and see if the exclamation points show up. I can't tell you how often I've found what I thought was the right spot in the code, but then wasted a bunch of time wondering "Why didn't THIS change do anything?" when I'm actually not in the right spot at all. This hearkens back to the important principle from yesterday's post: Programming is both theoretical and experimental. Don't just trust your guesses to be right, do the experiment!

So you know where your code started, now where is it going? Off the top of my head, there are three important tools you have for narrowing down the location of your bug.

Use a debugger. Decent program development environments all have a debugger. Learn how yours works, it is your best friend. With the debugger, you can step through your code a line at a time, see exactly where it's going, spot check your variables, and trace back where you've been. However, some types of development don't make debugging easy. For instance, if you're developing web pages, the program runs on your browser and not in your editing environment. Sometimes code can load an unrelated program and you have to go to a different tool. So if you have no debugger or you run out of use for it, you have to go to your backup plan:
Print statements. Lots of print statements. Print what you're doing: "X was set to 15!" or "Entering function..." "leaving function...". Just remember that debug statements in shipped code look really bad, so don't fail to clean up all your print statements when you're done. A good habit is to put a distinctive string in front of all your prints to make sure you don't miss any. For instance, sometimes I will make debugging statements like
print "RG Entering function foo";
The string "RG " rarely shows up in code, so I can search for all occurrences and delete them when I've fixed my problem. (Some languages use "ARGV", but if you include the space after "RG " then this won't show up in the search.) If you are willing to put in a little extra time, the preferred solution is to write a "printDebug" routine that only prints when a flag is set, so that you can globally turn off all debug messages if necessary. This isn't always worth the effort, though, when working across multiple files that don't share libraries.
Comment out large blocks of code. Just remove them entirely. Don't underestimate this technique. If your problem is that the program is slow, and you comment out an entire function, and it STILL takes five minutes, you immediately know "Guess that function isn't causing the slowness!" Then you don't have to waste your time looking there.

A word about print statements: It's not necessarily that easy. Sometimes you will add a "printf" command (C) or "cout" (C++) or "System.out.println" (Java) and you see nothing at all. "Print" in this case means "do whatever you can to make it visible." If you're coding to a web page, write to the web page's output stream. If you're writing Javascript, use "alert" statements to pop up a window. If your program uses a log file, write to the log. If you're writing a windowed program, you might want to make a special panel that you can use to display debug messages. Just figure out what makes the most sense to make your messages visible.

Basically the objective here is to narrow down all the possible locations where the bug might be. If your program crashed, where did it crash? If it was supposed to display a picture of a flower and didn't, did it even reach the "drawFlower()" function? If so, why is drawFlower broken? If not, where did it make a wrong turn?

So you're a detective, casting a wide search net at first but tightening the net. From the million lines of code, we've found that the error must be happening in this 1,000 lines. Then we cut it down to 100 lines, then 10, then 1: this exact line is where it misbehaved.

As you tighten your search net, you will dig deeper into the code. If you get down to one line and discover that it's a function you control, you're not done yet: you have to step into that function and keep going. For instance, I comment out a single line and discover that the Bad Thing no longer happens. I uncomment the line, step into the function, and comment out the entire function body. Same result. Good, my guess is confirmed. Now uncomment half the body. Now does it still do the Bad Thing? Is it getting inside this "if" block, or the "else" block? Why did it go here and not there? What values is it seeing when this decision is made?

Ultimately, fixing a bug in a million lines of code often comes down to changing one line. So finding where the bug is, is actually 99% of the work. Hence, this is probably the single most important skill you can develop.

Coding is both theoretical and experimental

2009-02-26T15:55:00.005-06:00

"As soon as we started programming, we found to our surprise that it wasn't as easy to get programs right as we had thought. Debugging had to be discovered. I can remember the exact instant when I realized that a large part of my life from then on was going to be spent in finding mistakes in my own programs."
- Maurice V. Wilkes, inventor of microprogramming

My father is a computational physicist. That's a job description that didn't exist when he started working a few decades ago, but he made the decision to transition into that role.

In the past, scientists have generally fallen into two broad categories: theoretical, and experimental. Theoretical science is distantly related to pure math. You have an arsenal of known scientific facts, you know the equations, you analyze those equations and learn new consequences that result from them. Experimental science is more directly involved with measuring and testing the real world. You come up with ideas, you do something to test if your ideas match reality, and if they do, you've got a theory. (Ultra-simplified version.)

A computational scientist is a different beast altogether. A computational scientist can create models of reality using a computer simulation to represent theoretical information. Then he can run the simulation with different parameters, finding out what would "really" happen if you changed the initial configuration.

When we deal with things like planets, we pretty much know how they behave in general, but you can't say "I wonder what would happen if we put three planets at this distance from each other" because there is no practical way to set up an experiment by moving planets around. Instead, your computer can simulate what would happen, and you might learn some things from the simulation that weren't obvious just by running the equations.

Programming in general is like that: it's both theoretical and experimental. You can eyeball your code, trace the logic by hand, and figure out what it should do. That's theory. Then you can run the code, either logging the output or stepping through it with effective debugging tools, and find out what it really does. That's experiment.

In decades long past, computer programs ran on expensive mainframe terminals which could take hours to complete a single execution via, for example, punch cards that were hand-fed to the computer. Because terminal time was at a premium, writing a program with any bugs could be a costly mistake. It was more economical to spend hours poring over the punch cards or machine code, making dead certain that the program would run correctly before you fed it to a computer. In other words, programmer time was cheap and computation time was expensive.

Today, the reverse is true. Rather than hours, it takes seconds to compile and run a computer program. Programmers are still free to spend their time making sure that the code "should" run before they run it. However, in many cases it is easier and smarter just to run it and see if something goes wrong. Following Moore's Law, computer time has become incredibly cheap.

A smart programmer takes advantage of this and does a mixture of both theory and experiment. Rather than write an entire program from scratch on paper, then running it and hoping for the best, today's programmers should view a program as a series of components, to be built and tested bit by bit, making sure that each part behaves properly through real demonstration. Unless I'm in the middle of a major rewrite that deliberately broke old code, I will rarely leave my program in an uncompilable state for more than fifteen minutes, and usually a lot less. Each change can be tested to make sure that it has predictable behavior.

In an optimal testing environment there are no computer errors; logic errors come from the developers. That's not a failing on the part of the developer; to err is human, and the point of this style of coding is to recognize and anticipate those errors. The benefit of working this way is that if you make a mistake, you get immediate feedback that something has gone wrong.

If you write a large number of changes and then discover an error after running them all at once, you are temporarily stuck. You have no way of knowing which of your changes was responsible, so you have no choice but to backtrack and break your code into smaller fragments to isolate the problem... which is exactly how you should have been writing the program in the first place.

So how do you approach a problem that requires debugging? I advocate an approach that uses something akin to the scientific method to systematically track down and destroy bugs. I'll discuss this in a future post.

Programming thought-stuff

2009-02-26T10:39:00.004-06:00

Hi, my name is Russell Glasser, and I've been writing software professionally since 1995. I have a BS in computer science from UC San Diego (1997) and an MS in computer engineering from UT Austin (2007). I currently do Java Enterprise development for a logistics company in Temple, TX. In my past lives, I've done work that included scientific modeling, 3D virtual reality simulations, educational games, and data mining. I also tutored a kid for two years and taught programming classes for about six months.

I'm a prolific blogger, and for a while I've been kicking around the idea of starting a new blog to share thoughts with my colleagues about software development. I decided to take the plunge today. I don't know if I'll be updating frequently or not, but add me to your feed and you can read my one post a year if that's how it turns out. :) Also, I encourage people to ask questions, as it will give me more incentive to write new posts. The only restriction is that I'm going to insist on keeping this as a purely professional blog, which means I will not field any questions that aren't at least marginally related to software. If you want to discuss other topics, look me up or email [rglasser *at* apollowebworks *dot* com].

The title of this blog was inspired by a quote from The Mythical Man-Month, by Frederick Brooks. When I read it, I discovered that it perfectly encapsulated the reason why I decided to pick software as a career path.

Brooks wrote:

"The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds castles in the air, from air, creating by exertion of the imagination. Few media of creation are so flexible, so easy to polish and rework, so readily capable of realizing grand conceptual structures.

Yet the program construct, unlike the poet's words, is real in the sense that it moves and works, producing visible outputs separate from the construct itself. It prints results, draws pictures, produces sounds, moves arms. The magic of myth and legend has come true in our time. One types the correct incantation on a keyboard, and a display screen comes to life, showing things that never were nor could be.

Programming then is fun because it gratifies creative longings built deep within us and delights sensibilities we have in common with all men."

I hope you enjoy this blog.