Let's explore a classical problem in computer science called the Towers of Hanoi problem. The goal of this problem is to transfer all of the cubes from the leftmost stack to the rightmost stack in such a way that no larger cube can sit on top of a smaller cube. For example, we might start moving the smallest cube on top and moving it over one stack. Made one step in the Tower of Hanoi problem and we've gotten maybe slightly close to removing this entire stack from the source here to the destination. Next thing we might want to do is to go ahead and take this purple cube and move it all the way to a destination. The idea here being that we can't put it on top of this yellow cube because that would put a larger cube on top of a smaller cube. Something that's against the rules of this game. After removing the purple cube, then we have only two options now. We can't move the orange cube on top of anything because the orange cube is too large. Instead, our options are really to move the yellow cube on top of the purple cube or the yellow cube on top of the orange cube. Here, I went ahead and move the yellow cube on top of the purple cube, which leaves a space to move the orange cube down on top of the empty stack. We can continue this process of juggling these cubes all around with the goal being that we want to slowly move the largest cubes to the right. Notice that here I've stacked up all three of the cubes except for the largest cube in the middle, and now I can go ahead and move the largest cube from where it began to where we eventually want to indent. This process continues, but we want to talk about how we can represent this problem programmatically with code. So, what I see here is I see three distinct classes or three distinct things that we want to represent. The first thing I see is we have these cubes. So, we already have a class to represent our cubes. So, we're going to use our UIUC cube class to represent a cube. But I see these cubes don't just have a length, they also have a color. So, I'm gonna go ahead and use a color to represent the cube in addition to its length. So, we want to modify the cube class, and we'll do that in just a minute. The second thing I see, as I see three individual stacks. I see this as this maybe stack at index zero, a stack at index one and a stack at index two. So, what we have is we have a series of individual stacks. All three of these stacks are part of something even larger because we need some container to store the stacks. Here, the entire container might just be called the game. So, inside the game, we have stacks and in each stack we have cubes. That's the relationship we have between the game, the stacks, and the cubes. Let's go ahead and build a program that creates a number of different classes to represent all of these entities. So, in last week's assignment, you built the UIUC HSLAPixel. [This appears in the Week 4 project.] You already know how to represent a color. Let's go ahead and see this cube come together. Here, I've modified the cube constructor to have a length and a color, and because we've modified the cubes construction of a color, we're going to store that color in a new private member variable. So, a cube is different than before in the sense that we now have a cube that has both a length and a color. We have the ability to get a link settling to get the volume and get the surface area. These basic operations have been with our cube the entire time and all we've done is we've added a color to these cubes, so we can better represent how the image works. Next, I want to focus on the stacks. Each stack has a series of cubes on top of it. We don't know how many cubes there are, there may be zero cubes. There may be three cubes. There may be one cube, and who knows, we might expand this game and there may be 10,000 cubes here in this last stack. We don't know. So, because we don't know, an array or a vector in C++ is a great way to represent this. So, every single stack needs to contain a vector of cubes, so that we can push the cubes onto the stack. The other piece we need, in addition to the vector of cubes, is we need operations to interact with the top of the stack. So, notice on every stack, we never care about what's below the top element. We can only move the yellow element. We can't move the yellow and the purple element at the same time. So, the only operation we ever have on the stack is to modify the top element by either looking at it or removing it all together. Here in the stack class, we have four public member functions and one private member variable. We know it's a stack class because we sees class stack here and this is in stack.h file. So, let's look at the four member functions. The first one is to push back. This borrows this terminology we see from the vector and this pushes an element to the last element on our stack, which is the top of our stack. The second element we see is remove top, that returns a cube by value. So it's going to return a copy of a cube that we created earlier, and we're going to peek top as well. So, peek top is only going to return that memory without removing it from our internal data structure. So, we can either remove the entire cube or just look at what cube is on top, and then we have our last public member function, which is the size. So, the size function tells us how large the stack is, it may be zero cubes, two cubes, five cubes, three cubes, whatever. Finally, we have this additional friend function here on line 21 and 22. This function is going to be something that we see quite a bit throughout this course and it's always going to take on this std ostream by reference operator less than, less than, and always have an ostream as the first argument and then a constant reference of its own type as the second argument. So here we see a friend function that is ostream. This friend ostream function allows us to "cout" an object. If you've come from a Java background, this is something like your "to string" function that it allows us to write out the output of an object in a textual way. So, this way we can actually see what's on top of the stack and we're going to have to define exactly what that function does in the CPP file. The last piece that I want to build is, I want to build the functionality for the entire game itself. So, the game itself is going to set up the number of stacks we need. It's going to set up all of the cubes and it's going to keep track of those stacks. It's going to be the container to hold the three stacks. So, we'll have this vector to store the three stacks, which will store as a vector and we're going to have the constructor create the initial setup of the game. So, let's look at the h file. Here on game.h, we see that we're going to use stack.h into our making use of stacks here in our private member variable and we have vector. The game class is pretty simple. We simply have a game constructor, which you're going to set up the initial state of the class and we have a solve function, which is going to solve the game programmatically for us. We have the same ostream friend function, which allows us to print out the game as an object, so we can see out the entire game and get useful information, and then here adds a private member variable, we have a vector of stack objects. The final thing I want to show is we have the game itself. So, this is Game.cpp and specifically I'm looking on line 17 at the constructor. So, the constructor of the Tower Hanoi game is going to build three stacks. So, notice we have stack, stack of cubes, and the stack is going to be added to the back of the stacks array. What's going to happen once this code run is the stacks array is going to have three elements in it and each of those elements is a stack. So, this is our stack at zero, this is our stack at one, this is our stack at two, and these three stacks represent the three stacks you see in the game itself. The last 12 lines of code of this constructor, just to set up our four cubes and pushes the cubes all to stack zero. So, here we have our blue cube that has a length of four, our orange cube that has a length of three, our purple cube with a length of two, our yellow cube that has length of one. So, what we have here is the yellow cube, the purple cube, the orange cube, and the blue cube. These are all placed onto stack at zero. So, all of these cubes are now at the initial starting point. So, when the game is created, the game already has the cubes created. The cubes are on the zero stack and the object of solve is to actually solve the game to make sure that the game moves the cubes that are on stack zero to the very last stack. We haven't seen a main function, so I created a main.cpp that's going to actually run the game. So, the goal here is we're going to here in main.cpp, create a game, game G, and we're going to print out the initial game state. So, on line 14, I do cout and say, initial game state and then on line 15, print out g, the game itself. So, since we defined our friend ostream operator, we're able to print out the game itself and that's going to print out information about the game, which I implemented in the game.cpp file that you can check out. Here on line 17 g.solve. This should solve the game and on line 28 repeat the previous lines except for I'm saying, the final game states, I'm printing out g again. What we expect to see, is we expect that g is going to be solved. Right now, I haven't programmed the solve function. So, we're going to run this program right now and see that this program does create the cubes and it's going to print out the state of the game. After we see that happen, I'm going to challenge you to solve this puzzle yourself, though we'll go over solutions right after this. But let's first see if main runs. Here in the console, I'm going to go into the directory CPP tower and run make to build this program, and then run./main. Here in./main, we see the initial game state, consists of stack zero, stack one, and stack two, and stack zero has the cubes four, three, two, and one on top of it. In my solve function, I have a small amount of output, that just outputs the game itself again, and then here's the final game state: four, three, two, one, inside of our main function again. I mentioned that our solve currently does not do anything. So, the four, three, two, one, is the exact same state we see in the initial game state. If I open up the file, Game.cpp, we're going to find our solve function. Looking here at line 17, we have a solve function. This solve function solves the Tower of Hanoi problem. Here, I'm only outputting the game itself and that was that output that you saw. This here refers to the reference of the game, and your goal here is to finish solving the game. As I mentioned earlier, I'm going to chat about two different solutions on how you might go about solving it. But I encourage you before you go and look at those videos, try and play around with this game yourself. Try and solve the game, or at the very least figure out what strategy might use and you can follow along as we develop a solution. So, I'll see you then.
