Há um enigma interessante no final de Harry Potter e a Pedra Filosofal. Harry e Hermione entram na sala, após o que as entradas são bloqueadas por fogo mágico, e eles só podem sair resolvendo o seguinte enigma:
[da "tradução popular" do livro "Harry Potter e a Pedra Filosofal"]Há perigo à sua frente e salvação atrás de você,
Duas pessoas que você encontra entre nós irão ajudá-lo;
Com um dos sete você continuará avançando
O outro irá levá-lo de volta imediatamente.
Em nós dois você encontrará apenas vinho de urtiga,
E três trazem destruição, ficando em fila secretamente.
Então escolha qual você está destinado a provar,
Para isso, damos quatro dicas.
Em vão o veneno tentou esconder o seu calor mortal,
Você sempre o encontrará à esquerda do vinho,
E saiba que aqueles que estão nas bordas guardam um presente diferente,
Mas se você quiser continuar, ninguém vai ajudar.
Todos nós variamos em tamanho, de ponta a ponta,
Sua morte não está no menor, mas também não está no maior;
O segundo da extremidade direita e o segundo da esquerda
Eles têm gosto de gêmeos, embora não sejam parecidos.
Simplificando, eles precisam entender quais garrafas contêm quais poções.
Neste artigo, resolveremos todas as 42 variações possíveis deste quebra-cabeça usando programação e desenharemos um diagrama dos resultados (como na imagem acima, só que muito maior).
Espere um segundo, de onde vieram 42 opções?
Isso ocorre porque as localizações das poções “menores” e “maiores” não são indicadas. O maior pode estar em um dos sete lugares, o que dá 6 opções restantes para o menor, num total de 7 * 6 = 42. Não será possível descobrir exatamente qual arranjo JK Rowling tinha em mente quando surgiu com esse enigma, a menos que ela fale sobre isso no seu Twitter. Bem, até que esse dia inevitável chegue, podemos escolher uma versão aleatória e trabalhar com ela. No entanto, não haverá garantia da sua solubilidade, razão pela qual trabalhamos para o bem comum, resolvendo todas as 42 variantes do enigma (ou provando a sua insolubilidade).
DECIDA JÁ
Primeiro, aqui estão todas as restrições do quebra-cabeça, reformuladas em termos simples:
- Existem duas poções inofensivas, 3 venenosas, uma que permite avançar e outra que permite voltar.
- No lado esquerdo de cada uma das duas poções inofensivas está uma poção venenosa.
- As poções de ambos os lados são diferentes e nenhuma delas permite que você avance.
- As garrafas maiores e menores não contêm veneno.
- O segundo frasco à esquerda e o segundo frasco à direita contêm a mesma poção.
Como lidar com isso? Vamos considerar a seguinte opção. Observe que, como diz o enigma, na fileira há 1 garrafa menor que todas as outras em tamanho e 1 garrafa maior que todas as outras.
Vamos tentar estupidamente passar por todas as opções - pegue uma garrafa de cada vez e selecione todas as opções possíveis de conteúdo.
Por exemplo, a primeira garrafa não pode conter uma poção que nos faça avançar devido à restrição nº 3. Também não contém uma poção segura devido à restrição nº 2 - não pode haver veneno à esquerda dela. Isso nos deixa com as opções de poção venenosa e poção de retrocesso. Vamos tentar as duas opções.
Nas imagens a seguir, as poções verdes representam veneno, as laranjas são bebidas seguras, as azuis são as poções que se movem para trás e as roxas são as poções que avançam.
Vamos repetir este processo para ambas as opções de trabalho - pegue a segunda garrafa e experimente alternadamente todas as opções de conteúdo aceitáveis. Isso nos dará o seguinte:
Continuando a agir nesse sentido, e descartando todas as opções de trabalho em que algum frasco não possa ser preenchido com uma poção sem violar as restrições listadas, chegaremos à única opção aceitável:
Naturalmente, não tínhamos garantia de encontrar uma solução. Pode não haver solução, ou pode haver várias (e se você tiver várias soluções, isso é o mesmo que o enigma ser impossível de resolver porque você não sabe qual poção é a correta).
Aplicar o algoritmo a todas as opções nos dá as seguintes soluções. 8 versões do enigma podem ser resolvidas, 8 não têm soluções e 26 têm múltiplas soluções.
Mais sobre soluções
Todas as versões resolvidas do enigma têm algo em comum? Sim! Observe que neles as garrafas menores ou maiores ficam em 2º ou 6º lugares. Isto nos permite concluir que os 2º e 6º frascos contêm poções seguras devido às restrições #4 e #5. Sem este passo, não podemos eliminar a possibilidade de estas garrafas conterem veneno e acabamos com várias soluções possíveis. Também as opções resolvidas exigem que a segunda garrafa “especial” (menor ou maior) seja colocada em 3º ou 4º lugar. Caso contrário, não será possível encontrar a localização exata da poção que nos faz avançar.
Resultados de
Encerrarei com uma citação do livro.
Hermione exalou alto, e Harry ficou surpreso ao notar que ela estava sorrindo – foi a última coisa que poderia ter ocorrido a ele. "Brilhante," disse Hermione. - Isso não é mágica - isso é lógica, um enigma. Muitos dos maiores mágicos não têm um pingo de lógica e ficariam presos aqui para sempre."
Mas espere um minuto - talvez possamos descobrir a versão canônica do enigma com base no diálogo do livro:
“Entendi”, disse ela. “A menor garrafa nos levará através do fogo negro e até a Pedra.”
...
“E qual permitirá que você retorne através do fogo roxo?”
Hermione apontou para uma garrafa redonda no lado direito da fileira.
Caramba. Esta opção ainda nos dá várias soluções. Tweet, DR.
código
Se você estiver interessado no código para resolver esse quebra-cabeça e desenhar os diagramas, você pode .
Fonte: habr.com