malbarbo.pro.br

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

Edição 2013/2 - Informática

Trabalho / Resolvedor do jogo Same em Racket

Introdução

O objetivo deste trabalho é a implementação de resolvedores do jogo Same em Racket.

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.

Data de entrega: até o dia 05/05/2013 à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. 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 dois resolvedores para o jogo Same em Racket. Um resolvedor chamado “basic” e outro chamado “fast”. Veja no final desta seção as características que estes resolvedores devem ter.

O programa deve receber como parâmetro na linha de comando o nome do resolvedor e o nome do 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

Características dos resolvedores

Para exercitar os conceitos do paradigma funcional, só é permitido usar funções com efeito colateral para as operações de entrada e saída, o restante do programa deve ser puramente funcional. Alguns funções com efeito colateral em Racket tem o nome terminado com !. Estas funções não podem ser utilizadas.

Um grupo deve ser criado apenas quando necessário, o seu programa não deve criar todos os grupos de uma só vez. Para seguir esta restrição, você deve criar um stream de grupos. Além disso, o seu programa não deve criar grupos repetidos, isto é, grupos que já tenham sido criados e processados.

O resolvedor “basic” deve representar o jogo como uma lista de listas.

O resolvedor “fast” deve representar o jogo como um vetor de vetores.

Para ambas as representações, a primeira dimensão refere-se a coluna e a segunda dimensão a linha. Esta inversão facilita a implementação das funções. Além disso, os testes de unidade esperam as representações dessa forma.

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

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

Você deve escrever o código do programa no arquivo src/racket/resame.rkt, que contém código inicial para fazer a leitura do jogo.

Execução dos testes

Para executar os testes unitários, abra o arquivo src/racket/resame-tests.rkt no DrRacket e clique no botão Correr (ou Crtl-R).

Para executar os testes funcionais, entre no diretório resame-racket e execute um dos comandos

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 05/05/2013. O termo de autoria assinado deve ser entregue pessoalmente ao professor no dia 06/05/2013 no horário da aula.

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.