Tarefa 3: Minotauro

Abril 12, 2010

O professor da disciplina sugeriu que o laboratório 3 de MC202 fizesse uso de recursão. Apesar de ser uma técnica ensinada em MC102, é um conceito que demora a ser aprendido, ao meu ver porque exige maior abstração. Enfim, devido a essa dificuldade tal tópico costuma ser revisto em MC202.

A ideia que tive foi a de um problema de percorrer labirintos. A tarefa foi contextualizada com uma história da mitologia grega em que Teseu procura o Minotauro e para não se perder no caminho de volta utiliza uma corda cedida por Ariadne.

Para não ter que tratar múltiplas soluções, especifiquei uma regra de percurso: primeiro tenta-se ir em frente, se não houver sucesso, tente ir à direita e finalmente à esquerda. O primeiro passo consiste em encontrar a entrada, representada por um buraco na parede mais externa. É garantido que haverá exatamente um buraco. Depois disso, aplicamos a técnica de backtracking seguindo as regras acima até encontrar o Minotauro (representado pela letra ‘M’).

Para especializar um pouco mais o problema, exigi no enunciado que fosse impresso, além do caminho utilizado para chegar da entrada ao Minotauro, o caminho por onde ele passou. Essa informação adicional seria útil no caso em que o Minotauro não fosse encontrado, pois sem imprimir o caminho por onde Teseu passou, o mapa de saída seria igual ao de entrada. Porém, por distração acabei especificando que apenas fosse impressa uma string caso o Minotauro não fosse encontrado. Só percebi o erro que tinha cometido quando fui corrigir o laboratório de um aluno, cujo programa era mais ou menos o seguinte:

#include <stdio.h>
int main (){
    printf("O Minotauro eh lenda.");
}

Ele ia passar em 2 dos 12 testes do SuSy se não tivesse esquecido de pular linha.

Alguns alunos também tentaram detectar a existência do Minotauro pelo mapa de entrada: se o caracter ‘M’ fosse rodeado por paredes (‘X’) então ele não poderia ser encontrado. Essa é uma condição suficiente, mas não necessária (por quê?)

Finalmente, não sei se o enunciado é que ficou confuso demais ou se o conceito ainda não foi absorvido, mas o fato é que a maior parte dos alunos não entendeu que não era preciso voltar explicitamente para trás quando uma das direções não era a certa. Isso porque depois de retornar das chamadas recursivas obtemos esse efeito implicitamente.

Anúncios

Tarefa 2: Bandex

Abril 1, 2010

Terça-feira foi o último dia para a submissão da tarefa 2 da disciplina de estruturas de dados.

O problema consistia em simular uma fila mais complexa, onde as pessoas saem pelo começo mas nem sempre entram no final. As pessoas nesse contexto são os alunos da Unicamp, e cada aluno é de um dado ano (2006 até 2010) e pertence a exatamente um grupo de amigos. A regra para entrar na fila é a seguinte: um aluno de um ano $a$, sempre entra na frente de um aluno do ano $b > a$ e atrás de um aluno do ano $c \le a$. A única exceção é que quando algum amigo do seu grupo está na fila, quando o aluno entra na frente deste amigo.

Uma restrição dada no enunciado garante que dois alunos são do mesmo grupo somente se pertencem ao mesmo ano. Essa é uma simplificação importante, pois desta forma garantimos que pessoas do mesmo grupo estão sempre juntas na fila e a ordenação em relação aos anos é mantida.

Minha ideia para esse problema envolvia estruturas de dados diferentes: vetor, lista ligada, pilha e fila de prioridades. Na raíz de tudo temos uma fila de prioridade onde cada elemento (representando os anos) é uma lista ligada. Cada elemento desta lista é uma pilha (representando os grupos). Além disso, mantemos um vetor indexado pelo identificador do grupo apontando para o lugar onde este grupo está na fila. Como os alunos não tinham aprendido fila de prioridades ainda, dei a dica de implementá-la usando 5 filas, uma para cada ano.

Para inserir um aluno, primeiramente verificamos o ano ao qual ele pertence e vamos inserir na lista correspondente. Agora precisamos inseri-lo na frente do seu grupo. Primeiro verificamos se seu grupo está na fila. Se sim, inserimos ele no topo da pilha correspondente ao grupo. Caso contrário, criamos uma pilha para este grupo e colocamos no final da lista ligada.

Para remover um aluno, consideramos a fila com maior prioridade, no caso 2006. Se ela estiver vazia, verificamos a próxima fila. Caso contrário, removemos o topo da primeira pilha. Se a pilha esvaziar, removemos ela da lista ligada.

A complexidade esperada é O(1) para inserção e para remoção. Porém devido a restrições no SuSy, o sistema de avaliação dos programas, não consegui colocar instâncias muito grandes, de forma que algoritmos com inserção O(n), que consiste em procurar o grupo na lista percorrendo-a elemento a elemento, passavam nos testes.

Porém, deixei um teste grande para rodar localmente no meu computador e bonifiquei com 1 ponto as pessoas que passaram nesse teste.