Каракули от Google для детского кодирования: самая короткая программа, решающая все уровни

26

Сегодняшний дудл Google посвящен празднованию 50-летия детского кодирования : цель состоит в том, чтобы запрограммировать путь маленького зайчика, чтобы он мог съесть всю морковь. Есть 4 типа блоков (см. Рисунки ниже):

описание блока

Слева направо:

  • O("...", k)= оранжевый кусок: это forциклы, которые k раз исполняют программу "...".
  • G = зеленая фигура: сделайте один шаг вперед, если можете, иначе ничего не делайте
  • Bl = синий кусок: повернуть направо и остаться на том же блоке
  • Br = синий кусок: поверните налево и оставайтесь на том же блоке

большая программа

Код выше можно записать как

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

Каждый блок ( G, Bl, Br, O(...,k)) считается за 1 единицу, поэтому эта программа имеет длину 7. Обратите внимание, что значение kвключено в 1 единицу O.

Есть 6 уровней. Чтобы пройти уровень, вам нужно съесть всю морковь. Это не проблема, если ваша программа не полностью выполнена, уровень заканчивается сразу, когда вы едите последнюю морковку.

Мы предполагаем, что все 4 типа блоков доступны на каждом уровне.

Ваша задача - найти единую программу, которая решает все уровни игры.
Кратчайшая программа в блоках выигрывает.

Снимки экрана каждого уровня:
Уровень 1: Уровень 2: Уровень 3: Уровень 4: Уровень 5: Уровень 6:скриншот 1 уровня
скриншот 2 уровня
скриншот 3 уровня
скриншот 4 уровня
скриншот 5 уровня
скриншот 6 уровня

Сурб
источник

Ответы:

24

Не мой ответ

6 блоков

Пользователь Alex нашел более короткое решение, длиной 6. Я могу подтвердить, что его решение работает:

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

6 блоков

Они попытались отредактировать этот вопрос, чтобы добавить этот ответ, поэтому я предполагаю, что они хотят, чтобы он отображался здесь. Мне не нравится, как здесь работает система репутации.

Сообщение, которое они оставили:

Редактор не имеет 10 повторений, но имеет решение длины 6. O (O (RGG, 6) R, 5)

Через несколько дней они снова отреагировали, отредактировав сообщение: «Спасибо за это. Редактировать это был единственный способ, которым я видел, чтобы получить сообщение. Я счастлив, что оно существует вообще. Не стесняйтесь перенести его в новый пост, если Вы хотите, хотя. "

Старый ответ

7 блоков

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

Требуется терпение.

Изменить: изображение было неправильно. 7 блоков

Рейнис Мажейкс
источник
Хорошая находка! Я попробовал этот подход, но не получился с этой конкретной комбинацией, прежде чем сдаться и перейти к своему 9-блочному решению.
Спарр
2
Пользователь Alex утверждает, что нашел более короткое решение.
Джонатан Фрех
@JonathanFrech действительно у него есть! Это ограничение 10 повторений раздражает. Я понимаю, что мы должны предотвращать спам, но разве у новых пользователей не должно быть хотя бы модерируемого способа публикации ответов? Свобода слова и прочее.
Рейнис Мажейкс
@ RM Я также был немного раздражен, увидев проблему. Я думаю, что SE просто не предназначен для одноразовых ответов, так как разочарование это, вероятно, для Алекса ...
Джонатан Фрех
1
Почему вы отредактировали это в своем старом ответе вместо того, чтобы публиковать его как новый ответ?
Спарр
12

Собственно, я нашел решение с 8 блоками

O(O(O(G,4)R,4)GGR,4)
samuelleal
источник
6

Найдено вручную, 9 блоков

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

Я начал с очевидного, O(O(GGR,4)L,4)что решает уровни 1-5, затем попробовал несколько вариантов, добавив фактически нулевые ходы на этих уровнях, чтобы найти тот, который завершил бы уровень 6. Самый короткий из них был простым направо-направо-налево в середине каждого "моста". «поэтому движение вперед не имело никакого эффекта.

Sparr
источник
1
Это, вероятно, оптимально, что означает, что проблема уже закончена. :(
полностью человек
6
@totallyhuman выясняется, что сообщество еще не закончило с этим: P
HyperNeutrino
«Очевидное O(O(GGR,4)L,4)» опровергает, что самое короткое решение для уровня 4 - 7, как показано в игре.
МИК
1
@mik Игровые решения не зависят от изменения размера петли или движений, которые ничего не делают.
Нил
@totallyhuman, ты предсказываешь, был совершенно неправ :). Еще через год после того, как вопрос был опубликован, было найдено лучшее решение.
Сурб