Can you do the Google Doodle.

June 23, 2012

I’m having immense fun with today’s Google doodle. As a programmer who learned Z80 without an assembler so had to write out the opcodes long hand and convert in to hex, and calculate the offsets by hand (up hill, in the snow both ways dagnamit) , I absolutely love the type of complexity that can arise out of a relatively simple instruction set. And when it comes to the puzzles set by the Google doodle, they couldn’t be simpler.

If you don’t want to know how to play the Google doodle, or want to work it out on your own *DO NOT READ THIS POST*.

Still with me? Then we shall begin. We’ll start with a (relatively) straightforward puzzle, but one that contains everything you need to know about solving the puzzles:

Image

This is a puzzle at the start. I haven’t changed anything. The goal is to make the large number on the tape (the 010110) match the smaller number in the top-right corner (the 00011). You do this by programming the Google Turing Machine. And like many interesting puzzles, the rules are simple, the problems are challenging.

The Rules.

When you hit the big green GO button, the puzzle begins by carrying out the instructions from left-to-right starting at the circle to the right of the GO button. It will look at each circle it comes to, perform the task written on the circle and – unless the instruction says otherwise – move one circle to the right. It carries on in this fashion until it moves off the right hand side.

The Google puzzle can carry out precisely four types of instructions:

  1. If there is only a number in the circle, the number at the current position is set to that number.
  2. If there is only an arrow in the circle, the current position is moved to the left or the right depending on the arrow.
  3. If there is a number in a square with an arrow, the puzzle carries on in the direction of the arrow if and only if the number at  the current position is the number in the square (or blank if the square is blank). We’ll call this a condition.
  4. If the circle has a curved arrow (like the yellow circle in the example) then the puzzle carries on by moving back the number of circles in the middle. In the starting example this is two. We’ll call this a branch

Believe it or not, with only these few rules, these puzzles represent everything you need to write any program. It is what is known as a Turing machine.

How to solve

The only thing you can change when solving the puzzles are the circles highlighted in yellow. If it’s not highlighted in yellow, you can’t change it. So in the example above we can only change the branch. If we follow through the logic we can trace out how the program will run:

  • START: Condition: go down if the current value is 1. The current value (the number under the rectangle in the center) is 0. So nothing happens, we continue to the right
  • Condition: Go down if the current value is 1. The current value is still 0, so we continue to the right
  • Condition: Go down if the current value is 1. Once again, it’s still 0 so we continue to the right.
  • Arrow: Move the current position to the left. Something’s changed! This gives us this position:

Image

The current position has moved to the left. But notice also: the value at the current position has changed! So we carry on:

  • Branch: Move back two circles. Moving back two circles from the branch takes us back to the third
  • Condition: Move down if the current value is 1. Well, what do you know! The current value is 1! So we move down to:
  • Arrow: Move the current position to the right, and
  • Arrow: Move the current position to the right.

With a blank circle meaning “do nothing”, the program now just slides off the end and nothing else happens. The numbers don’t match, so the problems not solved.

So how do we go about solving it? Bear in mind that what we want to do is change the number on the tape to match the number in the top corner. In order to change the number on the tape we need to execute a number instruction to make a number change. As it turns out, there’s only one of these, right underneath the starting instruction – our first condition. We also know that current value will be 1 by the time we reach the branch (we know this, because we’ve done a test run, but you can also work it out quite quickly, once you know the rules). We also know that we can change the number of circles the branch moves backwards! What if we do this:

Image

Notice how the branch now takes us straight back to the beginning? Well, this changes everything. Now when we branch we go right back to the first

  • Condtion: Move down if the current value is 1. Well, when it reaches that branch this time around, the current value will be 1, so we move down! And a completely different set of instructions is executed:
  • Number: Number is zero, so we change the current value to 0. This gives us:

ImageLooks to me like we’ve solved the problem! Execution continues along the bottom row, but this only moves the current position, it doesn’t change the tape. Problem solved!

By using these basic principles it is possible to create arbitrarily complex instructions. Indeed, one of the last puzzles (which I can’t now convince Google to serve up) involves shifting the number 1 across in a beautifully crafted loop. This kind of system is what Alan Turing – most famous for his work in cracking the Enigma code – is most well known for in computing circles; it even has a name that you’ve no doubt heard by now: the Universal Turing Machine. It’s a concept that is so essential to modern computer programming and systems design that without it, you wouldn’t be able to read this, because there would almost certainly be no general purpose computers.

Incidentally, if you complete all the puzzles, there’s an extra treat in store, as Google let it go off an execute a somewhat more complicated program. I’m not certain, but I think it’s counting 🙂

Image(All images taken from the Turing Google Doodle.)

Advertisements