Universidade do Minho

Mestrado Integrado em Engenharia Biomédica

Introdução aos algoritmos e à Programação
Enunciado do Trabalho de Grupo
Ano letivo 2019/2020
Enunciado do Trabalho de Grupo

Objetivos
O presente trabalho tem como objetivo avaliar os conhecimentos adquiridos nas
aulas da unidade curricular de “Introdução aos algoritmos e à Programação”,
nomeadamente no que diz respeito à análise de problemas, elaboração de algoritmos e
programação de computadores.
Em termos práticos, o trabalho envolverá a utilização das seguintes ferramentas:
 Ambiente de desenvolvimento integrado (e.g. Spyder) e linguagem de programação
Python para a codificação;
 Editor de texto para escrita do relatório.

A resolução dos problemas deve desenrolar-se segundo as seguintes fases:

 Especificação do problema;
 Planeamento das soluções;
 Codificação;
 Verificação;
 Escrita de um breve, mas completo, relatório que não deverá exceder 5 páginas de
tamanho A4 com a descrição do trabalho efetuado.

Problema
Pretende-se o desenvolvimento de uma aplicação, em Python, para jogar uma versão
adaptada da conhecida Batalha Naval.
 A Batalha Naval é um jogo desenhado para dois jogadores num tabuleiro quadrado. A
linhas estão organizadas por letras de A a J e as colunas por números de 1 a 10. Em termos de
regras, cada jogador começa por posicionar a sua frota de barcos, esperando que o adversário
adivinhe as suas posições no tabuleiro. A frota é composta por 8 barcos:
 3 submarinos (barcos de uma casa);
 2 rebocadores (barcos de duas casas seguidas);
 1 contratorpedeiro (barco de três casas seguidas);
 1 cruzador (barco de quatro casas seguidas); e
 1 porta-aviões (barco com uma configuração em ‘T’ de cinco casas seguidas).

Entende-se por “casa” uma quadrícula/posição do tabuleiro e os barcos podem ser

posicionados na horizontal ou na vertical; nunca sobrepostos nem noutra configuração,
distanciando sempre no mínimo uma casa de outro barco.
Na versão a ser desenvolvida neste “trabalho de grupo”, o jogador jogará tentando acertar
nos barcos dispostos em tabuleiros predefinidos, sendo o seu objetivo afundar todos os barcos no
menor número de jogadas possíveis. Neste caso, temos então um só jogador que deve descobrir
onde estão todos os barcos mediante dois tipos de informação:
 Sabendo o que está em certas posições da grelha: água ou segmentos de barcos;
 Sabendo o número de segmentos de barcos em cada linha e em cada coluna.
O jogo termina quando um dos jogadores “afunda” todos os barcos do adversário ou
indica que uma casa está vazia (água) quando na realidade a coordenada atinge um segmento de
barco.
Para a interface de utilizador devem criar um interpretador de comandos (Shell) com
comandos que implementem as funcionalidades pretendidas. Serão disponibilizados os módulos
Python com as classes necessárias à implementação do interpretador de comandos.
Para facilitar a visualização do estado de um tabuleiro será fornecida também uma classe
baseada numa biblioteca gráfica desenvolvida especificamente para o efeito. Embora o seu uso
não seja obrigatório, este deverá facilitar de forma significativa o processo de desenvolvimento,
nomeadamente na fase de validação. O código encontra-se devidamente comentado. A janela em
que o tabuleiro é desenhado fica bloqueada até que ocorra um clique de rato.
Tarefas
Pretende-se com este trabalho criar um programa em Python que permita a um utilizador
tentar adivinhar a posição de todos os barcos de um tabuleiro existente. Tal como na versão
original, o jogo termina quando o utilizador “acertar” em todos os barcos do tabuleiro no mínimo
de jogadas possíveis. É necessário verificar que as regras de jogo são cumpridas ao longo dos
movimentos executados pelo utilizador. Adicionalmente, deve ser possível pedir ao sistema para
validar movimentos e/ou dar sugestões do movimento seguinte.
O programa deve implementar, no mínimo, as seguintes funcionalidades:
 Leitura de um tabuleiro por jogar, em ficheiro;
 Permitir jogar;
 Gravar o estado atual de um dado tabuleiro em ficheiro.

Para o efeito deverá ser implementada uma Shell em que se implementam os seguintes
comandos:
 jogar <ficheiro> <jogador> comando jogar que leva como parâmetro o nome de
um ficheiro e a identificação do jogador e carrega o tabuleiro, permitindo jogá-lo;
 gravar <ficheiro> comando gravar que leva como parâmetro o nome de um
ficheiro e permite gravar o estado do jogo atual;
 tiro <l> <c> comando tiro que permite o utilizador jogar na linha l e coluna c;
 agua <l> <c> comando agua que leva como parâmetros a linha e a coluna de uma
casa, pertencente a uma embarcação que se pretende rodear de “água”. Se alguma
destas casas contiver um segmento de barco (caso em que a embarcação ainda não
está totalmente descoberta/afundada), o jogador automaticamente perde;
 linha <l> comando linha que permite colocar o estado de todas as casas da linha l
que ainda não estão determinadas como sendo “água”. Se alguma destas casas
contiver um segmento de barco (caso em que a embarcação ainda não está
totalmente descoberta/afundada), o jogador automaticamente perde;
 coluna <c> comando coluna que permite colocar o estado de todas as casas da
coluna c que ainda não estão determinadas como sendo “água”. Se alguma destas
 casas contiver um segmento de barco (caso em que a embarcação ainda não está
totalmente descoberta/afundada), o jogador automaticamente perde;
 ajuda comando ajuda que indica por linha e por coluna a quantidade de
segmentos de barco existentes nessa linha/coluna.
 undo comando undo para anular movimentos (retroceder no jogo);
 bot comando bot para apresentar a sequência de jogadas ótimas para terminar o
jogo;
 gerar comando gerar que gera tabuleiros válidos;
 score comando score que permite ver o registo ordenado dos scores dos
jogadores;
 ver comando ver para visualizar o tabuleiro em ambiente gráfico;
 sair comando para sair do jogo.

Após cada comando, deve ser apresentado o tabuleiro e uma mensagem de confirmação
de ação ou de erro.
Como se pretende que seja criado um registo dos scores dos jogadores, é necessário que
cada jogador possa indicar o seu nome sempre que decidir jogar. Entende-se por “score” o
mínimo de jogadas feitas que permitiram ganhar o jogo. Este registo deve sempre incluir o nome
do jogador.

Formato do ficheiro
O formato do ficheiro contempla sempre o tabuleiro de jogo, seguido da informação de
número de jogadas ótimas e do número de jogadas efetuadas. Caso tenha sido gravado o estado
atual do tabuleiro durante o jogo, este tabuleiro com as jogadas efetuadas deverá ser representado
a seguir ao tabuleiro inicial. A representação do tabuleiro inicial deverá ser a seguinte:
 A primeira linha contém um espaço seguidos da numeração das colunas da grelha de
jogo;
 As seguintes dez linhas apresentam o mesmo padrão: letra correspondente à linha e
representação do tabuleiro, isto é:
o O caractere . se a casa for vazia;
 o O caractere # se a casa contiver um segmento de barco.

A representação de tabuleiro já iniciado deverá ser a seguinte:

 A primeira linha contém um espaço seguidos da numeração das colunas da grelha de
jogo;
 As seguintes dez linhas apresentam o mesmo padrão: letra correspondente à linha e
representação do tabuleiro, isto é:
o O caractere . se a casa for vazia;
o O caractere # se a casa contiver um segmento de barco;
o O caractere O se se acertou numa casa com água;
o O caractere X se se acertou num segmento de barco;
o O caractere * se o barco foi afundado.

Após a representação de cada tabuleiro, deverão estar indicadas o número de jogadas

ótimas para terminar o jogo segundo o bot e o número de jogadas feitas pelo utilizador até àquele
momento.
Segue um exemplo da representação de um tabuleiro:

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
A A . . . . . . . . . .
B O B . # # # # . . O . .
C C . . . . . . . . . .
D D . . . . . . . . . .
E O X X X → E # . . O * * * . . .
F F # # # . . . . . . .
G G # . . . # . . . # .
H H . . . . . . . . . .
I X I . . # . . . . . * .
J J . . # . . # # . . .
Exemplo de utilização de alguns comandos (o que deverá aparecer na Shell)
BatalhaNaval> jogar tab1.txt
1 2 3 4 5 6 7 8 9 10
A . . . . . . . . . .
B . . . . . . . . . .
C . . . . . . . . . .
D . . . . . . . . . .
E . . O . X . X . . .
F . . . . . . . . . .
G . . . . . . . . . .
H . . . . . . . . . .
I . . . . . . . . * .
J . . . . . . . . . .
[topgun] Jogadas efetuadas:4

BatalhaNaval> ajuda
3 2 4 1 3 2 2 0 2 0
1 2 3 4 5 6 7 8 9 10
1>A . . . . . . . . . .
5>B . . . . . . . . . .
1>C . . . . . . . . . .
0>D . . . . . . . . . .
4>E . . O . X . X . . .
3>F . . . . . . . . . .
3>G . . . . . . . . . .
0>H . . . . . . . . . .
2>I . . . . . . . . * .
3>J . . . . . . . . . .
[topgun] Jogadas efetuadas:4

BatalhaNaval> tiro B 7
1 2 3 4 5 6 7 8 9 10
A . . . . . . . . . .
B . . . . . . O . . .
C . . . . . . . . . .
D . . . . . . . . . .
E . . O . X . X . . .
F . . . . . . . . . .
G . . . . . . . . . .
H . . . . . . . . . .
I . . . . . . . . * .
J . . . . . . . . . .
[topgun] Jogadas efetuadas:5

BatalhaNaval> tiro E 6 (ao acertar na casa restante de um contratorpedeiro, afunda-o,

tornando as casas automaticamente marcadas com *)
 1 2 3 4 5 6 7 8 9 10
A . . . . . . . . . .
B . . . . . . O . . .
C . . . . . . . . . .
D . . . . . . . . . .
E . . O . * * * . . .
F . . . . . . . . . .
G . . . . . . . . . .
H . . . . . . . . . .
I . . . . . . . . * .
J . . . . . . . . . .
[topgun] Jogadas efetuadas:6

BatalhaNaval> linha H
1 2 3 4 5 6 7 8 9 10
A . . . . . . . . . .
B . . . . . . O . . .
C . . . . . . . . . .
D . . . . . . . . . .
E . . O . * * * . . .
F . . . . . . . . . .
G . . . . . . . . . .
H O O O O O O O O O O
I . . . . . . . . * .
J . . . . . . . . . .
[topgun] Jogadas efetuadas:7

BatalhaNaval> agua G 8 (o jogador perde porque há um barco em G9)

Jogada inválida! Há segmentos de barco ao redor de G8!
1 2 3 4 5 6 7 8 9 10
A . . . . . . . . . .
B . . . . . . O . . .
C . . . . . . . . . .
D . . . . . . . . . .
E . . O . * * * . . .
F . . . . . . . . . .
G . . . . . . . . . .
H O O O O O O O O O O
I . . . . . . . . * .
J . . . . . . . . . .
[topgun] Jogadas efetuadas:8
PERDEU!!!FIM DE JOGO!

Repare que o comando tiro não faz nenhuma verificação ao efetuar a jogada para ver se é
uma jogada válida de acordo com as regras ou não. A única verificação que o comando faz é se
tentar colocar uma peça numa casa bloqueada ou fora do tabuleiro. Nesse caso, o comando não
deverá fazer nada devolvendo uma mensagem de erro de casa bloqueada ou fora do tabuleiro.

Observações
 Deverá programar utilizando o paradigma da programação por objetos, desenvolvendo
classes próprias para a resolução do problema proposto.
 Pretende-se que na resolução deste problema sejam utilizados as “estruturas de dados”
dinâmicas e os tipos abstratos de dados (caso se justifiquem) que foram dados nas aulas;
 O código deve ser bem documentado.
 Na fase de “especificação do problema” pode fazer as considerações relativas ao
problema que entender mais adequadas.

Metodologia
O trabalho prático será realizado em grupo, devendo este ser constituído no máximo por
3 elementos. Cada grupo deverá enviar um email para [email protected] com a constituição
do grupo, colocando no tema da mensagem “IAP-grupo de trabalho”.
A entrega do trabalho compreende a entrega de um relatório (formato .pdf) e os módulos
Python desenvolvidos num só ficheiro comprimido (.zip) com a solução do problema proposto.
A entrega será efetuada por upload no portal de e-learning por um dos elementos do grupo.
A avaliação do trabalho será realizada, fundamentalmente, com base nos seguintes
critérios:
 Programa desenvolvido;
 Soluções algorítmicas;
 Relatório escrito;
 Cumprimento das regras estabelecidas.
Os elementos dos grupos farão a apresentação individual do trabalho desenvolvido de
acordo com o calendário que, entretanto, será publicado no portal de e-learning.

Prazo de Entrega do Trabalho: 5 de janeiro de 2020.