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.
Wednesday, October 12, 2011
Monday, September 19, 2011
Operation HackMaster Crit Tables, episode 2
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 powerfulslave 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:
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:
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:
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.
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
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>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.
{
private Listranges;
private class Entry
{
protected T item;
protected int low, high;
public Entry( T i, int l, int h )
{
item = i;
low = l;
high = h;
}
}
...
}
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.
Wednesday, September 14, 2011
A bit about data structures
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:
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:
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:
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.
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;(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.)
String str = "Hello world.";
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];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.
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;
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.
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.
Thursday, September 8, 2011
Operation HackMaster Crit Tables, episode 1
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.
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.
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...
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...
Tuesday, August 23, 2011
Recruitment spam
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.
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.
Monday, August 1, 2011
On learning to love your users, who are idiots
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.
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.
Thursday, July 14, 2011
Programming puzzle: Testing probability
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:
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:
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.
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.
Thursday, July 7, 2011
Adventures in junior programming, episode 3
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:
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.
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.
Monday, February 28, 2011
My very late entry to mobile computing
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.)
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.)
Subscribe to:
Posts (Atom)