From Z to A: Reversing arrays (Part 1 of 4)
While loops and variables
This is an ongoing series. Please check out the collection for the rest of the articles.
I want to talk more about arrays but my plan will take a lot of background to complete. Accordingly, I’m starting a four-part miniseries on them; this first part is all buildup and although it’s substantial enough to warrant its own post, it doesn’t have a nice conclusion so I’m placing the punchline in the second part of the series. In the third and fourth parts, I’ll demonstrate alternative ways to solve the problem.
I covered how to search arrays in an earlier post and in this series I’ll explain how to reverse them. Reversing an array is a beautifully simple operation and will help introduce you to the kind of algorithmic thinking aspiring computer scientists must adopt. Put simply, reversing an array makes the first element the last element, the second element the second-to-last element, and so on. For instance,
becomes
Understanding how to reverse an array is also very useful from a practical perspective. Think of the situations in which programmers must reverse arrays of things:
- In spreadsheets, databases, and other tabular systems, users frequently want to reverse columns of data; maybe the data were initially alphabetized and now they must be reverse alphabetized; maybe you first wanted the biggest numbers at the top and now want the smallest at the top.
- You’re designing a flashcard application and you discover that if the cards are displayed in the same order each time, the users get too familiar with the order and start to depend upon it to memorize the cards; you need to be able to reverse the order of the cards (or sort them randomly, but we’re not there yet).
- Imagine you’re writing an application that tells you whether or not the words you give it are palindromes (words that are the same forwards and backwards; for instance, pop, racecar, and kayak are all palindromes). How can you test if a word is a palindrome or not? Reverse the word and compare it to the original — if the original and the reversed word are the same, it’s a palindrome.
There are many, many more examples when reversing arrays (or words, which are usually called strings and are just arrays of characters) is useful and even essential. Some social proof of this fact is that most programming languages provide built-in instructions for reversing arrays, lists, words, and many other types of data. Basically, the concept is fundamental and essential.
But enough introduction! Now I’ll actually explain how to reverse an array. Except, as usual, we must learn some more rudimentary ideas first. The big one this post is the concept of a while loop. While loops enable you to repeat a set of instructions over and over until some condition is no longer met. We use this kind of structure every day in English: “while it is raining, wear a raincoat” and “while they are napping, keep your voice down” are some basic examples. As long as some condition holds, keep doing something.
Here’s the while loop instruction in Cake:
- while (x) do (y): while x remains true, compute y
It seems simple enough on the surface but there’s one problem: if the condition that keeps the while loop performing the action returns true, how could it later return false? As in, if some instruction returns true then shouldn’t it always return true? If some instruction returns 4, then shouldn’t it always return 4? How could 2 + 2 return 4 one time and 5 another? Yet if a while loop is ever going to end, its condition must return false at some point.
We both know that 2 + 2 always returns 4, even in Cake. There’s no spooky magic that surreptitiously changes answers when you’re not looking. Rather, the way that an instruction can return one value one time and another value another time is through state. No, not a state like New York or California, a state like a configuration; like the State of the Union address. A state, in this sense of the word, is the configuration or layout of a system.
A light switch is a great example of a simple system. There are two states in a standard light switch: off and on. Flicking the switch up changes the system to the on state and flicking the switch down changes the system to the off state. If the switch transitions to the on state then the connected light turns on. If the switch transitions to the off state then the connected light turns off. If this sounds blindingly obvious, it’s because it is; I want to gently acclimate you to the idea of a system with states. While we will encounter systems with much more complicated states, the principle is the same: there are a certain number of states and methods of transitioning from one state to another.
When a programming language (like Cake) runs instructions, it acts as a system with state. This system is called the run-time system or run-time environment. In this context, “system” and “environment” mean basically the same thing. The term “run-time” comes from the fact that this system exists when the code is running. No, not like jogging; like a car running as opposed to being turned off or broken. Unlike a light switch, however, a run-time system can change what states it has on the fly. Instead of just off and on, a run-time system may have gone through tens, thousands, or even millions of states by the time the code is finished. Basically, it can get as complicated as you want (but please don’t think that “complicated” equals “advanced” or “sophisticated” — your system should usually be as simple as possible given the task at hand).
The Cake instructions we’ve explored so far don’t have the ability to change the state of the system. The state was implicitly setup at the beginning and left unchanged. What exactly constitutes state in Cake, you might ask? A major component is all of the instructions. Every time I’ve introduced a new instruction, Cake has implicitly added it to the run-time system when it runs code. As of this post, Cake has many instructions (+, -, *, /, and, or, etc.) that are added to the system every time we (pretend to) run a Cake program. Since Cake isn’t an actual language — we’ve just talked about it, we haven’t physically programmed a language — all of these instructions are added to the system in our heads. When I write down Cake code, I’m assuming that all of the instructions I’ve defined before have been added to the system.
Real languages work the same way, except they’re real. Whenever a programmer runs some code in the language, the run-time system adds all of the default, built-in instructions before any of the programmer’s code gets computed. So operations like addition, subtraction, etc. are always available. If you didn’t add these instructions, the language wouldn’t recognize anything the programmer wrote. Sometimes certain values are added by default as well — π is often added and most languages include true and false. These are all part of the initial state.
At this point state may sound like an overly technical definition of “the default stuff” but I assure you it’s more than that. Why? Because, as I explained before, you can change the state. Usually, the default instructions and values aren’t changed during run-time. Instead, more instructions and values are added. Adding a value changes the state of the system. Instead of the only possible values being, for instance, true and false, you can add your own. Let’s say you add the value elephants and give it the value 7. Why? I don’t know — it’s your program. But now, when Cake sees elephants, it replaces it with 7.
elephants can represent whatever you want. Perhaps your program is keeping track of how many elephants are in various photos, and you’re indicating that the current photo has 7 elephants. elephants doesn’t have to refer to elephant related things, though — Cake is a simple program and thus has no idea what an elephant is and doesn’t care in the least. You could use elephants to keep track of how many cats are in a photo or how many items are in an array. Please don’t — confusing and irrelevant variable names are the bane of every programmer — but the point is that the names matter only to the humans reading the code, not the computer reading it. Whether elephants refers to the number of elephants or giraffes, its value is 7 and that’s all Cake knows; you’re the one who attaches meaning to the name.
elephants is an example of what’s called a variable. Why “variable”? Because a variable’s value can vary (as in, change). This goes back to the idea of state. Variables keep track of the state of the system. When a variable’s value changes, the system has changed states. In other words, the state of a system is all of the variables and instructions currently added. This is why a run-time system can change states so many times: changing a variable’s value changes the state, and most programs have lots of variables that change values lots of times.
Here is how to add a variable to Cake:
- let x = y: make a variable named x and give it the value y
So let cats = 4 adds a variable named “cats” and gives it the value 4. The term “let” comes from the mathematics community and is usually used to declare new variables. Note that variables, like instructions, can’t have spaces in their names. If you want to add a variable with a more descriptive name (and descriptive names are great), you can use underscores (e.g. number_of_cats) or capitalize the first letter of each word except the first (e.g. numberOfCats). Having said this, for now don’t worry too much about details like naming conventions; focus on understanding what “state” means and how to change it.
If you want to change a variable’s value, use this instruction:
- set x = y: give the variable named x the value y
If the variable doesn’t exist yet, use let. If it already exists, use set. Here is an example of variables:
Here, num_apples stands for number of apples. The same logic goes for num_oranges and num_fruits. As you can see, at first there are 2 apples and 4 oranges. Then the number of apples changes to 3. Since there is no other fruit, the total amount of fruit is the number of apples plus the number or oranges — that is, 3 + 4, which is 7. So at the end of computing this code, num_fruits has a value of 7. Incidentally, we’ve just demonstrated that you can, in fact, add apples and oranges.
Now that we have a notion of what state is and how to use it, we can solve the paradox of the while condition; include a variable in the condition so that when the time comes, the variable can be changed so that the condition return false. When the condition returns false, the loop ends and the code moves on. Let me show you what I mean:
The variable counter is initially set to 0. Then the while loop checks if counter < 10, which is true, and consequently computes the code following do:
So after the first iteration of the while loop, counter is set to 1 and the condition is checked again; 1 < 10 so the code following do is computed again. As you can probably see, this pattern repeats until counter is increased to 10. Then, when the condition is checked, it returns false (since 10 < 10 is false). At this point, Cake jumps out of the loop — as in, it doesn’t compute the code following do — and moves on to whatever code is after the loop (represented with “…” in the example above). The key to understanding while loops is to remember that the condition you specify is checked every iteration. Make sure you include a variable in this condition or you may find your code in an infinite loop!
Image credit: light switch, elephants, Cézanne’s Apples and Oranges, ouroboros
