Can you do the Google Doodle.

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.)

About these ads

3 Responses to Can you do the Google Doodle.

  1. Cliff Sather says:

    I have looked through several “explanations” but none of them explained the functional basics of the keys, the green key and the ribbon. This explanation does and it makes a lot of sense. Thanks for not just being smart enough to figure things out, but being able to explain it to someone who had made drastically different assumptions about how everything inter-related and worked.

    I am dumb. You are smart. But more important, your knowledge can be leveraged because you can explain and teach. Good job!

  2. armchairdissident says:

    Many thanks Cliff, when I’m writing about computer systems I always try to be careful with making assumptions about people’s knowledge and it’s nice to know that, at least in this instance, I’ve succeeded! Of course, it’s got nothing to do with smart or not smart, I’m simply fortunate enough to have an extensive background in computing. I don’t know what you do for a living, but I’m prepared to bet good money that I’d look pretty dumb if I tried to do it ;)

  3. paleciak says:

    paleciak…

    [...]Can you do the Google Doodle. « Armchair Dissident[...]…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: