Google's doodle on kids coding: shortest program solving all the levels

26

4

Today's Google doodle is about Celebrating 50 years of Kids Coding: The goal is program the path of a little bunny so that it can eat all the carrots. There are 4 types of blocks (see pictures below):

block description

From left to right:

  • O("...", k) = orange piece: these are for loops which executes k times the program "...".
  • G = green piece: go one step forward if you can, otherwise do nothing
  • Bl = blue piece: turn right and stay on the same block
  • Br = blue piece: turn left and stay on the same block

big program

The code above can be written as

O(O(G G Br, 4) Bl Bl, 23)

Each block (G, Bl, Br, O(...,k)) counts as 1 unit, so this program is of length 7. Note than the value of k is included inside the 1 unit of O.

There are 6 levels. To finish a level you need to eat all the carrots. It is not a problem if your program is not fully executed, the level finishes directly when you eat the last carrot.

We assume that all the 4 types of blocks are available in every level.

Your task is to find a single program which solves every level of the game.
Shortest program in blocks wins.

Screen shots of each level:
Level 1: level 1 screenshot
Level 2: level 2 screenshot
Level 3: level 3 screenshot
Level 4: level 4 screenshot
Level 5: level 5 screenshot
Level 6: level 6 screenshot

Surb

Posted 2017-12-05T12:51:52.280

Reputation: 371

Answers

24

Not my answer

6 blocks

The user Alex found a shorter solution, of length 6. I can confirm that their solution works:

O(O(Br G G, 6) Br, 5)

6 blocks

They attempted to edit this question to add this answer, so I'm assuming they want it to be displayed here. I don't like how the reputation system works around here.

The message they left:

The editor doesn't have 10 rep, but does have a solution of length 6. O(O(RGG,6)R,5)

After a few days they responded again via editing the post with: "Thanks for doing this. Editing this was the only way I saw to get a message. I am happy it exists at all. Feel free to bring it into a new post if you want though."

Old answer

7 Blocks

O(O(G G Br, 4) G Br, 100)

Patience required.

Edit: The image was wrong. 7 blocks

Reinis Mazeiks

Posted 2017-12-05T12:51:52.280

Reputation: 388

Good find! I did try this approach but didn't happen on this particular combination before giving up and going for my 9 block solution. – Sparr – 2017-12-10T02:04:18.783

2

The user Alex claims to have found a shorter solution.

– Jonathan Frech – 2019-05-03T20:06:24.103

@JonathanFrech indeed he has! That 10-rep limit is annoying. I get that we have to prevent spam, but shouldn't new users have at least a moderated way of posting answers? Freedom of speech and stuff. – Reinis Mazeiks – 2019-05-04T10:38:06.390

@R.M I was also a bit irritated upon seeing the problem. I guess SE simply is not designed for one-off answers, as frustrating this probably is for Alex ... – Jonathan Frech – 2019-05-04T13:07:59.263

1Why did you edit this into your own old answer instead of posting it as a new answer? – Sparr – 2019-05-05T18:54:53.070

12

Actually, I found a solution with 8 blocks

O(O(O(G,4)R,4)GGR,4)

samuelleal

Posted 2017-12-05T12:51:52.280

Reputation: 121

6

Manually found, 9 blocks

O(O(GRGLGR,4)L,4)

I started with the obvious O(O(GGR,4)L,4) that solves levels 1-5 then tried a few variations adding effectively-null moves on those levels to find one that would complete level 6. The shortest was a simple right-forward-left in the middle of each "bridge" so the forward move had no effect.

Sparr

Posted 2017-12-05T12:51:52.280

Reputation: 5 758

1This is probably optimal which means the challenge is already over. :( – totallyhuman – 2017-12-06T00:43:50.790

6@totallyhuman turns out the community's not quite done with this yet :P – HyperNeutrino – 2017-12-06T03:31:52.900

"The obvious O(O(GGR,4)L,4)" disproves that the shortest solution for level 4 is 7, as shown in the game. – mik – 2017-12-06T11:00:01.430

1@mik The game solutions don't rely on changing the loop size or moves that do nothing. – Neil – 2017-12-06T15:53:12.893

@totallyhuman you're forecasting was quite wrong :). Even more than a year after the question was posted, a better solution was found. – Surb – 2019-05-05T13:02:22.717