C++ Programming As A Set Of Problems/Chapter1
Introduction - Solving The Tower of Hanoi
[edit | edit source]
The Tower of Hanoi is a fairly simple puzzle. It consists primarily of three poles and a set of rings. The rings are in different sizes, stacked from largest to smallest on the first pole. Your objective: to move all the rings to the second or third tower. Sounds simple? Rules: You can only move the top ring on a given tower, and you can't place larger rings on top of smaller rings. If you already know how to get a solution, you can skip the next part.
Let's start off with a simple version of Hanoi, it is from this version that we will base larger versions. Let's start with two ring Hanoi. I'm sure it shouldn't be a challenge for you to move two rings to the target location. We will call these rings #1 and #2. #1 is stacked on #2 on the first pole. We want to get both #1 and #2 to the second pole; so eventually, we will have to move #2 to the second pole. #2 is the bottom ring, so it can't be placed on top of anything else; the second pole has to be clear. So, from this, we formulate a solution. We move the #1 ring onto the alternate pole, then we move #2 on to the target pole, then move #1 back onto the target pole.
Now, let's move onto a larger example. How about 4 ring Hanoi. We will try to use some of the knowledge present in the previous example. First, we have to move the #4 ring onto the second pole at some time in the solution, and for that to happen, the second pole has to be empty. For #4 to be movable there can be nothing on top of it, so we have to stack #1, #2, and #3 on the alternate pole first. Now we can move #4 to the target pole and reassemble the tower on top of it.
The solution has gotten slightly more complex. We can't simply pick up #1, #2, and #3. We have to move them according to the same rules. So we apply the same pattern, #3 has to be moved to the alternate pole, and that pole has to be clear of rings with lower numbers than #3, meaning no #2's, or #1's. So, the alternate pole becomes our target pole, only we're moving less rings. See the pattern? Its called a recursive pattern. So, let's define a basic rule: To move n rings from pole a to pole b, using c as an alternate, first we move n-1 rings to pole c using the same rule, then we move the ring n to pole b, then we move n-1 rings back from pole c to pole b. Note that when n=0 we should do absolutely nothing. Now, let's turn this into a program.
Proudly, Your First Program
[edit | edit source]Open up your favorite text editor with a new file called "hanoi.cpp". This file will contain our source code.
First of all, we told ourselves that there is a recursive pattern. This pattern seemed to take four variables, n, a, b, c. We should give these slightly better names, perhaps, depth, from, to, and alternate. So, let's make a function. A function, as in math, is just a list of instructions for the computer to follow. It has a name, unlike in math where everything is named "f" or "x", which makes little to no sense. We will name our function "hanoi". Type or copy/paste into your text program the following:
void hanoi(int depth, int from, int to, int alternate)
{
}
Let's dissect this for a moment. The first part of the line is "void". What does this mean? Well, in reality, the first part of the line is the return type. This is what the function will return, which is what it will evaluate to, what its result is. A type just means a type of data, like a number, a letter, a string (which is a bunch of letters that make up sentences and stuff), or even our own data type (we will explore this later). The void type means nothing, literally, so this function doesn't have a result, it does some other thing, like output its result to us, instead of returning it. The second part of line is "hanoi", which, as you may have guessed, is the name of the function.
Then a pair of parentheses, "(" and ")", and within them is a set of arguments. You may have also guessed that these arguments are what we named earlier: depth, from, to, and alternate. They are separated by commas, which is logical. However, what is the int part, you may be wondering? Remember I said earlier that all data has a type. The int is a type that your compiler knows, it stands for integer. So, our four variables are integers, in that they represent negative or positive numbers. The depth is a number that represents the number of rings the system should be moving. The from, to, and alternate are all integers that specify what pole we are working with. Indeed, these could also be done with strings, which would allow the output to be more like "Move ring #3 from tower a to tower b", instead of "Move ring #3 from tower 1 to tower 2". We can, and will, do this later.
The next lines consist entirely of an opening bracket "{", and a closing bracket, "}". These two brackets show what is in the function, what the function does.
Now, we are going to start making up the function. Remember our rule? Part of it said that we should do nothing if n, or depth, is 0. So, let's do that first. Make a new line in between the brackets, and we will add in an if statement. An if statement consists of a few parts, mainly, it follows the following pattern:
if(something)
{ ..do something.. }
You can note that the "..do something.." is only done if the "something" is true. In our case, the something is "depth is 0", and the do something would be to do nothing, as confusing as that sounds. Our code, then, is:
if(depth == 0)
{
return;
}
I can hear the screams already! You shout "Wait, that doesn't match the pattern! It's supposed to be on one line, not three!". Let me explain. You're allowed to put spaces and new lines anywhere, absolutely anywhere in the code, except in dumb places like between the "i" and the "f" in the "if", or inside the "depth". But in most other places, it's perfectly OK. So you might be asking, "Why bother?". There are notable benefits to spacing things out. It makes code more readable. You will find that as you get more experienced that more than two-thirds of your time is spent reading code you wrote at some other point in time, rather than writing code right there and then. You will spend lots of time finding mistakes, or computer bugs, in your code. So, it becomes essential that your code be easy to read.
All this being said, we should discuss the code. First of all, our "something" in the if statement is "depth == 0". You might be wondering why there are two equals signs instead of one. This is because using only one equals sign would change depth, "depth = 0" causes depth to become 0, and we lose whatever used to be the value of depth. Two equals signs denotes comparison, we are comparing depth to 0, and if it is true, we are going to execute the return statement, otherwise, we skip past everything contained in the curly brackets. The return statement causes the function to return immediately, meaning there is nothing more to be done in this function, so no more code is executed in that function. This is exactly what we want: if the depth is 0, then do no more, just go back up a level. Also note that the return statement has a semicolon (;) at the end, yet the if statement does not. This is extremely important to remember: all statements, except for ones that use curly brackets, must end in a semicolon.
So, on to the next part. First things first, we move all of the rings above the nth ring to the alternate. So, basically, the function is calling itself to do this. Add in the following code:
hanoi(depth-1, from, alternate, to);
You can see that we are calling the hanoi function again. Except, we've now swapped the alternate and the to, to represent the fact that we want to move all the above rings to the alternate pole, rather than onto the pole we are trying to move the bottom ring to. This is simple enough.
On to the next part. We have to move the nth ring from the from to the to. Let's decide how we're going to do this. We are not literally doing it in code—there is no Pole data and we are not moving Ring data between poles, we are simply issuing the command so that a human reader who had the three poles in front of him could do it himself. We will get into more advanced forms later. For now, add in the following code:
std::cout << "Move ring " << depth << " from pole " << from << " to pole " << to << "." << std::endl;
This is the code that will output our information. Let's dissect it. First, it starts with "std::cout". The "std::" part specifies that we are using something in the standard library. The standard library includes lots of useful things, and it comes with every implementation of C++. The "cout" part means we are using cout from the standard library, which stands for "Character-OUTput". The next part is "<<". This is called the format operator. It sends what's on the right into what's on the left. This operator is used almost exclusively for "std::cout", although, if you really wanted to, you could use it for your own purposes. The next part is "Move ring ". This simply means we're sending the text "Move ring " into std::cout, which will, in turn, come out for us to see.
Then you see another "<<", so we are sending more into std::cout, except this time, we're not sending in text that is to be replicated exactly, we are sending in depth, which means whatever the value of depth is, be it 17, 42, or 15843, it will be output that number. The next part is another piece of text. Again, notice that there is a space at the beginning. This is because when the program is outputting the 'depth', it doesn't add in spaces at the beginning and end, as that may not be what you want. So, you have to add in the spaces manually. The rest of the line may be easily deciphered; we are just outputting more information. The last part, however, is std::endl. Another thing from the standard library. "endl" stands for "end-line", it causes the line to end, and all the previous output to be sent to the screen.
Let's go onto the next part of our pattern. Now we have to move all the rings, which would now be on the alternate pole, back onto the target pole. For that, we use a similar command to what we used the first time:
hanoi(depth-1, alternate, to, from);
We've swapped things around again. We are moving from the alternate pole to the target pole (named "to"), and we use the from pole as a new alternate pole. Lost in confusion? I hope not. Now that that is over with, the rings should all be on the right poles, so that is the end of our function. The completed function looks like this:
void hanoi(int depth, int from, int to, int alternate)
{
if(depth == 0)
{
return;
}
hanoi(depth-1, from, alternate, to);
std::cout << "Move ring " << depth << " from pole " << from << " to pole " << to << "." << std::endl;
hanoi(depth-1, alternate, to, from);
}
You can take notes on how I space things, as it's probably not how you did it in your text editor. You can see that for every "{" bracket, I indent things by four spaces. Again, this is a style choice, but it's commonly agreed upon that four spaces makes code look neat and tidy, while still allowing lots of code to fit on-screen at once.
The terror is not over yet! All we have is a function. We haven't told the computer what we want done with the function. We also forgot to include some header files, but we'll get more on that later. For now, let's add in the following code:
int main(int argc, char** argv)
{
hanoi(4, 1, 2, 3);
return 0;
}
We made a new function, main, and it returns an integer. The main function is special, it specifies the entry point to your program. It takes two arguments. The first one we can figure out easily—it's another integer. The second one is slightly more confusing. "What is with the char** thing?" Well, a "char" stands for character. But the two stars changes this somehow. I can't entirely explain what this does at this point, it's fairly complex. For now, just be certain that it stands for the arguments passed into the function on the command line.
Let's jump into the body of the function. It seems to execute our hanoi function, it provides a depth of 4, and it wants you to move rings from tower 1 to tower 2, using tower 3 as an alternate. Then we see that return statement again, except this time, we are returning nothing (as we did in our hanoi function, which returned void, which is basically nothing). This time we are returning a 0, which is compatible with the int return type. That is the end of our main function. It seems pretty simple, heh?
We are missing just one last thing to make the program complete. Remember how we used std::cout? Well, the compiler doesn't just assume std::cout exists, you have to ask for it. To do this, you "include the header file". This is done by adding the following to the very top of the file:
#include <iostream>
This copies and pastes the iostream header file into your file at compile time, rather than you doing it manually (which is both error prone and time consuming, and, if the iostream header file were to change, you'd have to repeat the whole process over again). You will have to memorize this one fact, std::cout is contained in the iostream header file. If you want to use std::cout, you have to #include the iostream header file.
Here is the entire program. Note that the compiler may care about the order, so 'main' should be placed after the 'hanoi()' function definition.
#include <iostream>
void hanoi(int depth, int from, int to, int alternate)
{
if(depth == 0)
{
return;
}
hanoi(depth-1, from, alternate, to);
std::cout << "Move ring " << depth << " from pole " << from << " to pole " << to << "." << std::endl;
hanoi(depth-1, alternate, to, from);
}
int main(int argc, char** argv)
{
hanoi(4, 1, 2, 3);
return 0;
}
We now have a complete program! Your first! Congratulations! I think it's about time we test it out, don't you think? At this time, pull up a console, go into the directory where hanoi.cpp is located, and type in "g++ hanoi.cpp -o hanoi". Wait about 2 seconds, and you have your program. You can execute it by doing "./hanoi". Amazing, isn't it? It's giving you the commands for 4 ring Hanoi. I think you should give yourself a pat on the back, and move onto the next section when you're ready.
Extending, What More Could A Man/Woman Want?
[edit | edit source]So, we have a Hanoi program. It tells us how to solve Hanoi. Big deal. This won't impress an interviewer at Google who's qualifying you for "Head Of Development." Our program needs to become a little more involved. Heres a list of things we want the program to do:
- Allow us to choose the number of rings when we start the program
- Show us the actual towers of Hanoi, and where the rings are placed.
- Update the image, on the console, in real time as the computer finds the solution
- Not to go too fast, as we would like to see the solution, rather than have it blaze by us in the blink of an eye.