Speaking the same language

How to think programmatically

Theseus and the Minotaur in Daedalus’ Labyrinth

Our heroes from last time got off easy — there were no monsters in their mazes! Real heroes must fight monsters on their quests, so let us update the maze accordingly:

blue=hero
red=monster

As before, the blue square represents our daring hero seeking fame and glory. This time, however, the journey is plagued with two monsters, each labeled with a red square. Luckily for us, the hero has utilized their spy network to obtain a very useful piece of intel: the tall monster is invincible, while the small one can be slain. Let us update the vocabulary so that our hero has a fighting chance:

• walk x steps: the hero walks forward x steps (each step is a square in the grid), stopping at the first wall or monster they hit
• turn left: the hero turns 90 degrees left
• turn right: the hero turns 90 degrees right
• tall monster ahead: yes if there is a tall monster just in front of the hero; otherwise no
• small monster ahead: yes if there is a small monster just in front of the hero; otherwise no
• slay: the hero destroys the monster in front of them, completing the quest
• if x then y: if the situation matches x then the hero does y; otherwise they do nothing (hint: replace x with tall monster ahead or short monster ahead and y with something you want the hero to do in response)

The hero’s goal is to slay the vincible monster and avoid the invincible one. Plan out a path for the hero, but be careful! If the hero walks into a monster, the monster will devour them. If the hero encounters the tall monster, run the other way; if they encounter the small one, slay it. Assume the hero always starts facing up (↑). If you’re having trouble planning the route, try writing down what each color means and physically tracing the route — just because we’re learning about computers doesn’t mean you can’t use pen and paper. When you’re finished with your plan, check it with this one:

1. walk 3 steps
2. turn right
3. walk 3 steps
4. if small monster ahead then slay
5. turn left
6. turn left
7. walk 2 steps
8. turn left
9. walk 5 steps
10. turn left
11. walk 2 steps
12. slay

Of course, my plan isn’t the only way to do it. If your plan differs, that may be completely fine. And if you couldn’t make a plan, that’s also fine — you’re here to learn not to be tested! The only thing I ask is to make sure you fully understand Step 4. In Steps 1-3, the hero approaches the monster towards the top of the maze. When they’re standing toe to toe with the monster, they must ensure that it can be slain. Since only the short monster can be slain, the slay instruction should not be used unless the hero confronts the small one. That’s where if x then y comes in: the hero performs whatever instruction replaces y if and only if the situation matches x. So Step 4 says that if there is a small monster ahead then slay it. If the monster is tall or there isn’t any monster ahead at all, then slay is ignored and the hero moves to Step 5. Remember that since slay completes the quest, if the hero slays the small monster the rest of the steps (5-12) are ignored.

I hope the rest of my steps look reasonable to you. If in doubt, physically trace the maze with your finger as you follow the steps. When you’re ready, read on.

I want to show you a more complicated maze. It will take real ingenuity to complete this quest but I think at this point you’re up to the task. In order to complete it, we’ll need to add three instructions:

• jump: the hero jumps over the square in front of them; useful for avoiding deadly lava pits
• boss monster ahead: yes if the boss monster is just in front of the hero; otherwise no
• x while y: the hero performs x over and over as long as the situation matches y

Yes, lava and boss monsters. Why not include all the clichés, right? The boss is special in that it can withstand many hits before getting slain. The hero will have to slay the boss many times before it actually works. Unfortunately, the hero does not know how many times; he must find that out through experience. This is where the third instruction, x while y, comes in handy. Without further ado, here is the (for now) final maze:

blue=hero
green=treasure
orange=lava
red=monster
black=boss

Since this maze is larger and more complex, let’s break it down into parts. First, devise a plan to get to the boss, represented by the black square. You don’t necessarily have to fight him, but if you examine the maze you’ll see there’s no way around at least passing him one square above. Note that walking into lava kills the hero and they can jump over only one square; two lava squares in a row cannot be jumped over. To make things a bit easier, let’s assume this hero is more powerful than the last one and can slay any monster in their path, tall or small.

Here’s my plan:

1. turn right
2. walk 1 steps [yes, steps; the hero doesn’t understand step!]
3. jump
4. jump
5. turn right
6. walk 1 steps
7. turn left
8. walk 2 steps [the hero is now out of the lava room]
9. turn left
10. walk 4 steps
11. turn right
12. walk 2 steps
13. turn right [the hero is now facing the first monster]
14. slay
15. walk 2 steps
16. slay
17. walk 2 steps

I hope that’s not too many steps to follow. I’ve annotated a few key points but if you’re not used to this kind of thinking, 17 steps just to jump over some lava and slay a few monsters may seem excessive. The goal, however, is not to make the hero’s abilities conform to your idea of what’s reasonable (not yet, at least). Instead, try to adjust your idea of what’s reasonable to the hero’s abilities. This idea harks back to the title of this post, Speaking the same language. Successful computer scientists must be able to think and plan in the language of computers as well as of humans. Acquiring this skill takes time and practice and I don’t think there’s any silver bullet or special mnemonic that lets you skip all of the hard work.

That being said, some learning methods are more effective than others. I want to introduce programmatic concepts without subjecting you to lots of messy syntax, a term that basically means a language’s grammar. It’s important to understand the concepts and methods behind a programming language before delving into its syntactic details like whether a certain instruction should end in a semicolon or not. In other words, consider the hero’s vocabulary a very easy to read but primitive programming language.

With that in mind, let’s finish the maze. The hero has a choice to make: defeat the boss in combat or sneak around it. I’ll let you decide which option makes more sense. For convenience, the maze is reprinted below.

Graphics were never my specialty

What choice did you make? Either one works, of course, but one is definitely more concise. By taking advantage of the while instruction, the hero can defeat the boss in combat and get to the treasure quite quickly (assume the hero is where we left them):

1. slay while boss monster ahead
2. walk 2 steps
3. turn right
4. walk 9 steps

The first step is really composed of many steps. The hero performs slay over and over as long as boss monster ahead. When slay finally finishes the boss, the situation no longer matches boss monster ahead and the hero stops slaying and moves to Step 2.

I won’t explicitly lay out the steps for going around the boss but they involve lots of turning, jumping, and either slaying or avoiding the monsters. Slaying the boss directly is a much shorter sequence of steps. This principle comes up all over computer science; using more complex instructions like while can shorten the number of steps required to complete a task. But please note that using while may not make the job of the hero any easier — perhaps the hero had to slay 100 times to defeat the boss. In that case, walking around may have taken fewer actions than 100 sword swings (from the hero’s perspective).

Generally, you’ll want to push as much work on the hero as possible and minimize your own workload. A lot of computer science focuses on creating short, concise lists of instructions that perform thousands of actions in just a few lines. However, you should also be aware of the hero’s stamina, i.e. how long it takes the computer to accomplish your instructions. Instructions that take mere seconds to write can take a computer many hours to complete. We’ll delve more deeply into this discussion later. For now, just be aware of the complex relationship between the number of written instructions and the number of steps computers must take to complete them.

I would also like to congratulate you and your hero. The treasure in the last maze was a giant chest full of cash, coins, and gems. Your hero will be rich and famous, which everyone knows are the only important goals in life!

Image credit: Theseus