1225 Linguagens de programação
Edição 2012 - Informática
Trabalho 2 - Resolvedor do jogo Same
O objetivo deste trabalho é a implementação de um resolvedor do jogo Same em Prolog e em uma linguagem imperativa.
O trabalho é em equipe de até duas pessoas. O compartilhamento de informações entre as equipes é permitido (e aconselhado), mas o compartilhamento de código não é permitido. Trabalhos que tenham porções significativas de código iguais, ou copiados da internet, serão anulados. Veja a resolução Nº 008/2007-COU para as possíveis sansões disciplinares. Cada membro da equipe deverá apresentar o trabalho individualmente para o professor.
Este trabalho vale 5,0 pontos na nota do segundo bimestre.
Data de entrega: até o dia 22/08/2012 às 23:00h.
Um jogo Same consiste de um campo retangular inicialmente preenchido com blocos coloridos. O jogador pode selecionar um grupo (clicando em uma posição) para ser removido. Dois blocos estão no mesmo grupo se eles tem a mesma cor e são adjacentes (na vertical ou na horizontal). Após selecionar um grupo, os blocos que estavam acima dos blocos do grupo caem e preenchem os espaços vazios. Quando um coluna fica sem blocos, os blocos a direita são deslocados para a esquerda. Apenas grupos com mais que um bloco podem ser selecionados.
Uma solução para um jogo Same é uma sequência de posições que quando "clicadas" removem todos os blocos.
Este trabalho consiste na implementação de um resolvedor para o jogo Same.
O programa deve receber como parâmetro na linha de comando um arquivo com a especificação do jogo e escrever na saída padrão uma resolução para o jogo, ou sem-solucao, se não existe solução para o jogo. Uma resolução consiste em uma sequência de jogadas (posições) e resultados (campo obtido após a jogada). As jogadas e os resultados devem ser separados por uma linha em branco.
Por exemplo, considere um arquivo com o seguinte conteúdo
No arquivo de entrada, as linhas e as colunas são enumeradas da seguinte forma
2 | 2 1 3 1
1 | 2 2 2 3
0 | 2 3 3 1
Uma possível resolução para este jogo é
Observe que as posições são representadas pelo número da linha seguido pelo número da coluna.
Uma estratégia simples para encontrar uma solução para um jogo Same é:
escolha um grupo qualquer
remova o grupo
se não existir um grupo que possa ser removido, retroceda na jogada anterior e escolha outro grupo
se acabaram as opções de grupos na primeira jogada, então o jogo não tem solução
utilize recursivamente o mesmo processo para resolver o jogo obtido no passo 2
Observe que este é um problema de busca. Este tipo de problema é bastante adequado para ser resolvido com Prolog.
Duas versões deste programa devem ser escritas. Uma na linguagem Prolog e outra em uma linguagem imperativa. O interpretador Prolog utilizado para testar o programa será o SWI-Prolog. Você pode utilizar qualquer uma das linguagens imperativas a seguir, desde que o compilador/interpretador utilizado esteja disponível nos repositórios do Debian ou do Ubuntu.
Linguagens permitidas:
Se você quiser utilizar outra linguagem, converse com o professor a respeito.
Python não faz parte da lista porque o testador foi escrito em Python, e algumas funções necessárias para implementar um resolvedor estão no código do testador. Apesar de não poder escrever o código em Python, você pode basear a sua solução nas funções implementadas no testador.
Para facilitar o desenvolvimento dos programas, está disponível um "projeto" com os arquivos iniciais de código, um programa testador e um Makefile para compilar, testar e enviar os programas.
Para fazer o download do projeto é necessário ter o git instalado. Se você utiliza um sistema GNU/Linux baseado no Debian (Mint, Ubuntu, etc), o git pode ser instalado com o comando
git clone http://malbarbo.pro.br/git/resame
Após a execução deste comando, um diretório chamado resame terá sido criado.
No diretório src/prolog, estão os arquivos com o código Prolog inicial. Você deve escrever o seu código no arquivo src/prolog/same.pl.
O código para a versão do programa na linguagem imperativa deve ficar no diretório src/x, onde x é a linguagem utilizada. Para o seu programa funcionar com o testador, é necessário criar um arquivo src/resolvedor-x. Veja o exemplo src/resolvedor-exemplo.
Para executar os testes, entre no diretório resame e execute um dos comandos
make plunit         # executar os testes de unidade do programa Prolog
make testar-alguns  # testar os resolvedores com alguns casos de teste
make testar-todos   # testar os resolvedores com todos os casos de teste
Após enviar o trabalho, o aluno deverá entrar na página da disciplina, imprimir e assinar o termo de autoria. O termo de autoria é um documento em que o aluno afirma que ele é o autor do código do trabalho que ele enviou e que portanto, não copiou parte significativa do programa de outra pessoa ou da internet.
O trabalho deve ser enviado até as 23:00h do dia 22/08/2012. O termo de autoria assinado deve ser entregue pessoalmente ao professor até o dia 23/08/12 no horário da aula.
Este trabalho vale 5,0 pontos na nota do segundo bimestre. O trabalho será avaliado de acordo com os critérios:
Corretude e completude: os programas têm quer passar em todos os testes.
Esta seção contém algumas dicas de implementação. Use as que achar útil.
Antes de implementar o programa em Prolog, resolva alguns problemas da seção 1 e 2 da lista de 99 problemas em Prolog. Você terá muitas dificuldades em implementar o trabalho em Prolog se você nunca resolveu algum problema em Prolog antes.
Veja a implementação do testador no arquivo testador/same.py. Algumas operações necessárias para construir um resolvedor estão implementadas no testador.