Projeto 2012.2

Para cada tentativa o jogador recebe uma resposta através dos pinos de chave. Basicamente uma de três informações diferentes lhe são passadas a respeito de cada um dos seus pinos de código.

        a) O pino não faz parte da senha, e neste caso uma casa vazia é mostrada no espaço dos pinos de chave.

        b) O pino faz parte da senha, mas está numa posição incorreta, e neste caso um pino de chave branco é colocado em algum furo.

        c) O pino compõe a senha e está posicionado no seu local correto, e assim um pino de chave preto vai surgir como resposta.

Note que não há qualquer relação entre as posições ocupadas pelos pino de chave e de código. Tipicamente se reservam os primeiros furos para possíveis pinos pretos, e em seguida os pinos brancos e finalmente os furos que restam vazios.

O Projeto.

Basicamente temos um alfabeto, composto de uma sequência de diferentes caracteres ASCII, que representarão os pinos de código. Ao invés de cores, caracteres. Além disso, o tamanho do quebra-cabeças também é variado (no jogo de tabuleiro são sempre quatro pinos de código).

O sistema já está pronto, e pode ser baixado aqui. Ocorre que, infelizmente, ele implementa um agente resolvedor que executa testes aleatórios, embora não repetitivos, até que encontra uma solução. Não parece ser a escolha mais adequada.

O seu trabalho é implementar uma estratégia mais inteligente, que naturalmente resolva o problema com menos tentativas. Idealmente é interessante que sua solução funcione para qualquer alfabeto, e qualquer tamanho de quebra-cabeças. Mas inicialmente é satisfatório trabalhar com o alfabeto dos algarismos decimais (0 a 9) e senhas de tamanho igual a 5.

Detalhes do sistema.

O sistema, que segue com testes de unidade, pode ser baixado aqui.

Para executá-lo é necessário configurar um arquivo com os parâmetros de operação. Estes parâmetros são três: ALPHABET, que é uma String com os diferentes caracteres que representarão os pinos de código, PUZZLESIZE, que é o tamanho do quebra-cabeças, ou seja, de quantos caracteres do alfabeto será composta a senha e SOLVER_TYPE, que indica o tipo de resolvedor que será instanciado para que se resolva o problema. Junto com o sistema já está disponível o resolvedor aleatório descrito acima, e ele será instanciado caso a opção para este parâmetro seja RANDOM.

Junto com o sistema segue um arquivo de parâmetros para exemplo.

Para executar é necessário se invocar a classe de fachada. Basicamente isso pode ser feito usando o comando (execute-o a partir do diretório bin).

java facade.Facade <arquivo_de_parametros> <número de execuções>

Invocado assim, o sistema irá gerar um jogo a partir dos parâmetros definidos em <arquivo_de_parametros> e instanciará um resolvedor (também definido em <arquivo_de_parametros>) que resolverá o problema um certo número repetido de vezes (definido em <número de execuções>). Estas múltiplas execuções permitirão aproximar mais os resultados de médias comparativas a fim de aferir o desempenho de diferentes métodos de resolução do problema.

Informações críticas.

Dentro da classe MasterMind há um método instanciateSolver, que permite facilmente a criação de diferentes objetos para resolver o problema. Uma nova opção no arquivo de parâmetros, um novo teste e um novo objeto criado e... voilà!

Cada objeto que vai resolver o problema deve implementar a interface Solver (padrão de projeto Strategy), e portanto o método public int solve(), que recebe um conjunto de caracteres (os que compõem o alfabeto), o tamanho do quebra-cabeças e um objeto do tipo Answer.

Cada jogo (Instância da classe MasterMind) possui um objeto do tipo Answer que armazena a senha secreta que deve ser descoberta. Este objeto pode ser “consultado”: o método answer.analyze() recebe uma String e a compara com a solução do problema, retornando outra String com uma sequencia de letras “b” (de Black), “w” (de White) ou “o”. Esta String representa a resposta dos pinos de chave: furo com pino preto (“b”), com pino branco (“w”), ou vazio (“o”).

Um objeto do tipo Answer também responde se uma dada String é a solução correta (método correct()).

Avaliação.

Você deverá implementar seu resolvedor de acordo com as especificações acima. Idealmente seu resolvedor deverá funcionar para qualquer alfabeto e qualquer tamanho de quebra-cabeças válido. Mas inicialmente pode-se trabalhar com o alfabeto “0123456789” e desvendar senhas de tamanho igual a 5.

Cada consulta feita (answer.analyze()) a fim de encontrar a sequência correta deve ser contada, e o desempenho de um método será melhor quanto menos consultas ele fizer para resolver o problema.

Você deve preparar um experimento para mostrar que seu método é melhor do que o RandomSolver que segue implementado junto com o projeto.

Você deve redigir um pequeno artigo descrevendo seu método, o experimento que foi realizado, e os resultados obtidos. Faça considerações a respeito de uma comparação entre seu método e o RandomSolver. Faça considerações a respeito dos resultados: porque melhorou? Porque não melhorou mais (se for o caso)? Que alternativas poderiam (se for o caso) ser tentadas para melhorar ainda mais seus resultados? Porque?

Boa Sorte!