Eu só consegui encontrar desafios de código-golfe para o Mastermind, então aqui está uma versão de código-desafio que eu gostaria de enfrentar.
Uma estratégia ideal para o jogo Mastermind normal, MM (4,6), foi encontrada por Koyama e Lai em 1993, com um número médio de suposições = 5625/1296 ~ 4,34. MM (5,8) ainda não foi resolvido, mas estima-se que tenha um número médio de suposições ~ 5,5.
Sua tarefa é criar uma estratégia MM (5,8), com 5 furos e 8 cores, cobrindo todas pow(8,5) = 32768
as soluções distintas possíveis. Obviamente, não precisa ser o ideal. Você tem duas opções:
- Poste um programa determinístico que gere a estratégia. O programa deve ser compilável / executável no Windows 7, Mac OS X ou Linux sem nenhum software extra gratuito.
- Publique sua estratégia (junto com o seu nome StackExchange) em algum lugar da Internet e publique o URL aqui.
Nos dois casos, indique a pontuação (veja abaixo) no cabeçalho da resposta.
A estratégia deve ser codificada de acordo com a seguinte gramática:
strategy : guessing-strategy | known-solution-strategy
guessing-strategy : '{' guess ':' branches '}'
known-solution-strategy : guess
guess : color color color color color
color : 'A'..'H'
branches : '{' branch (',' branch)* '}'
branch : reply ':' strategy
reply : number-of-blacks number-of-whites
number-of-blacks : number-of-key-pegs
number-of-whites : number-of-key-pegs
number-of-key-pegs : '0'..'5'
O algoritmo usado para decidir o número de pinos de teclas preto / branco está descrito em http://en.wikipedia.org/wiki/Mastermind_(board_game)
Observe que a resposta "50" (ou seja, palpite correto) está implícita e não faz parte da gramática.
Pontuação: N = a soma do número de suposições para cada um dos 32768 caminhos / soluções. A estratégia com o N mais baixo ganha. Primeiro tie-break: o menor número máximo de palpites. Segundo tie-break: a primeira resposta postada. A competição termina em 1 de agosto de 2014 às 0:00 GMT .
Um exemplo de estratégia para MM (2,3) com pontuação = 21:
{AB:{10:{AC:{10:AA,01:CB,00:BB}},02:BA,01:{BC:{01:CA}},00:CC}}
Usando esta estratégia, os 9 jogos possíveis serão assim:
- AB 20
- AB 10, CA 20
- AB 10, CA 10, AA 20
- AB 10, CA 01, CB 20
- AB 10, CA 00, BB 20
- AB 02, BA 20
- AB 01, BC 20
- AB 01, BC 01, CA 20
- AB 00, CC 20
Em breve, publicarei um verificador de estratégia MM (5,8) baseado em Java para sua conveniência.
fonte
{AB:{10|01:BB}}
? Eu tenho uma resposta, mas é bastante ingênua e, devido à estrutura em árvore da gramática, ela não escala muito bem (4 furos, 3 cores, gera uma estratégia de 147 MB, que eu poderia reduzir significativamente combinando partes de a árvore).Respostas:
Java
Meu algoritmo para MM (5,8) pontua com
177902178006182798182697 com uma profundidade máxima de89 e precisa de apenas alguns segundos (no meu computador lento).Um exemplo de saída de uma estratégia para MM (2,3) com score = 21 encontrada por esse algoritmo é semelhante a:
Não há nada empolgante com meu algoritmo. Nenhuma invenção. Eu apenas segui as receitas encontradas na rede e as comprimi neste código Java. A única otimização que fiz foi tentar otimizar as linhas de código (de certa forma). É assim:
@ MrBackend: Escrever um verificador é difícil, eu acho. ;-)
Algumas observações:
A estratégia para
MM(5,8)
pode ser encontrada aqui . O GitHub tem alguns problemas ao exibir linhas que demoram tanto, então clique no botão Raw .fonte
Rubi
Edição: Adicionado alguma lógica para excluir suposições impossíveis. Portanto, as estratégias agora estão em conformidade com o formato fornecido e são muito mais gerenciáveis.
Então, aqui está uma tentativa de fazer isso acontecer. É bastante ingênuo (e não muito legível - ajuda a ler o ramo if / elsif / else de baixo para cima).
Primeiro, eu tento 5 de cada cor:
AAAAA
,BBBBB
, etc. A partir desse figura I quais cores são realmente utilizados no padrão. E então simplesmente tento todas as permutações das cores fornecidas, omitindo aquelas que já foram descartadas pelos pinos pretos.Aqui está a
MM(2,3)
estratégia:A estratégia para
MM(5,8)
376KB pode ser encontrada aqui . O GitHub tem alguns problemas ao exibir linhas que demoram tanto, então clique no botão Raw .Agora, se eu receber um verificador, também posso lhe dizer qual é minha pontuação real. :)
fonte