Algoritmos e Estrutura de Dados I - AE22CP - 2012/2

TRABALHO PRÁTICO 2

Bruno César Ribas e Willian Zalewski

• Resultado final do RANK
• Prólogo
• A planta da construção
  • Formato do arquivo da planta
  • Carl e Rick
  • Zumbis
  • Armamento
  • "Libertando" Zumbis
  • Uso do armamento
• Comandos
• Saída
• Execução
• Exemplos de Entrada e Saída
• Ranking
• Prazos
• Critérios da Correção

---

Resultado final do RANK

• 15/04/2013

A etapa final do RANK foi executada no dia 14 de abril de 2013, e foi executada contra os trabalhos que resolveram todos os mapas que estavam disponíveis no RANK, informações das rodadas anteriores estão AQUI.

Segue abaixo a roda final onde os 3 melhores trabalhos ganharam 10 pontos extras no trabalho.

Nome	Tempo	Passos	Trocas	Disparos	Score	Pto Extra
LAEL SANTOS	179.27	1027	0	24995	26022	10
GABRIEL SOUSA e MURIEL MAZZETTO	52.54	1013	10402	24397	46214	10
ANDRE MARASCA e CALLEBE BARBOSA	309.30	1005	1242	42852	46341	10
DIONEI MICHEM	37.79	989	11443	59358	83233	- -
VAGNER SANTOS e EKUIKUI ROSA	60.76	989	13461	58790	86701	- -
DOUGLAS MARCAL e JOAO DLUGOSZ	22.35	989	1797150	127019	3722308	- -
ANA MOSER	29.73	989	2030457	153367	4215270	- -

---

Prólogo

Rick Grimes está curado e muito agradecido pela sua ajuda em tempos passados. Rick apenas se queixa de fadiga em alguns momentos, ele disse que se sentiu andando em círculos.

Dessa vez, nosso herói, está com um novo problema e podemos dizer que ele é bem mais delicado que o que tem enfrentado nos últimos tempos.

Carl foi fazer uma patrulha escondido e acabou ficando cercado por zumbis. O maior problema é que Carl não tem como sair desse cerco sem a ajuda de alguém, e como Carl é filho de Rick ele já foi correndo tentando salvar seu filho.

O ambiente em que Carl está preso já é razoavelmente familiar para Rick, porém ele não sabe onde estão os zumbis e a quantidade de Arma e munição que consegue carregar é bastante limitada. Alguém precisa ajudar Rick a escolher o melhor conjunto de armas para conseguir chegar ao Carl sem precisar voltar diversas vezes.

A única pessoa que pode ajudar Rick é Você!

No atual momento você colocou sonares e consegue identificar as posições em que os zumbis estão, além de já possuir os arquivos com as plantas dos possiveis lugares em que Carl se encontra.

A planta da construção

A planta da construção é bem simples. Ela possui o caractere '#' indicando que o local é uma parede e '.' indicando que é um caminho livre.

Formato do arquivo da planta

A planta da construção é um arquivo de texto onde a primeira linha possui 2 números inteiros L e C indicando, respectivamente, quantas linhas e colunas existe na planta.

Não sabemos os limites de L e C! Fique preparado para aceitar qualquer valor.

Depois existirão L linhas com C colunas onde cada posição podemos ter algum desses caracteres:

• '.' caminho livre
• '#' parede, você não pode passar
  Exemplo de um mapa:

    5 30
    ##############################
    #.#...#########.##############
    #.#.#.#########.##############
    #...#........................#
    ##############################
  

Carl e Rick

Após o mapa será passado a você onde no mapa Rick e Carl estão, indicando a Linha e Coluna do Rick e depois a Linha e Coluna do Carl, como no exemplo abaixo:

  5 30
  ##############################
  #.#...#########.##############
  #.#.#.#########.##############
  #...#........................#
  ##############################
  2 2
  4 28

Então Rick está na posição 2 2 e Carl 4 28, que são indicados como R e C abaixo:

  ##############################
  #R#...#########.##############
  #.#.#.#########.##############
  #...#......................C.#
  ##############################

Zumbis

Após indicar a posição de Rick e Carl será indicado quantos Zumbis tem no mapa e onde cada Zumbi está e uma lista (de tamanho arbitrário) com as fraquezas dos Zumbis.

A lista de fraquezas é um conjunto de informações que relaciona os nomes das fraquezas e o impacto que cada fraqueza causa no zumbi.

A linha que define o Zumbi é rigorosamente definida como:

• Posição do Zumbi, definida por Linha e Coluna
• Lista de fraquezas no formato: [ fraqueza1: impacto, Fraqueza2: impacto, ... ]
  • Note que a lista inicia por [ e termina com ]
  • SEMPRE existe um espaço depois de [ e antes de ]
  • O : SEMPRE é grudado no nome da fraqueza
  • SEMPRE existe um espaço depois do :
  • O impacto é um número inteiro
  • Exceto o último impacto todos possuem uma vírgula grudada no valor do impacto

Exemplo de alguns Zumbis:

  5 30
  ##############################
  #.#...#########.##############
  #.#.#.#########.##############
  #...#........................#
  ##############################
  2 2
  4 28
  2
  2 5 [ shotgun: 10, faca: 3, soco: 1 ]
  4 10 [ pistola: 5, grito: 1, lanca-chamas: 20 ]

Então a representação do mapa seria assim:

  ##############################
  #R#.Z.#########.##############
  #.#.#.#########.##############
  #...#....Z.................C.#
  ##############################

Ou artisticamente:

Armamento

Para conseguir chegar até o Carl, Rick, potencialmente, deverá matar alguns zumbis.

Para matar os zumbis você receberá uma lista, de tamanho arbitrário, de armas que poderá utilizar durante sua jornada de resgate.

A lista é definida por:

• Lista de armas no formato: [ arma1: força, arma2: força, ... ]
  • Note que a lista inicia por [ e termina com ]
  • SEMPRE existe um espaço depois de [ e antes de ]
  • O : SEMPRE é grudado no nome da arma
  • SEMPRE existe um espaço depois do :
  • O impacto é um número inteiro
  • Exceto a última força todos possuem uma vírgula grudada no valor da força

Exemplo de uma entrada completa:

  5 30
  ##############################
  #.#...#########.##############
  #.#.#.#########.##############
  #...#........................#
  ##############################
  2 2
  4 28
  2
  2 5 [ shotgun: 10, faca: 3, soco: 1 ]
  4 10 [ pistola: 5, grito: 1, lanca-chamas: 20 ]
  [ pistola: 5, grito: 1, shotgun: 15, beretta: 10, ar-15: 7, soco: 1, fal: 15, lanca-chamas: 30, faca: 2, arpao: 10 ]

"Libertando" Zumbis

Todo zumbi possui uma energia de 1000 pontos e para matá-lo é necessário utilizar arma que confira com alguma fraqueza e você deverá disparar no zumbi até que ele perca 1000 pontos.

Cada disparo faz o zumbi perder pontos de energia que é definido abaixo:

  (impacto * força)

Então para matar o primeiro zumbi do exemplo anterior com a shotgun devemos utilizar 7 tiros da shotgun pois:

  7* ( 10 * 15 ) = 1050

A quantidade de disparos deve ser um número inteiro!

Uso do armamento

• atualizado 28/03
  Carregar muitas armas é bastante difícil, são diversas bandoleiras e fazer a troca sempre é algo complicado. Por isso você usará as suas armas como uma fila.
  No inicio da rodada você deve definir em que ordem as armas se encontram, e você começará com a primeira dessa fila. Sempre que precisar efetuar uma troca de arma você deverá imprimir na saída padrão a palavra troca, que significa que você pegará a próxima arma da fila, você pode trocar de armas quantas vezes for necessário.
  Antes de começar qualquer movimentação você deve imprimir a ordem da fila, no mesmo formato da entrada, um exemplo de uma fila é:

    [ lanca-chamas: 30, pistola: 5,  shotgun: 15, faca: 2 ]
  

  Importante notar que a fila de armas que você levará para as batalhas pode conter menos armas que você recebeu na entrada.
  Lembre-se de que você deverá colocar pelo menos 1 arma em sua fila, mesmo que você não vá usar nenhuma arma.

Comandos

O seu objetivo é levar o Rick até Carl e para isso você pode mandar os seguintes comandos:

• 'baixo' - manda o Rick descer 1 posição, como na animação abaixo;
• 'cima' - manda o Rick subir 1 posição, como na animação abaixo;
• 'direita' - manda o Rick andar 1 posição para direita, como na animação abaixo;
• 'esquerda' - manda o Rick andar 1 posição para a esquerda, como na animação abaixo;
• 'troca' - manda o Rick trocar de arma, escolhendo então, a próxima arma da fila definida no início;
• 'descarta' - manda o Rick jogar a arma em punho fora, removendo-a da fila e nunca mais podendo ser utilizada e passando a segurar a próxima arma na fila;
• 'dispara X direção' - manda Rick disparar a arma em punho X vezes, X é um número inteiro;

Saída

• atualizado 22/03 - Exemplo de entrada estava com espaço antes das virgulas

O seu programa deverá gerar uma saída que contenha os comandos que o Rick deverá seguir para sair da construção, onde cada linha deve ter um comando.

Para o exemplo abaixo:

  5 30
  ##############################
  #.#...#########.##############
  #.#.#.#########.##############
  #...#........................#
  ##############################
  2 2
  4 28
  2
  2 5 [ shotgun: 10, faca: 3, soco: 1 ]
  4 10 [ pistola: 5, grito: 1, lanca-chamas: 20 ]
  [ pistola: 5, grito: 1, shotgun: 15, beretta: 10, ar-15: 7, soco: 1, fal: 15, lanca-chamas: 30, faca: 2, arpao: 10 ]

Uma possível solução é:

  [ lanca-chamas: 30, pistola: 5,  shotgun: 15, faca: 2 ]
  baixo
  baixo
  direita
  direita
  cima
  cima
  troca
  troca
  dispara 7 direita
  direita
  direita
  baixo
  baixo
  direita
  direita
  direita
  troca
  troca
  troca
  dispara 40 direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita
  direita

Veja a animação da solução acima clicando na imagem abaixo:

Execução

A entrada e saída do programa devem ser feitas pela entrada e saída padrão ( como se estivesse lendo as informações pelo teclado e imprimindo na tela)

exemplo de execução:

  time ./meuprograma < mapa.txt  > solucao.txt

Onde "meuprograma" é o nome do executável do trabalho (pode ser outro nome qualquer), e "mapa.txt" é o arquivo que contém o mapa do local em que o Rick está. O arquivo "solucao" é o arquivo que armazenará a saída do seu programa.

Quando executar o seu programa da forma indicada abaixo , o sinal '<' significa que o conteúdo do 'mapa.txt' será passado ao programa como se ele estivesse sendo lido do teclado. E o sinal '>' significa que tudo que o seu programa imprimir na saída padrão será salvo em 'solucao.txt'. E 'time' é comando que contará o tempo de execução do seu programa.

Exemplos de Entrada e Saída

• atualizado 22/03 - 1 exemplo adicionado

• mapa2.txt / Possível Solução

Não se limite a esses exemplos, crie seus próprios exemplos!

Ranking

• atualizado 27/03 - modificada ordem de desempate
• atualizado 24/03

O ranking será feito por disputas diárias. Para participar basta enviar o código que o sistema copilará e executará.

Para participar do Ranking o seu código deve funcionar em LINUX, recomendamos o uso do Ubuntu. Se o sistema não conseguir compilar seu programa apenas será avisado que não conseguiu e nada mais.

• A tabela de execuções pode ser vista em: AQUI

No Rank a ordenação será considerada pelo SCORE, definido como:

  Passos + 2 * Trocas + Disparos

• Score menor é considerado como melhor

Em caso de empate no Score serão considerados os seguintes critérios:

• Quantidade de trocas
• Quantidade de tiros
• Quantidade de passos
• Tempo de Execução

Prazos

• atualizado 07/04
• atualizado 01/04

• Prazo de entrega: Dia 05 de Abril de 2013 Dia 7 de Abril Dia 10 de Abril
  • O sistema de submissão será encerrado às 23h50.

Critérios da Correção

• O trabalho vale 100 pontos
• Se for necessário efetuar alguma ordenação, NÃO utilizar o método Bolha
• Os trabalhos serão executados contra todos os mapas publicados no rank.
  • Se o programa falhar em qualquer mapa terá um desconto de 20 pontos, e desconto adicional de 5 pontos por cada mapa que falhar.
    • Se falhar em apenas 1 mapa terá um desconto de 20pontos, se falhar em 2 mapas o desconto será de 25pontos, em 3 mapas desconto de 30pontos, e assim por diante.
  • Se o programa falhar em 50% ou mais dos mapas, terá nota automaticamente em 0.
• Os programas que não falharem em nenhum mapa entrarão na rodada especial para ponto extra
  • Na rodada especial será executado um novo mapa
  • Se o programa falhar na rodada especial terá um desconto de 10 pontos
  • Os 3 melhores programas receberão 10 pontos extras.

• Além da rodada automática os trabalhos passarão pelas seguintes avaliações:
  • Será considerado o código:
    • Otimização
    • Limpeza do código
    • Criatividade
  • Defesa individual do código quando a T2 - P2 >= 4

---
Last Modified: Mon Apr 15 09:35:33 2013.