malbarbo.pro.br

6902 Paradigma de Programação Lógico e Funcional

Edição 2013/2 - Ciência da Computação

Trabalho / Resolvedor do jogo Same em Prolog

Introdução

O objetivo deste trabalho é a implementação de um resolvedor do jogo Same em Prolog.

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.

Descrição

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. A figura a seguir mostrar a seleção e remoção de um grupo.

Exemplo do jogo Same

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 em Prolog. Veja no final desta seção as características que o resolvedor deve ter.

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

2 1 3 1
2 2 2 3
2 3 3 1

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
--+--------
  | 0 1 2 3

Uma possível resolução para este jogo é

0 0

0 0 1 0
1 3 3 0
3 3 1 0

1 2

0 0 0 0
0 1 0 0
1 1 0 0

1 1

0 0 0 0
0 0 0 0
0 0 0 0

Observe que as posições são representadas pelo número da linha seguido pelo número da coluna.

Características do resolvedor

Um grupo deve ser criado apenas quando necessário, o seu programa não deve criar todos os grupos de uma só vez. Isto deve ser feito criado um predicado não determinístico, que gera grupo diferente a cada fez que é satisfeito. Além disso, o seu programa não deve criar grupos repetidos, isto é, grupos que já tenham sido criados e processados.

Resumindo as restrições, o seu programa não pode:

Desenvolvimento

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 o programa.

Para fazer o download do projeto é necessário ter o git instalado. No Ubuntu ou Debian o git pode ser instalado com o comando apt-get install git.

Para fazer o download do projeto, execute o comando

git clone http://malbarbo.pro.br/git/resame-prolog

Após a execução deste comando, um diretório chamado resame-prolog terá sido criado.

Você deve escrever o código do programa no arquivo src/prolog/resame.pl. O arquivo src/prolog/resame_utils.pl contém alguns predicados que podem ser úteis.

Execução dos testes

Os testes unitários estão no arquivo src/prolog/resame_tests.pl. Para executar os testes unitários, execute o comando

make plunit

Para executar os testes funcionais, execute um dos comandos

make testar-pequenos  # testar o resolvedor com algumas instâncias pequenas
make testar-medios    # testar o resolvedor com algumas instâncias médias
make testar-grandes   # testar o resolvedor com algumas instâncias grandes

Envio do trabalho

Para enviar o trabalho, execute o comando

make enviar

O script de envio criará um arquivo compactado com os arquivos a serem entregues para correção e enviará para a página do professor.

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 25/11/2013. O termo de autoria assinado deve ser entregue pessoalmente ao professor no dia 26/11/2013.

Avaliação

O trabalho será avaliado de acordo com os critérios:

Dicas

Esta seção contém algumas dicas de implementação. Use as que achar útil.