Agulha no palheiro na ciência da computação

O jeito lento: olhar tudo

Se você não sabe nada sobre onde a agulha está, a única opção é verificar cada pedaço de feno até achá-la. Na computação, isso se chama busca linear. Em média, você confere metade de tudo antes de ter sucesso e, no pior caso, tudo. Sempre funciona, mas o tempo cresce na proporção do tamanho do monte.

Ordenar muda tudo

Imagine agora que o feno estivesse organizado em ordem, como palavras em um dicionário. Um método mais esperto, a busca binária, abre no meio, decide em qual metade está a resposta e descarta a outra. Repita isso e um milhão de itens são pesquisados em cerca de 20 passos. O porém é que o monte precisa estar em ordem antes, e um palheiro nunca está.

Índices: trapacear se preparando

Bancos de dados e buscadores contornam o problema fazendo o trabalho pesado antes. Eles montam um índice, como a lista no fim de um livro que diz em qual página está uma palavra. Procurar algo fica rápido porque o tempo foi gasto antes. Não existe índice para um palheiro de verdade, e é exatamente por isso que a expressão existe.

Seguindo um sinal

Um detector de metais é diferente. Ele não diz onde a agulha está, mas diz se você está chegando perto. Imagine um número que sobe conforme você se aproxima. Você pode então usar uma regra simples: dar um passo, ver se o sinal ficou mais forte e seguir na direção que o melhora. Programadores chamam uma versão disso de subida de encosta (hill climbing), e ela está por trás de muita otimização prática.

No jogo, o sinal é calculado a partir da distância até o pedaço de metal mais próximo em comparação com o alcance do detector. Os apitos aceleram conforme esse número se aproxima de 1, então seu ouvido faz a subida de encosta por você. Mais em Como funciona o detector de metais.

Quando os sinais falham

A subida de encosta pode travar. Se houver muito metal de sucata perto da agulha, o sinal mais forte pode levar você a um prego. O jogo resolve isso dando aos detectores de nível alto a capacidade de distinguir a agulha. Buscas reais esbarram no mesmo problema e usam sensores melhores ou filtros extras.

O palheiro como dados

O palheiro do jogo é, em si, uma estrutura de dados: uma grade de 88 por 40 por 88 células, cada uma com um número para a densidade do feno. Cavar é mudar números, e chunks de 16 células mantêm o trabalho pequeno. Como isso funciona está em Como funciona o palheiro.