An Easy Riddle And A Hard Riddle: What It Means To Think In Code
by Chris Klimas
Close your eyes and think of a computer. (It's too bad this essay isn't about ice cream.) You might think of a box with a screen that has windows on it, beeps sometimes, and doesn't do what you want it to. But to really understand computers, beyond the fact that they come in a plastic box, and to understand why I write code for computers, beyond the fact that I tend to obsess on random things, you have to close your eyes and think of a really good riddle.
Here's mine: this is the easy riddle. You may have heard it before. Imagine that you stand on one bank of a river and you happen to have a wolf, a goat, and a head of cabbage with you. Perhaps they're your immediate family transformed by an evil sorcerer. Perhaps these are your only earthly possessions that you must sell to pay for medicine for your sick son. But you must cross this river with all three things.
To make things interesting, there is one restriction: you can only bring one thing with you in the boat at a time. You must make at least three trips—and there is a correspondence between the wolf, the goat, and the cabbage. The wolf, if you aren't there to stop it, will eat the goat. The goat, if you aren't there to stop it, will eat the cabbage.
How do you get the wolf, the goat, and the cabbage across without losing anything?
If you bring the cabbage on your first trip, the wolf will eat the goat while you're on the river. It works the same way if you bring the wolf first. So really, the first move you have to make is to bring the goat across the river and come back. Here there seems to be an impasse. If you bring the wolf across next, while you're retrieving the cabbage, the wolf will eat the goat. If you bring the cabbage across next, the goat will eat it while you're coming back for the wolf.
Think about things for a little and try to solve this one yourself. The key to this riddle is that there is an assumption you probably don't know that you've made. Stop reading for a moment and puzzle it out. If you're so motivated, you could tear up pieces of paper and act it out on a desk.
In many ways writing code for computers is like solving this riddle: you have to lay your thoughts on a suitably large surface and pick at them—consider how you unconsciously solve everyday problems. You search through your bedroom for your lost keys, pick apart cracks and narrow spaces, check your pants pockets, and shine a flashlight under the bed, until you realize that you hadn't looked on the dining room table as thoroughly as you had thought. You realize that the solution is more elegant than your previous time mucking around in dark places. The solution to this riddle, lying on the dining room table, rests in the fact that you can carry things across the river in both directions. After you carry the goat across, you come back and carry the cabbage across and then bring the goat back with you on your return trip, leaving the cabbage on the opposite shore. You bring the wolf onto the boat and leave it with the cabbage on the other side. Finally, you bring the goat across.
The real, hardcore way to attack this problem is to think in the abstract, in a fill-in-the-blanks kind of way. The boat that goes from the starting point to the destination can hold a certain number of things. The exact number doesn't matter. There is a list of items at the starting point; each may or may not have a desire to eat or, more abstractly, destroy another item. The cabbage, for example, doesn't eat anything, but the wolf wants to destroy the goat. You could write out a vague solution that would go something like this:
- Decide if the situation on the shore you're currently standing upon would lead to something getting eaten if you left.
- If something is in danger of getting eaten, place things into the boat to fix the situation and go to step four.
- Otherwise, if everything is fine:
- If you're standing at the destination point, leave the boat empty.
- If you're standing at the starting point, choose items (up to the capacity of the boat) to bring across in an unspecified intelligent manner.
- Cross the river.
- Unload the boat and see if all things are at their destination.
- If so, the riddle is solved. You stop working.
- If not, go to step one.
By writing a description like this, called an algorithm, you've not only solved the wolf, goat, cabbage, one-thing-at-a-time problem, you can also solve the computer geek, doughnut, creepy stalker, pizza, pretty girl, policeman, two-things-at-a-time problem. You could even solve a riddle involving thousands of items, something that would be too big too hold in a human head. In writing an algorithm and grasping the deep nature of the puzzle, we coders conquer whole classes of riddles.
That's what the real purpose of computers is: not only to solve problems that would take real people too long to be interesting, but to capture our thoughts and make them into diamonds. When I come up with an algorithm, when I come up with a solution to a class of riddles, I'm coalescing a lot of hazy thoughts in my head into a precise poem. The computer languages that people express their algorithms in are a compressed kind of English that reflects this. The steps above would look like this in C, one of the most popular languages. This is going to be a little like reading Middle English: the words will look familiar, but they won't be completely graspable. An important thing to keep in mind is that in C, a semicolon—not a period, exclamation point, or question mark—always ends a sentence. Be brave.
do
{
if ( somethingInDanger() )
while ( somethingInDanger() )
placeInBoat( chooseEndangeredThing());
else
if (thisShore == startShore)
while (boatLoad<= boatCapacity)
placeInBoat( chooseThingIntelligently() );
crossRiver();
unloadBoat();
}
until ( riddleSolved() );
It's easy to get lost in all of the parentheses and curly braces, but they're just the equivalent of the poles that hold up a tent. They don't do anything by themselves and aren't especially meaningful, but the tent would fall apart without them. Remember, this is exactly the same thing as the steps in English.
Skip over the word do in the beginning—it just a necessary part to set up the last steps that I'll explain in a little. The line if ( somethingInDanger() ) is the equivalent of step two. somethingInDanger() is a way to call on a function named somethingInDanger. A function is just a bundle of steps that has a name. Coders usually divide up steps into little packages so that it's easier to understand what's going on. somethingInDanger, for example, does the work of deciding whether an object is in danger of being eaten. I left out the actual definition of somethingInDanger because it's boring to look at. The word if has a pretty straightforward meaning: in English, "If whatever is in the parentheses is true, then do this next step."
The next line, while ( somethingInDanger() ), works the same way. The word while means, "While whatever is in the parentheses is true, keep doing this next step." The line after that is the equivalent of step two. Rephrased, it says, "While there are things in danger, place those things in the boat."
The line placeInBoat ( chooseEndangeredThing() ) is a call to the function placeInBoat, but it's different in that it has chooseEndangeredThing() between its parentheses. chooseEndangeredThing is a function, too, but it's acting as a parameter. A parameter is a silly word for something that a set of steps will work on—it's a way for functions to speak to each other. chooseEndangeredThing finds a thing that's in danger, and placeInBoat places that thing in the boat. Parentheses enclose parameters but not in the same way they enclose things that follow the words if and while. The things after if and while are called conditions—things that are either true or false.
In the next line, just plain else, works with the if on line three. It says, "If that condition in the if statement wasn't true, do this instead." It's the first half of step three. Notice how the if and else line up horizontally. That's intentional because, without these kind of cues, things get confused really quickly.
The if statement after that takes care of part A—there's no else to this if, so does nothing. The while statement after that is the equivalent of part B. boatLoad <= boatCapacity is a compressed form of the sentence, "The stuff in the boat is less than or equal to the capacity of the boat."
placeInBoat ( chooseThingIntelligently() ) works just like it does with placeInBoat (chooseEndangeredThing() ), only this time we're choosing things in that unspecified intelligent manner stated in part B. The similar naming is also intentional, because it helps people see that the two functions have similar uses.
crossRiver() and unloadBoat() are steps four and five. I took care of steps six and seven by fitting them around all of the other steps. The curly brackets enclose a set of steps and make them act like one big step—a set of steps enclosed in curly brackets is sort of a function without a name—and the do until statement says, "Do this big step until riddleSolved() is true."
Once you pierce the veil of parentheses and curly braces and semicolons, it's pretty simple in there. All a computer language is is a bridge between the real world, where we speak English and use ten fingers to count, and the world of computers, which speaks words like F043A0 and uses 16 light switches to count.
But these details are ultimately unimportant. They're just the incarnation of thought, a machinery that's no more interesting in itself than a grandfather clock. There are certainly a few people who find the insides of grandfather clocks interesting, but most people are more interested in their end result: cuckoos chirping and wooden ballerinas dancing. There are some people who are involved in designing clocks to do interesting things, but the actual cogs and wheels aren't interesting in themselves when they're sitting in a chest or a drawer. They're tent poles. They just get things done.
There's one problem with the solution to the easy riddle, though. What if this algorithm is given an unsolvable set of circumstances? What if we added a flesh-eating bacterium that would destroy both goat and wolf? The riddle would be unsolvable, because any way you tried it, you'd end up leaving the bacterium with the goat or the wolf at some point.
Here is the second riddle: Which riddles are solvable and which are unsolvable?
This is the hard riddle. Remember, our goal is to be as abstract as possible, so I'm not talking about just the wolf, goat, and cabbage riddle. I'm also talking about "Why is a raven like a writing desk?" and "How can the U.S. get rid of its budget deficit?" and "How do you get from here to the moon using only a spoon?" There are a few simple, good answers to the first riddle, a few complicated, good answers to the second one, and none at all for the third. (It would be neat if there was a solution, though.)
If you sat down and thought about it for a while, you could work out a way to decide whether a certain variation on the wolf, goat, cabbage riddle was solvable or not. It's a lot more complicated to figure out whether a problem is solvable than to solve it in the first place, which is a little strange, if you think about it. But what about all of those other kinds of riddles?
Imagine this hard riddle as a machine with a little slot to stick descriptions of riddles into, a green light that lights up for solvable riddles, and a red light that lights up for unsolvable riddles. The inside of the machine would be the algorithm; whatever steps it would take to decide whether a riddle was solvable or not.
Now imagine giving this machine the hard riddle itself.
If this machine does work, if this hard riddle can be solved, then the green light should light up. Think about this. If a machine could figure out whether it works correctly or not, then why do computer programs crash and lose important things? Couldn't a computer program be written that would be able to figure out if the person who created it had made a mistake?
The answer is no. The second, hard riddle has no solution. It is possible to tell, in some cases, whether a riddle is solvable or not. But in the most abstract sense—and remember, it's the abstract that's really important—there is no way to distinguish between all unsolvable riddles and all solvable riddles. The reason is that the best way to decide whether a riddle is solvable or not is by simply trying to solve it. If it is solvable, then the program would end and the green light would come on. But if it were unsolvable, the program would churn forever, never giving an answer. You can't assume that just because a light doesn't come on that the riddle is unsolvable because there are riddles that take a very long time to solve but still have solutions. Algebraic equations with three or more variables can take computers insane amounts of time to solve. And there aren't any other ways to attack this problem that aren't rephrasing this decide-whether-it's-solvable-by-solving program.
This implies that not every problem can be solved with a set of predetermined steps and that there are some things that computers can't do. This also means that coders, when they sit down to solve problems, know that there are certain things that can't be done—not because we're not smart enough, but because they're intrinsically impossible with a computer.
Computer science is one of the few scientific disciplines that acknowledges that it's not going to be able to figure out everything. Biologists or physicists don't know everything about how things work in the world, but there's a sense that if they keep working on it, they can crack open the universe's oyster shell. Perhaps they really can figure everything out, but I like working in a field that knows its own limitations. Even though people have had evil dreams about computers taking over the world, we coders know that what we're working with is only a limited shadow of our own selves.
Computers can do useful things. They can do surprising and beautiful things. But only because the people who program them can think usefully, surprisingly, and beautifully.