O doodle do Google hoje é sobre Celebrando 50 anos de codificação infantil : o objetivo é programar o caminho de um coelhinho para que ele possa comer todas as cenouras. Existem 4 tipos de blocos (veja as fotos abaixo):
Da esquerda para a direita:
O("...", k)
= pedaço laranja: sãofor
loops que executam k vezes o programa"..."
.G
= peça verde: dê um passo adiante, se puder, caso contrário, não faça nadaBl
= peça azul: vire à direita e permaneça no mesmo blocoBr
= peça azul: vire à esquerda e permaneça no mesmo bloco
O código acima pode ser escrito como
O(O(G G Br, 4) Bl Bl, 23)
Cada bloco ( G, Bl, Br, O(...,k)
) conta como 1 unidade; portanto, este programa tem o comprimento 7. Observe que o valor de k
está incluído na 1 unidade de O
.
Existem 6 níveis. Para terminar um nível, você precisa comer todas as cenouras. Não é um problema se o seu programa não for totalmente executado, o nível termina diretamente quando você come a última cenoura.
Assumimos que todos os 4 tipos de blocos estejam disponíveis em todos os níveis.
Sua tarefa é encontrar um único programa que resolva todos os níveis do jogo.
O programa mais curto em blocos vence.
Capturas de tela de cada nível:
Nível 1:
Nível 2:
Nível 3:
Nível 4:
Nível 5:
Nível 6:
fonte
Na verdade, eu encontrei uma solução com 8 blocos
fonte
Encontrado manualmente, 9 blocos
O(O(GRGLGR,4)L,4)
Comecei com o óbvio
O(O(GGR,4)L,4)
que resolve os níveis 1 a 5 e depois tentei algumas variações adicionando movimentos efetivamente nulos nesses níveis para encontrar um que completasse o nível 6. O mais curto era uma simples direita para a frente esquerda no meio de cada ponte " "então o avanço não teve efeito.fonte
O(O(GGR,4)L,4)
" nega que a solução mais curta para o nível 4 seja 7, como mostrado no jogo.