There's a joke (or as my former professor might have said, "it's like a joke, it just lacks humor") about how programmers think:
Programmer: "How do I make pasta?"
Recipe: How to make pasta:
Programmer: "How do I make pasta?"
Recipe: How to make pasta:
- Fill an empty pot with cold water
- Boil it
- Add pasta
Programmer goes home and wants to make pasta. She sees a pot of boiling water already on the stove. So she pours it out, fills it up with cold water, boils it, then adds pasta.
Again, like a joke, but potentially lacks humor.
For those not "in the know," the joke is that programmers tend to reduce problems to ones they've already solved. In this case, the programmer already had a solution for making pasta. So, she changed things around until she could use it.
In this case, we end up doing more work than necessary, but in general, this can be extremely effective.
This week, the Google Doodle is pretty great. It's a coding game geared toward kids, in the same vein as Scratch or Alice, where instead of writing code, you can click-and-drag three kinds of actions: forward jumps, turns, and loops (which let you repeat a set of actions a fixed number of times).
If you haven't played it, play it now. Seriously, it's really fun, and there are spoilers ahead on how to solve the levels.
Levels 4-6 take some clever thinking to solve. Sure, you could map out each individual step, but the fun of these problems is leveraging the loop concept. In fact, starting in level 4, the Doodle shows the minimum number of steps (the action tiles, not number of movements) to solve the problem, encouraging you to find the loop-driven solutions.
Level 3 can be broken down into solving each side. Move forward twice, turn, and now you're set up to solve the next one. In the Doodle, that looks like Loop4(move, move, turn right). In this blog post, I'm using parentheses to mark what goes inside each loop, the way the start and top bars on the loop indicate. LoopX just means that the loop runs that many times (you can click on loop on the Doodle and change the number).
Level 4 is a little more tricky, right? It's like solving level 3 twice. The bunny needs to go around one square, then around the other. One way to solve this is to go around the closer square clockwise (with right turns), turn left twice, then go around the farther square clockwise.
How do we solve that? Well, we learned in level 3 how to "solve a square clockwise": Loop4(move, move, turn right). Let's call that SquareCW=Loop4(move, move, turn right). Then, to solve level 4, we just solve SquareCW, turn left, turn left, SquareCW. When we have the last carrot, we're done. There can be more actions to take, but they don't matter - the bunny stops when he's full.
So, how do we efficiently write out the level 4 solution? Loop2(SquareCW, turn left, turn left) [yes, I could replace some repeated actions with a loop, but because loops cost me an action, it's the same for two actions]. In fact, that's the minimum 7 moves [SquareCW is really 4 moves as written above]! Not only do we have all the carrots, but we did the best possible.
Level 5 is weird though, right? It has more carrots, but the minimum number of moves is only 6 this time! What gives?! This problem is bigger, but Google wants us to use fewer moves to solve it!
In this case, one repeatable pattern is that we still just want to solve squares. Why is this easier? Well, now, instead of needing two left turns to reset between each square (like level 4), we just need one turn (and it can be a left turn or a right turn). Loop4(SquareCW, turn right) solves the bottom square first, then the one on the left, the top, and finally the right. Not needing to turn twice between squares makes the problem that much easier.
Before we get to level 6, let's look again at level 4. Something just felt fishy to me that we really needed all seven moves, especially because (after a bit of testing), if you ask the bunny to hop when there's no room in front, it just says put. In other words, instead of falling off the map, the bunny will essentially just ignore anything we ask it to do that it can't.
So, is there a way we can leverage the SquareCW solution even more efficiently? Well, there are a couple things to note:
- If, when we start, instead of Loop4(move, move, turn), we do Loop8(move, move, turn), the bunny still gets back to the same place. We can do SquareCW any number of times in a row and the bunny ends up exactly back at the middle.
- If we are at any corner of the farther square and do SquareCW, we'll complete the whole thing.
With that in mind, can we take the level 5 solution Loop4(SquareCW, right) and turn it into a level 4 solution (with only 6 actions)?
Yes, yes we can.
At the end of the bottom square, instead of turning twice, let's only turn once: Loop2(SquareCW, left). Now, the bunny gets all the carrots on the bottom half of the farther loop, including the left and right corners. Give that a try: Loop2(Loop4(move, move, right), left)
So close! We were doing so well! At the very end, the bunny just doesn't go far enough around the farther loop (and then turns left at the end, adding insult to injury).
Why is that? Well, we know we need a SquareCW to solve a square, but we have to start at a corner, facing clockwise. We saved a move by not turning twice in the middle like the original solution, but we don't end up at a corner facing clockwise until there are only two sides left of the SquareCW movement. Can you see how to fix it? Do the hints above help?
Yes, yes we can.
At the end of the bottom square, instead of turning twice, let's only turn once: Loop2(SquareCW, left). Now, the bunny gets all the carrots on the bottom half of the farther loop, including the left and right corners. Give that a try: Loop2(Loop4(move, move, right), left)
So close! We were doing so well! At the very end, the bunny just doesn't go far enough around the farther loop (and then turns left at the end, adding insult to injury).
Why is that? Well, we know we need a SquareCW to solve a square, but we have to start at a corner, facing clockwise. We saved a move by not turning twice in the middle like the original solution, but we don't end up at a corner facing clockwise until there are only two sides left of the SquareCW movement. Can you see how to fix it? Do the hints above help?
They do. If instead of Loop4(move, move, right), we do Loop8(move, move, right), now we're done. If you haven't already, give that one a try.
Several things are going on here. First of all, the bunny now does an extra lap of the bottom square. But this doesn't cost us anything as far as the Doodle is concerned -- it's the same number of actions. Second, we now have enough "sides" of the square motion in the farther loop that we can eat all the carrots -- we start at the right corner with at least 4 sides of motion left to run.
Perhaps most importantly though, YOU JUST BEAT GOOGLE! Seriously, the Doodle will give you points and let you go to the next level, but you just used fewer moves than they say is possible. As a former Google intern (or Xoogler - for ex-Googler), I'm offended at the misleading "minimum" numbers.
But I also get it. We had to visit several squares more than once, and we had to leverage this weird "bunny won't jump off a cliff" rule. But, we thought like programmers. We learned a simple solution (SquareCW), and tried our best to reduce problems to that as efficiently as possible.
If you got there before you read it in the post, congrats! And if not, that's okay. This is intended to help you see the world like I (and so many like me) see the problems we work on. Hopefully, it was interesting to you, and maybe a little insightful.
Several things are going on here. First of all, the bunny now does an extra lap of the bottom square. But this doesn't cost us anything as far as the Doodle is concerned -- it's the same number of actions. Second, we now have enough "sides" of the square motion in the farther loop that we can eat all the carrots -- we start at the right corner with at least 4 sides of motion left to run.
Perhaps most importantly though, YOU JUST BEAT GOOGLE! Seriously, the Doodle will give you points and let you go to the next level, but you just used fewer moves than they say is possible. As a former Google intern (or Xoogler - for ex-Googler), I'm offended at the misleading "minimum" numbers.
But I also get it. We had to visit several squares more than once, and we had to leverage this weird "bunny won't jump off a cliff" rule. But, we thought like programmers. We learned a simple solution (SquareCW), and tried our best to reduce problems to that as efficiently as possible.
If you got there before you read it in the post, congrats! And if not, that's okay. This is intended to help you see the world like I (and so many like me) see the problems we work on. Hopefully, it was interesting to you, and maybe a little insightful.
Okay, there's a glaring omission here. What about level 6?
I'm proud of this one. Google says you can do it in 6. I say you can do it in 4. Yeah, you heard me right. I think you can do it 33% better than Google. Go ahead give it a try for yourself.
Need a hint? For Google's solution, think about the problem the way we thought about doing my version of level 4. I managed to find the shorter solution yesterday, but it took until writing this blog post for me to realize Google's solution.
If you find Google's, a hint for mine is that we aren't going to solve SquareCW anymore, but will still leverage similar "bunny won't jump off a cliff" kinds of rules.
Spoilers below.
Google's solution (well, I don't know if it's how they solved it, but it has the minimum number of moves according to the Doodle) is: Loop4(SquareCW, SquareCW, left), which we can write as: Loop4(Loop8(move, move, right), left). It's the same solution as level 5, but we do each "square" twice before turning left. Here, each "square" is defined by the carrots. We make two "side" moves to get the middle carrot and the one clockwise from it. Then, we solve the square (a total of 6 "side" moves), which gets us back to the second carrot we ate in this square. Finally, add two more side moves (a total of 8) to get us near the middle carrot of the next square (from bottom-right, to top-right, to top-left, to bottom-left). It's a really clever solution.
But I can do better. One final hint before the solution, if you're still trying and racking your brain how to do it: the solution has more than 2 moves at once, and we'll use a loop to do it, like LoopX(move).
Alright, enough delay.
The solution is Loop13(Loop3(move), right).
We're still doing something kinda similar, right? The middle looks a lot like the SquareCW solution Loop4(move, move, right). But in that case, we're solving a square with side length 3. We used that in all our solutions so far.
If we used a smaller square (side length 2), we'd have LoopX(move, right). But that just doesn't move enough. If we use side length 5, we'd have LoopX(move, move, move, move, right). But what happens in that case? Well, we move forward, get the carrot immediately clockwise, move across the level, get those three carrots, move across the level to the remaining bottom-right carrot, then end up in a loop on squares without carrots. That's no good.
If we use side length 4, we have LoopX(move, move, move, right), which takes fewer actions if we do LoopX(Loop3(move), right). So, we now have 4x4 squares defined by the corners of the inner green pasture. If we're on one of those facing clockwise and do Loop3(Loop3(move, right)), we'll get three carrots from one of the sides, and end ready to start another square. It takes 3 "sides" to get into position, then 3 for each of the three remaining rows of carrots (12 total "sides"), and one final one to get the last carrot.
(note: I'm sure the developers or other Googlers figured it out, but didn't want to aggravate the kids they're trying to teach)
Yes, I'm a nerd. Yes, I spent too long figuring these things out. Yes, I should be working on my dissertation. Yes, this is how I think on a regular basis.
But hey, I literally did what Google says is impossible...
I'm proud of this one. Google says you can do it in 6. I say you can do it in 4. Yeah, you heard me right. I think you can do it 33% better than Google. Go ahead give it a try for yourself.
Need a hint? For Google's solution, think about the problem the way we thought about doing my version of level 4. I managed to find the shorter solution yesterday, but it took until writing this blog post for me to realize Google's solution.
If you find Google's, a hint for mine is that we aren't going to solve SquareCW anymore, but will still leverage similar "bunny won't jump off a cliff" kinds of rules.
Spoilers below.
Google's solution (well, I don't know if it's how they solved it, but it has the minimum number of moves according to the Doodle) is: Loop4(SquareCW, SquareCW, left), which we can write as: Loop4(Loop8(move, move, right), left). It's the same solution as level 5, but we do each "square" twice before turning left. Here, each "square" is defined by the carrots. We make two "side" moves to get the middle carrot and the one clockwise from it. Then, we solve the square (a total of 6 "side" moves), which gets us back to the second carrot we ate in this square. Finally, add two more side moves (a total of 8) to get us near the middle carrot of the next square (from bottom-right, to top-right, to top-left, to bottom-left). It's a really clever solution.
But I can do better. One final hint before the solution, if you're still trying and racking your brain how to do it: the solution has more than 2 moves at once, and we'll use a loop to do it, like LoopX(move).
Alright, enough delay.
The solution is Loop13(Loop3(move), right).
We're still doing something kinda similar, right? The middle looks a lot like the SquareCW solution Loop4(move, move, right). But in that case, we're solving a square with side length 3. We used that in all our solutions so far.
If we used a smaller square (side length 2), we'd have LoopX(move, right). But that just doesn't move enough. If we use side length 5, we'd have LoopX(move, move, move, move, right). But what happens in that case? Well, we move forward, get the carrot immediately clockwise, move across the level, get those three carrots, move across the level to the remaining bottom-right carrot, then end up in a loop on squares without carrots. That's no good.
If we use side length 4, we have LoopX(move, move, move, right), which takes fewer actions if we do LoopX(Loop3(move), right). So, we now have 4x4 squares defined by the corners of the inner green pasture. If we're on one of those facing clockwise and do Loop3(Loop3(move, right)), we'll get three carrots from one of the sides, and end ready to start another square. It takes 3 "sides" to get into position, then 3 for each of the three remaining rows of carrots (12 total "sides"), and one final one to get the last carrot.
(note: I'm sure the developers or other Googlers figured it out, but didn't want to aggravate the kids they're trying to teach)
Yes, I'm a nerd. Yes, I spent too long figuring these things out. Yes, I should be working on my dissertation. Yes, this is how I think on a regular basis.
But hey, I literally did what Google says is impossible...
Comments
Post a Comment