1028 Linguagens de programação

Trabalho / Resolvedor do jogo Same em Racket

Introdução

O objetivo deste trabalho é a implementação de um resolvedor 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.

Este trabalho vale 5,0 pontos na nota do primeiro bimestre.

Data de entrega: até o dia 18/04/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.

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

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

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

• usar funções com efeito colateral
• criar todos os grupos de uma vez
• criar grupos repetidos

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

```text
git clone http://malbarbo.pro.br/git/resame-racket
```

Após a execução deste comando, um diretório chamado resame-racket 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 18/04/2013. O termo de autoria assinado deve ser entregue pessoalmente ao professor no dia 19/04/2013 no horário da aula.

Avaliação

Este trabalho vale 5,0 pontos na nota do primeiro bimestre. O trabalho será avaliado de acordo com os critérios:

• Clareza lógica: a lógica nos programas deve ser clara.
• Corretude e completude: os programas têm quer passar em todos os testes.
• Boas práticas de programação: o código deve estar bem escrito e organizado; os recursos da linguagem devem ser usados corretamente.

Dicas

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

• Antes de implementar o programa em Racket, resolva as listas de exercícios. Você terá muitas dificuldades em implementar o trabalho se você nunca resolveu alguns problemas em Racket 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.