Ajuda na programação, respostas a perguntas / Algoritmo / Como analisar um jogo do tipo mentor usando inferências lógicas - algoritmo, conjunto, lógica

Como analisar um jogo tipo-mestre usando inferências lógicas - algoritmo, conjunto, lógica

ISENÇÃO DE RESPONSABILIDADE: Eu não estou procurando uma solução para o Mastermind.

Eu estou tentando escrever um programa para resolver um jogo como o mentor, e estou um pouco preso. Eu não quero uma solução completa, apenas ajuda com a parte que eu não posso passar. Aqui está o jogo:

tem N cores possíveis conhecidas antecipadamente. Existe um conjunto desconhecido (possivelmente com repetições) de k que são escolhidos e mantidos em segredo. O objetivo é adivinhar as cores (com repetições) no conjunto secreto. Deixe-me enfatizar novamente que este é um conjunto, então ordem não importa, mas as repetições são permitidas. Por exemplo

Cores são a,b,c,d,e,f,g,h (N=8) e conjunto desconhecido é {a,c,c} (k=3).

São feitas suposições sucessivas que resultam em mais informações sobre o conjunto secreto. Cada palpite deve ser um set (repetições permitidas) de k cores. A resposta para cada palpite é o número de cores em comum entre o palpite e as repetições de contagem do conjunto desconhecido. Por exemplo

Acho: a,d,e Resultado: 1

Acho: b,c,f Resultado: 1

Acho: a,a,g Resultado: 1

Acho: a,c,h Resultado: 2

Acho: b,e,h Resultado: 0

As suposições são feitas por outra pessoa. Meus objetivos são:

- Determine quando as informações sobre uma determinada cor são conhecidas.

- Determine quando o conjunto desconhecido pode ser deduzido logicamente.

No início do jogo, nenhuma cor está definitivamente no set ou definitivamente não está no set desconhecido (assumindo N>1). Depois de um palpite que resulta em 0, todas as cores desse palpite são conhecidas por não estarem no conjunto desconhecido. Se o resultado for k, então todas as cores desse palpite são conhecidasestar no conjunto desconhecido. Estou tendo problemas para escrever um programa para descobrir todos os casos intermediários. Por exemplo, nada é conhecido sobre qualquer uma das cores até o último palpite acima. Após o último palpite, o conjunto é conhecido por ser a,c,c. A lógica é esta:

Por 5, b,e,h não estão no conjunto desconhecido
Por 4, a,c estão no set desconhecido
Por 1, d não está no conjunto desconhecido
Por 2, f não está no conjunto desconhecido
Por 3, g não está no conjunto desconhecido
Portanto, as únicas cores no conjunto desconhecido são a e c.
Por 3, a não está no set desconhecido mais de uma vez.
Portanto, o conjunto desconhecido é a,c,c.

Eu posso trabalhar com a lógica dessa maneira, mas eu não tenho certeza de como programar isso em geral. Se alguém pudesse sugerir uma maneira estruturada de fazer isso, seria ótimo. Eu preferiria uma explicação de alto nível, com pseudocódigo, em vez de uma implementação completa em qualquer idioma. Obrigado.

Respostas:

1 para resposta № 1

Abordagem direta: Construa a população total de combinações possíveis. Então, conforme os palpites surgirem, remova as combinações que não podem satisfazer o resultado do palpite atual. Uma vez que você tenha apenas uma combinação, essa é a solução. Ou, no início do processo, quando você não tem mais uma determinada cor representada, então ela é (obviamente) eliminada do código secreto possível.

1 para resposta № 2

Você pode codificar a lógica após cada palpite da seguinte maneira. Tome uma matriz de comprimento N, onde a entrada de posição i é +1 se o ia cor está no set, -1 se o ia cor não está no conjunto e 0 se não se sabe se o ia cor está no conjunto.

Após cada palpite, você cria possíveis matrizes que satisfazem o resultado. Se um palpite tiver resultado rentão haverá (k choose r) (ou menos, se houver cores repetidas) possíveis matrizes. Para o seu exemplo, as matrizes são (aqui eu usei + ao invés de +1 e - ao invés de -1 por brevidade)

(+,0,0,-,-,0,0,0) | (-,0,0,+,-,0,0,0) | (-,0,0,-,+,0,0,0)
(0,+,-,0,0,-,0,0) | (0,-,+,0,0,-,0,0) | (0,-,-,0,0,+,0,0)
(+,0,0,0,0,0,-,0) | (-,0,0,0,0,0,+,0)
(+,0,+,0,0,0,0,-) | (+,0,-,0,0,0,0,+) | (-,0,+,0,0,0,0,+)
(0,-,0,0,-,0,0,-)

Agora você pode verificar a consistência entre ospossibilidades conforme a informação entra. Existem 3 possibilidades após o primeiro palpite, cada uma igualmente válida. Após o segundo palpite, existem 9 possibilidades (1 do primeiro 3 e 1 do segundo 3) e cada uma é válida. Após o terceiro palpite, existem 18 possibilidades, das quais apenas 9 são válidas. Isso ocorre porque a opção à esquerda de 3 exige a opção esquerda de 1 e vice-versa. Após o quarto palpite, existem 5 possibilidades válidas. Após o quinto palpite, existe apenas uma possibilidade válida, a saber: