🧩 Vinte e Nove Bytes para Dizer Olá: Fazendo Code Golf de “Hello, World!” em SuperHack 🔗

Uma análise do desafio “Super Small Hello World” do hacker.org: as soluções que funcionaram, as que quase chegaram lá e o truque que finalmente alcançou 29.

📑 Índice 🔗

🎯 O desafio 🔗

O hacker.org tem uma pequena linguagem esotérica chamada SuperHack. A tarefa parece trivial: escrever um programa em SuperHack que imprima Hello, World!.

O detalhe está na pontuação. Você é avaliado pela área do retângulo delimitador do seu código, e quanto menor, melhor. O programa também precisa terminar corretamente: executando a instrução ! (halt). Travar com uma exceção da VM depois que o texto já saiu não conta, nem imprimir bytes extras indesejados.

O número a ser batido era 29.

🧭 Um tour de dois minutos pelo SuperHack 🔗

SuperHack é uma máquina de pilha 2D, com espírito semelhante ao Befunge:

• O código é uma grade de instruções de um único caractere. O contador de programa (PC) começa no canto superior esquerdo (ou em um %) e se move para a direita.
• Há uma pilha de dados de números inteiros, além de uma pilha de chamadas separada que armazena posições.
• Instruções usadas neste post:

Duas consequências moldam tudo o que vem a seguir.

1. Caracteres são dados. g lê o próprio código do programa, então a string Hello, World! pode simplesmente ficar na grade e ser lida um caractere por vez. A maioria de suas letras (H e l o W r) são no-ops quando executadas. Três não são: , empilha 0, d divide e ! encerra o programa.
2. @ / $ criam loops, e a contagem de iterações depende de onde os @s estão. $ retoma a execução duas células após o @ para o qual retorna. Isso cai no próximo @, que se empilha novamente, de modo que alguns @s podem repetir o corpo do loop muitas vezes:
   • @@@@@ adjacentes geram contagens de Fibonacci. Cinco deles executam o corpo exatamente 13 vezes.
   • @s espaçados de dois em dois geram potências de dois. Quatro deles permitem 16 passagens.

Treze caracteres, treze passagens. Guarde essa informação.

A área é a largura multiplicada pela altura, e 29 é primo. Portanto, um programa de 29 células precisa ser uma única linha ou uma única coluna.

1️⃣ Solução 1: o loop direto (área 32) 🔗

Hello, World!%0@s!@@@@@ 01^gP1+$

A primeira solução funcional coloca o payload no início e começa a execução depois dele:

O gadget de parada. O primeiro @ coloca sua própria posição no fundo da pilha de chamadas, e s salta sobre o !. A cadeia de Fibonacci faz então suas 13 passagens. Quando a pilha de chamadas finalmente se desenrola até aquele primeiro @, $ retoma duas células após ele, que é exatamente o !. O programa para de forma limpa, e não há nenhum teste de fim de string em lugar algum.

O preenchimento (padding). Com @s adjacentes, retornar do último @ retoma duas células depois, o que pula a primeira célula após a cadeia. Essa célula deve, portanto, ser algo inofensivo, razão pela qual é um espaço.

Resultado: Hello, World!, parada limpa, área 32. Está correto, mas espaçoso: o payload é peso morto, e o %, o espaço de preenchimento e o 0 custam, juntos, três células.

2️⃣ Solução 2: intercalação (área 28, mas inválida) 🔗

1H@e@l@l@o ,1 ^WgoPr2lsds!+$

A próxima ideia é parar de gastar células com um payload separado e entrelaçar a string no código. Os caracteres de Hello, World! ficam nas colunas ímpares (1, 3, …, 25), e o código preenche as colunas pares entre eles:

• 1 inicia o índice na coluna 1 (o H).
• Quatro @s espaçados de dois em dois (colunas 2, 4, 6, 8) permitem até 16 passagens.
• A própria , do payload (coluna 11) empilha o 0 de que g precisa como linha.
• 2+ avança o índice para a próxima coluna ímpar.
• Células s saltam sobre o d e o ! do payload, para que não rodem como código.

O problema é que 16 passagens são mais do que 13. Depois de imprimir a string, o loop continua buscando além do fim e imprime $ e dois bytes NUL. Em seguida, $ encontra a pilha de chamadas vazia e a VM morre:

output:  "Hello, World!$\0\0"
message: call stack underflow

É pequeno, mas não é uma solução válida. Ainda assim, introduz a ideia-chave: caracteres do payload que por acaso são instruções úteis (,) cumprem dupla função como dados e código.

3️⃣ Solução 3: indo para a vertical (área 27, mas inválida) 🔗

\
2
H
@
e
@
l
@
l
@
o
x
,
g

P
W
2
o
+
r
$
l

d

!

(Um caractere por linha. As linhas em branco são espaços simples, que fazem parte dos dados.)

Colocar o programa na vertical traz um benefício inesperado. Em uma única coluna, g precisa que a coordenada x seja 0 e a linha seja i. A , do payload fornece esse 0 de graça, então a busca encolhe para x , g: duplicar i, empilhar 0, buscar. O custo é um \ no topo para virar o PC para baixo.

Contudo, ele tem a mesma falha da solução 2. O loop passa do ponto, imprime bytes NUL e termina em call stack underflow. Com área 27, é o menor programa deste post, mas não vale.

A lição das soluções 2 e 3 é que parar de forma limpa custa células. A intercalação torna o loop barato, mas entrega 16 passagens quando você precisa de exatamente 13.

4️⃣ Solução 4: pagando pela saída (área 30) 🔗

\
2
H
@
e
@
l
@
l
@
o
x
,
g
 
P
W
x
o
5
r
d
l
5
d
?
!
2
+
$

A solução 4 mantém a intercalação vertical da solução 3 e adiciona um teste de fim de string de verdade:

O índice percorre 2, 4, …, 26. floor(i/25) permanece 0 até o último caractere (i = 26), de modo que o ? pula a parada em todas as passagens, exceto na última. Na última passagem, a execução cai sobre o ! do payload, que é simultaneamente o último caractere impresso e a instrução que encerra o programa.

É um belo exemplo de reaproveitamento: ,, d e ! do payload servem todos como código. Mas o teste custa cinco células, e o total vai para 30.

🧱 Por que 29 parecia impossível 🔗

Nesse ponto, meu assistente de IA tentou provar que 30 era o limite ótimo. Todas as abordagens pareciam esbarrar na mesma parede:

• A intercalação bloqueia o loop barato. Treze passagens exigem cinco @s adjacentes, e uma intercalação não tem células de código adjacentes. Assim, você fica preso a 16 passagens e a um teste pago com células.
• A paridade bloqueia saídas mais baratas. Em uma intercalação, ? nunca pode ficar diretamente na frente de $. A célula entre eles é sempre uma célula de payload.
• Um payload contíguo bloqueia o outro design. Coloque o payload em um único bloco e o loop de Fibonacci volta a caber. Mas então o payload precisa viver em algum lugar nunca executado (custando um % ou um índice inicial grande), porque executar ...d! como código trava ou encerra o programa prematuramente.

Buscas exaustivas por computador em áreas menores não encontraram nada, e buscas em torno do layout da solução 4 com área 29 também não deram resultado. “30 é o piso” começou a parecer um teorema.

Não era.

🏆 Solução 5: vinte e nove (área 29) 🔗

9@s!@@@@@Hello, Worlä¡1^gP1+$

A virada veio ao reler o código-fonte do juiz. Duas linhas importam:

case 'P':
  $output .= chr($this->Pop() & 0x7F); break;
...
default:
  break;   // every unknown character is a no-op

• P imprime apenas os 7 bits menos significativos. Um byte com o bit mais significativo ativado, c + 128, é impresso exatamente como c.
• Um byte de 128 a 255 não é uma instrução, então é executado como no-op.
• Strings em PHP são sequências de bytes, portanto um byte desses ocupa uma única célula como qualquer outro.

Cada caractere do payload tem, portanto, duas codificações. A normal pode fazer alguma coisa quando executada. Já a versão c | 0x80 é garantidamente inerte. Essa é a “fórmula para os dados”: armazene os caracteres perigosos como c + 128 e deixe que P remova o bit alto de graça.

Apenas dois caracteres do payload são perigosos: d vira ä (0xE4) e ! vira ¡ (0xA1). Com esses dois alterados, todo o payload pode ser executado. Isso remove o obstáculo do terceiro item acima.

Agora pegue a solução 1 e mova o payload para dentro do loop:

Acompanhe uma passagem:

1. O PC aterrissa em algum ponto da cadeia de @ e percorre o payload. H e l l o, o espaço e W o r l não fazem nada. A , do payload empilha o 0 de que g precisa como linha. ä e ¡ não fazem nada.
2. 1^ copia i acima desse 0, e g busca a coluna i.
3. P imprime o caractere. Para os dois últimos caracteres, ele imprime 0xE4 & 0x7F = 'd' e 0xA1 & 0x7F = '!'.
4. 1+ avança i, e $ retorna para a cadeia.

Em comparação com a solução 1, três células desaparecem:

• %: o payload não precisa mais ser protegido da execução.
• O espaço de preenchimento: a célula pulada após a cadeia agora é o H do payload, um no-op.
• O 0 antes de 1^g: a , do payload o fornece em todas as passagens.

32 − 3 = 29. Após a 13ª passagem, a pilha de chamadas se desenrola até o gadget e o programa para no ! da coluna 3.

Saída Hello, World!, nenhuma mensagem da VM, 271 ciclos, área 29.

🌐 O último obstáculo: fazer os bytes chegarem ao juiz 🔗

O primeiro envio retornou got: 'Hello, WorlC$' e uma pontuação de 31. O formulário web havia enviado UTF-8, o que transformou cada caractere especial em dois bytes (ä → C3 A4, ¡ → C2 A1). Mascarados para 7 bits, 0xC3 é impresso como C e 0xA4 como $.

A correção consiste em fazer o navegador enviar em Latin-1, codificação na qual cada um desses caracteres ocupa um único byte. Na página do desafio, precisei abrir o console do DevTools e executar:

document.querySelectorAll('form').forEach(
  f => f.acceptCharset = 'ISO-8859-1');
document.querySelector('textarea').value =
  "9@s!@@@@@Hello, Worl\u00e4\u00a11^gP1+$";

Depois, bastou pressionar o botão normal de envio. O juiz imprime Hello, World!, e a pontuação no King of the Hill crava 29.

📊 Placar 🔗

💡 Lições aprendidas 🔗

• Dados também são código. Cada avanço decisivo veio de permitir que as mesmas células servissem para ambos os papéis: a , do payload como um push 0 gratuito, seu ! como a parada, e, finalmente, todo o payload como parte do corpo do loop.
• Uma prova de impossibilidade só é tão boa quanto suas premissas. “30 é o piso” era verdade para layouts intercalados e restritos a caracteres ASCII imprimíveis. Nenhuma dessas restrições estava nas regras.
• Leia o código-fonte real. Uma busca por força bruta dentro de um espaço de design fixo não consegue encontrar uma resposta que esteja fora dele. Duas linhas de PHP do juiz (& 0x7F e default: break) fizeram o que horas de busca automatizada não conseguiram.
• Cuidado com o transporte. Um programa correto ainda pode falhar quando o formulário web altera seus bytes no caminho até o juiz.