malbarbo.pro.br

1225 Linguagens de programação

Edição 2012 - Informática

Trabalho 2 - Resolvedor do jogo Same

Introdução

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.

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.

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.

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.

Uma estratégia simples para encontrar uma solução para um jogo Same é:

  1. escolha um grupo qualquer
  2. remova o grupo
  3. se não existir um grupo que possa ser removido, retroceda na jogada anterior e escolha outro grupo
  4. se acabaram as opções de grupos na primeira jogada, então o jogo não tem solução
  5. 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.

Linguagens

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.

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 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

sudo apt-get install git

Para fazer o download do projeto, execute 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.

Execução dos testes

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

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

Avaliação

Este trabalho vale 5,0 pontos na nota do segundo bimestre. 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.

Segue alguns links.

Jogo Same

Prolog

Git