Nowadays we seem to have an endless supply of puzzle games on mobile devices to keep our minds occupied during all of the spare moments of the day. It's fine to use puzzle games to fill up the empty spaces of time, but I've found some games that entice me to go much deeper. Lately I've been getting into games geared towards introducing kids to programming concepts. Lightbot and Cargo-Bot are games that teach young kids the basics of programming by setting up sequences of simple instructions for on-screen robots to carry out in pursuit of a goal. While these are kids' games, and quite good ones at that, I've also found them to be excellent practice tools for me.
What I like about these games as a way to practice programming as an adult is that the pressure is off. Since they don't use formal programming languages and instead have cute avatars following simple movement instructions, I can give myself permission to sit back and enjoy doing something I've loved since I was a kid. Most of the time, a solution to the problem the game is presenting comes easily to mind, but there is a deeper challenge. Once you've found a solution, the difficult part is optimizing it to the minimum number of instructions or the shortest execution path. I've found myself deep in thought on the best way to optimize a solution on a number of occasions, sometimes working out better solutions over a period of days. Shaving off an instruction here and there is incredibly satisfying.
What follows is an example of the path I took to a solution for the Double Sort level in Cargo-Bot. After an initial solution, I looked at the hints and saw that the shortest known solution used 11 registers (instructions), but over the course of a half-dozen iterations, I stumbled across a solution using only 9 registers. It was quite satisfying and, I believe, instructive for how beneficial it is to keep attacking a problem and revising the solution to discover better ways to reach a goal.
Spoiler Alert: If you haven't already guessed it, I'll be showing solutions to the Double Sort level of Cargo-Bot in detail. If you want to solve it yourself, do it before reading on.
Double Sort starts out like this:
The idea is to make the initial setup in the middle of the screen look like the goal box at the top using only the four sets of program registers in the bottom left and the instructions in the toolbox at the bottom right. The arrows move the crane, and when the crane moves down it will pick up a box if it's empty or drop the box if it's carrying one. The red instructions jump to each of the numbered program registers and execution will return to the caller when the program hits the last instruction in the callee. The colored tabs are used to mark instructions, and those instructions will only execute when the crane is holding the corresponding colored box (or empty for the grey tab). Simple enough, so let's look at an initial attempt at this problem.
This is a straightforward solution of the problem, doing it almost the way I would do it by hand. That's often a good way to start, by doing something you know how to do. It probably won't be efficient or optimal, but it's a starting point. We shouldn't expect to leap right to the finish without experimenting and playing around a bit.
So what's this program doing? PROG1 picks up a box and essentially examines it, performing different actions depending on the color of the box. If there was no box in that column, it moves right and goes to PROG2 (we'll come back to that in a second). If it's a yellow box, the program runs a 3-instruction action that puts the box in the column to the right and comes back to the previous column. If the crane picked up a blue box, it does the opposite action, moving the box to the column on the left and coming back. Then the program repeats PROG1. If the program found the column empty, it had moved right and started PROG2. PROG2 does pretty much the same thing as PROG1, except if the column is empty, the crane moves back to the left and runs PROG1 again, and at the end it repeats PROG2 instead of PROG1.
The basic procedure that the crane follows is to move the boxes under its starting position either left or right, depending on their color. When the current column is empty, it will move right to work on the next column, keeping track of the fact that it moved right. When that column is empty, it has to move left again because there are some leftover blue boxes in the second column that need to be moved to the first column. As I said earlier, this procedure is almost the same as what I would do if I were physically sorting these boxes. I would more directly move each box to its final resting place by moving the yellow boxes in the second column to the right two columns and the blue boxes in the third column to the left two columns instead of one, but I didn't think at the time that I had enough registers to accomplish that in the program.
Now that we have a starting point, how do we make it better? It's hard to wrap your head around optimizations that would work in this problem because the program needs some way of keeping track of which column is the anchor point for the crane. The valid moves are dependent on which column the crane picked the box from, and that requires some way to switch between two sub procedures. It is obvious that there is a fair amount of duplication, though. PROG1 and PROG2 are very similar, as are PROG3 and PROG4. The flash of insight comes from realizing that the down arrows at the beginning of PROG1 and PROG2 could serve two purposes: picking up and putting down a box. With that observation, we can merge PROG3 into PROG1 and PROG4 into PROG2 like this:
Let's again mentally simulate what's going to happen here. Simulating a program in your mind is a great way to improve your problem solving skills by following a complex sequence, keeping multiple moving parts in your head at once. It's like following a line of moves in chess—the longer the line of moves you can visualize in your head while correctly tracking where all the pieces are, the better you'll get at calculating long combinations of moves.
Here, the crane starts by picking up a yellow box. It's not empty, so it moves the yellow box right and execution goes to PROG2, which promptly puts the box down. Now the crane is empty, so it moves left (back to the second column) and repeats PROG2, picking up another yellow box. Now that it has a yellow block, it moves right and repeats PROG2, putting the box down. This time when it returns to the second column and picks up a box, it's a blue box, so the crane moves left and execution goes to PROG1.
The program then stays in PROG1 while the blue boxes are dropped in the first column and the crane returns to the second column. When the second column is empty, the crane moves right, repeats PROG1, picks up a yellow box, and starts repeating the whole process of sorting boxes right and left from the third column. When the third column is empty, the previous box that the crane held was yellow, so the program is in PROG2. This is important, because that means when the crane is empty, it will move left and finish moving the blue boxes in the second column to the first column. If the last box in the third column wasn't yellow, this program would not work correctly!
The fact that this program's correctness is dependent on the input is a slight shortcoming, but it works for this input and that's all that the game requires. We were also able to reduce an 18 instruction program down to 12 instructions, which is pretty good. However, I know from the hints that I should be able to shave off one more instruction. I can also see that the down, move right if yellow, and move left if blue instructions are all repeated twice, making me think that there should be a way to reduce this program by at least one of those instructions.
Unfortunately, I got stuck at this point. No matter how I shuffled the instructions around, I could not figure out how to remove any of those duplicate instructions without breaking the program. After coming back to this problem a few times over the course of several days, I finally decided to take a different tack, and I brought back the dedicated actions for moving colored blocks left or right one column:
As you can see, I blew away PROG2 and tried to make this program work solely with PROG1 and the two helper actions, for a total of 11 instructions. It gets close, but it doesn't work:
When Cargo-Bot programs don't work, they either get into an infinite loop, or they crash, literally. This one crashes.
I didn't want to give up on this new line of thought, though, so I pursued some optimizations while I continued to think about why the program was failing. First, I noticed that the down and right instructions in PROG4 are repeated at the beginning of PROG1, so I could remove them while maintaining the same behavior:
Now PROG4 only has one instruction in it, so I can replace the call to PROG4 with that instruction:
Suddenly, I'm down to only 8 instructions, and a simple, easy to understand program! The crane continuously picks up a block. If it's blue, the crane moves left, puts it down and moves right, all in PROG1. If it's yellow, the crane moves right, puts it down and moves left, all in the helper action in PROG3. But I still have that nasty crash after the third column is empty:
The problem is that pesky third column. When that column empties, the crane keeps marching right when it should go left. As I continued to mess around with the instructions, that idea kept running through my mind. How do I make the crane go left at that point. I was stuck again, but then it occurred to me that it's really hard to detect the need to go left precisely when the third column was empty with only the instructions I had available. What if I always assumed I had to go left?
See that double move left in PROG2? That's the insight. I had also shifted the move right instruction up to PROG1 during some other experimenting, but this program works. And it's only 9 instructions! That's two better than what the game thought was the optimal solution. I decided to clean up that move right if yellow instruction to make the program clearer:
The flow of the program is now to pick up a box, and if it's blue, put it in the column to the left and move right. If the box is yellow, put it in the column to the right and move left twice. It's as if the crane does some over-scanning after yellow boxes, and that's enough of a correction to pick up the last two blue boxes in the second column and put them in the first column without crashing the crane into a wall. After all of that hard thought, finding a new solution was immensely satisfying. I never did find that 11 instruction solution, but oh well.
What I love about this game, and all good puzzle games, is that it gives you permission to play with ideas and think deeply without external time or performance pressure. It's easy to just try things without worrying about whether it will work or not, and it's fun. I like to think that the mental abilities to work out minimum sequences of instructions and efficiently solve problems that I improve by playing these games will transfer to my day job, but even if they don't, I still have the satisfaction of solving some cool puzzles. It's one of the main reasons I got into programming in the first place.
Here's a video of the 9-instruction solution so you can see the process that the crane goes through to sort the boxes:
No comments:
Post a Comment