Resolução de variantes do quebra-cabeça de olhos azuis

8

O quebra-cabeça "Olhos Azuis" original é dado aqui (e abaixo).

Um grupo de pessoas com cores variadas vive em uma ilha. Todos eles são lógicos perfeitos - se uma conclusão puder ser deduzida logicamente, eles farão isso instantaneamente. Ninguém sabe a cor dos seus olhos. Todas as noites à meia-noite, uma balsa para na ilha. Todos os ilhéus que descobriram a cor de seus próprios olhos então deixam a ilha e o restante fica. Todo mundo pode ver todo mundo o tempo todo e mantém uma contagem do número de pessoas que vê com cada cor de olho (excluindo a si mesmas), mas não pode se comunicar. Todos na ilha conhecem todas as regras deste parágrafo.

Nesta ilha, existem 100 pessoas de olhos azuis, 100 de olhos castanhos e o Guru (ela tem olhos verdes). Portanto, qualquer pessoa de olhos azuis pode ver 100 pessoas com olhos castanhos e 99 pessoas com olhos azuis (e uma com verde), mas isso não indica a sua própria cor dos olhos; até onde ele sabe, os totais podem ser 101 marrons e 99 azuis. Ou 100 marrons, 99 azuis, e ele poderia ter olhos vermelhos.

É permitido ao Guru falar uma vez (digamos ao meio-dia), em um dia em todos os seus intermináveis ​​anos na ilha. Diante dos ilhéus, ela diz o seguinte:

"Eu posso ver alguém que tem olhos azuis."

Quem sai da ilha e em que noite?

A resposta é que todos eles partem no centésimo dia. Isso ocorre devido à seguinte lógica:

Se houver apenas uma pessoa de olhos azuis, ele sairá no dia 1. Se houver apenas duas pessoas de olhos azuis, ninguém sai no dia 1. Depois disso, os dois saem no dia 2. Agora, se houver 3 pessoas de olhos azuis, ninguém sai no dia 1. Ninguém sai no dia 2 também. Agora todo mundo sabe que existem três pessoas de olhos azuis, porque se houvesse apenas uma, ele teria saído no dia 1 e se houver duas, ambas teriam saído no dia 2. Portanto, todas as 3 saem no dia 3.

Agora podemos escrever uma prova indutiva de que se n pessoas de olhos azuis precisarem de n dias para descobrir a cor dos olhos e partirem, então n + 1 pessoas de olhos azuis precisarão de n + 1 dias para fazer o mesmo.

No entanto, o código que você escreve deve ser capaz de resolver não apenas o quebra-cabeça original, mas também algumas variantes que exigem etapas indutivas ligeiramente diferentes.

Você será informado quantos dos ilhéus têm olhos azuis e quantos não. Você também receberá uma declaração do oráculo (um sistema de equações / inequações) que todos na ilha ouvem. Você precisa determinar quando a ilha estará livre das pessoas de olhos azuis.

As declarações do oráculo serão usadas bpara o número de pessoas de olhos azuis e rpara o número de pessoas de olhos não azuis. As equações podem incluir < > <= >= = + -e qualquer número inteiro.

Casos de teste

Com base neste conjunto de variantes

50 50
b>=1
b<b+r

Resultado: 50

A segunda equação não fornece novas informações; portanto, esse problema se torna exatamente o mesmo que o quebra-cabeça original.

100 50
b+3>=r+4

Resultado: 25

100 0
b-2>8+1-1

Resultado: 90

50 50
b>=10
b<=75

Resultado: 41

ghosts_in_the_code
fonte
@ Dennis Está tudo bem agora?
Ghosts_in_the_code
Acho que sim. Um pequeno esclarecimento: não parece com os casos de teste, mas as equações (in) podem incluir multiplicações implícitas como 3b<2r?
Dennis
@ Dennis Não, mas poderia ser escrito como b+b+b < r+ralternativa.
Ghosts_in_the_code
O terceiro caso de teste afirma ser baseado em "Pelo menos 10 de vocês estão de olhos azuis", mas na verdade simplifica b>10, não b>=10, portanto a saída deve ser 90, não 91.
Anders Kaseorg
@AndersKaseorg Com preguiça de verificar, mas eu acredito em você, portanto editado.
ghosts_in_the_code

Respostas:

1

Python 2 , 60 48 bytes

f=lambda b,r,c:all(map(eval,c))and-~f(b-1,r+1,c)

Experimente online!

Como funciona

Por indução:

  • Se a composição da ilha é ( b , r ) e se sabe que ( b - 1, r + 1) não é possível, no dia 1, os ilhéus de olhos azuis, vendo ( b - 1, r ), concluirão que eles têm olhos azuis e vão embora.
  • Se a composição da ilha for ( b , r ) e for sabido que os ilhéus de olhos azuis teriam saído no dia n se a composição fosse ( b - 1, r + 1), no dia n + 1, o ilhéus de olhos, vendo ( b - 1, r ), concluirão que têm olhos azuis e vão embora.

Essa segunda inferência falha se b = 1, mas nesse caso, o ilhéu de olhos azuis nunca sairia se já não o tivesse, e o caso de teste seria inválido.

Observe que os ilhéus de olhos azuis nunca sairão nesta versão do quebra-cabeça, porque, mesmo que usem lógica semelhante para concluir que não têm olhos azuis, ainda não sabem qual é a cor não azul de seus olhos. .

Anders Kaseorg
fonte