Dicas/notas:
- Primeiro pode começar por criar uma solução adaptada para as colunas, linhas e diagonais e verificar que a sua solução está correta.
- Crie os seus casos de teste e teste a sua solução está correta.
- Após os passos anteriores, irá verificar que na sua primeira solução, o código que utilizou para a verificação das linhas é muito parecido com o que usou para as colunas e diagonais.
- Tente encontrar uma solução que generalize a verificação das linhas para que possa ser usado nas restantes verificações (colunas e diagonais).
Exercício 2) Jogo da Vida
Dicas/notas:
- O Jogo da Vida é talvez o mais conhecido autómato celular e foi criado para simular, através de regras simples.
- O objectivo é principal é que submeta um código adequado e estruturado.
- Comece por ler o enunciado do problema, prestando especial atenção às regras que definem como é criada uma nova geração a partir do estado actual do jogo.
- Depois de ler, experimente interagir um pouco com o jogo, para garantir que percebeu as regras:
- Vá por exemplo a este simulador: https://playgameoflife.com/.
- Experimente usar o botão Next para ir vendo como aparece cada nova geração.
- Usando o botão Start pode ver as várias gerações a irem aparecendo sem ter de carregar num botão para cada nova geração (pode também usar o interface para mudar a velocidade das iterações)
- No "lexicon" pode ver outras formas de vida inciais (estados do tabuleiro) que dão origem resultados interessantes (carregando na figura consegue colocá-las no simulador)
- Para este problema vamos sugerir que use o seguinte esqueleto de código (que contém funções que deverá completar).
[Depois do código vem explicado um conjunto de passos para completar este exercício!]
/* ----------------------------------- Estruturas de Dados 2024/2025 Jogo da Vida [ED088] ----------------------------------- */ import java.util.Scanner; // Classe para representar um jogo class Game { final char DEAD = '.'; // Constante que indica uma celula morta final char ALIVE = 'O'; // Constante que indica uma celula viva private int rows, cols; // Numero de linhas e colunas private char m[][]; // Matriz para representar o estado do jogo // Construtor: inicializa as variaveis tendo em conta a dimensao dada Game(int r, int c) { rows = r; cols = c; m = new char[r][c]; } // Metodo para ler o estado inicial para a matriz m[][] public void read(Scanner in) { for (int i=0; i<rows; i++) m[i] = in.next().toCharArray(); } // Metodo para escrever a matriz m[][] public void write() { // ... por completar } // Deve devolver o numero de celulas vivas que sao vizinhas de (y,x) private int countAlive(int y, int x) { int count = 0; // ... por completar return count; } // Deve fazer uma iteracao: cria nova geracao a partir da actual public void iterate() { // ... por completar } } // Classe principal com o main() public class ED088 { public static void main(String[] args) { Scanner in = new Scanner(System.in); // Ler linhas, colunas e numero de iteracoes int rows = in.nextInt(); int cols = in.nextInt(); int n = in.nextInt(); // Criar objecto para conter o jogo e ler estado inicial Game g = new Game(rows, cols); g.read(in); //... por completar } }
- Passos sugeridos:
- Poderá começar por completar o método write() da classe Game, que deverá escrever a matriz m[][] para a saída padrão. Deverá chamar g.write() no método main para testar se o que fez está a funcionar.
[Sempre que implemente novos métodos deve testar o seu funcionamento individual!] - Agora deverá implementar o método int countAlive(int y, int x). Este método deve percorrer todas as oito células vizinhas da posição (y,x) e contar quantas são iguais a ALIVE (ou sejam iguais a 'O'). Não se esqueça de testar o funcionamento depois de implementar!
- O próximo passo é implementar o método void iterate() que deverá fazer uma iteração do jogo da vida, ou seja, produzir a nova geração a partir da actual. Para isso pode criar uma nova matriz (por exemplo com char m2[][] = new char[rows][col]; e depois percorrer todas as posições possíveis e colocar em DEAD ou ALIVE consoante o número de vizinhos (aqui deve chamar a função countAlive(y,x) que implementou anteriormente. Finalmente deve copiar o conteúdo da nova matriz (m2[][]) para a matriz que contém o estado actual (m[][]). Note que é fundamental não escrever logo na matriz m[][] enquanto quando vai criando a nova geração por causa da regra indicada no enunciado: "todos os nascimentos e mortes de células têm lugar em simultâneo, isto é as alterações têm por base o estado actual e nunca o estado futuro".
- Para finalizar o problema basta completar o método main: chamar n vezes função anterior que faz uma iteração (g.iterate()) e no final escrever (g.write())
- Poderá começar por completar o método write() da classe Game, que deverá escrever a matriz m[][] para a saída padrão. Deverá chamar g.write() no método main para testar se o que fez está a funcionar.
Exercício 3) Sopa de Letras
Neste exercício a ideia é tentar resolver o problema de forma organizada e estruturada sozinho. O problema em questão é o [ED015] Sopa de Letras que também disponível no Mooshak.
- Antes de começar a escrever código, não se esqueça que deve:
- Ler todo o enunciado com atenção, e perceber as tarefas e as restrições (limites do input)
- Pensar como vai organizar o código: como dividir as tarefas em blocos pequenos? que classes usar? onde guardar os dados? que métodos criar?
- Durante a implementação, não se esqueça de:
- Criar métodos - não fazer tudo no main
- Escrever código para humanos (a melhor documentação é um código bem escrito)
- Adicionar comentários a partes não triviais (para que da próxima vez que lerem o vosso código ainda o percebam)
- Generalizar: evitar copy+paste e ter código que generaliza uma tarefa e pode ser reutilizado
- Testem o vosso programa à medida que vão implementando. Cada vez que criam um método, testem o seu funcionamento chamando-o e imprimindo os resultados.
- Testem o vosso programa no final de implementarem e antes de submeterem. Usem não só os exemplos do enunciado, mas experimentem com outros casos feitos por vocês. Não criem dependência do Mooshak para testar o vosso código porque no futuro não terão a "papinha feita" e os testes já preparados para vocês.
Exercícios extra para consolidação de conhecimentos
- O Mundo da Tartaruga
Para cimentar os seus conhecimentos sobre uma programação bem estruturada, segue mais um problema. O problema em questão é o [ED101] O Mundo da Tartaruga que também disponível no Mooshak. - O Mundo da Tartaruga... gráfico!
Se já tiver feito todos os outros exercícios e quiser "brincar" um pouco com interfaces gráficos no seguimento do problema anterior, pode usar um TAD de desenho chamado StdDraw, implementando por docentes da Universidade de Princeton. Comece por fazer download do ficheiro StdDraw.java, compile-o e execute-o. Deverá ver uma janela como a que se segue:
Espreite o método main para ver como as imagens da janela foram geradas. Como referência, e se necessário, pode consultar a documentação da classe StdDraw.
A ideia deste exercício vai ser criar uma classe para Turtle Graphics, um termo que designa um tipo de criação de desenhos usando um "cursor" que vai "andando" por um plano. A ideia é portanto desenhar num plano cartesiano (com tamanho a ser dado na construção do objecto) e ter um "cursor", a tartaruga, com uma dada posição e orientação, sendo possível andar na direção actual e ter um lápis que pode estar ou não levantado.
- Classe e construtores.
Crie uma classe Turtle que consegue guardar a posição da tartaruga (coordenadas x e y), a orientação actual (uma direção em graus) e o estado do lápis (pousado/levantado). A classe deve também guardar o tamanho da área de desenho. Crie um construtor padrão que coloca a tartaruga na posição (0,0), orientação a 0 graus, com o lápis pousado. - Métodos iniciais.
Crie os seguintes métodos numa classe LibTurtle: - Um método para pousar e outro para levantar o lápis
- Um método para rodar x graus (pode ser um número positivo ou negativo)
- Um método para andar para a "frente" (consoante a direção) x pixeis. Se o lápis estiver pousado, isto deve dar origem a uma linha.
- Crie métodos para desenhar:
- Um quadrado com um lado de x pixeis (será algo como andar x para a frente, rodar 90 graus, andar x para a frente, rodar 90 graus e assim mais duas vezes até fechar o quadrado).
- Um polígono regular de n lados, cada um com x pixeis (uma generalização do quadrado)
- Uma espiral
- Crie um método para movimento browniano: uma tartaruga desorientada, que executa ciclicamente (n vezes) os seguintes passos: rodar para uma direção aleatória, andar para a frente x pixeis (e depois voltar a rodar aleatoriamente, andar para a frente x e assim continuadamente).
- Crie código para ler de um ficheiro comandos para "dirigir" a tartaruga. Um exemplo seria algo como:
forward 50 rotate 90 penUp forward 100 rotate 20 penDown forward 30
- Classe e construtores.