Objectif : Lire et Analyser un sujet - Choisir les bonnes structures de données - Parcours simple dans un graphe - Analyser les besoins en temps et en mémoire.
Pour tous les exercices de cette session, on vous fournit deux
fichiers squelette Session3.java et Grid.java.
Les objectifs sont, dans l’ordre, que le code soit
correct, que le code soit efficace et
que le code soit lisible. Des tests unitaires
sont fournis dans Session3Test.java.
Vous devez être attentifs à la quantité de mémoire nécessaire à votre programme et vous avez le droit d’utiliser toutes les caractéristiques de l’entrée (elles sont indiquées pour chaque exercice) pour concevoir un code efficace.
Dans cette partie, vous ne devez pas utiliser de
Stream.
On va représenter une grille de bataille navale (l’objet
Grid) du point de vue d’un joueur. Une grille est composée
de cases (x,y) avec
0 ≤ x < lengthX
et 0 ≤ y < lengthY,
où (0,0) désigne la case en bas à
gauche. Sur la grille, un joueur place des bateaux. Un bateau a un nom
(String), ainsi qu’une direction (UP, DOWN,
LEFT, RIGHT) et une longueur length.
Les directions sont spécifiées ainsi :
UP : (x,y) ⭢ (x,y+1)
DOWN : (x,y) ⭢ (x,y-1)
RIGHT: (x,y) ⭢ (x+1,y)
LEFT : (x,y) ⭢ (x-1,y)Dans un premier temps, nous allons placer les bateaux sur la grille.
Bien évidemment, un bateau ne peut pas déborder de la grille (occuper
une position en dehors de la grille) et deux bateaux ne peuvent pas
occuper une même position. Pour placer un bateau, le joueur précise la
position (x,y) de la
première case du bateau. Si sa direction et RIGHT et sa
longueur length,
il occupera les positions consécutives (x,y), (x+1,y), … (x+length−1,y),
et de façon similaire pour les autres directions.
La classe Grid représente une grille avec son état
courant. Implémenter la méthode addShip
qui rajoute un bateau sur la grille. Si jamais un bateau ne peut pas
être placé, la méthode doit renvoyer false,
et sinon true.
public boolean addShip(Ship ship, int x, int y)Vous devez également implémenter la méthode
numberOfShips qui permet à tout instant de connaître le
nombre de bateaux placés sur la grille.
public int numberOfShips() Nous fournissons un fichier avec une série de bateaux à placer.
Implémenter la méthode statique suivante dans la classe
Session3.
public static Grid buildGrid(Path path)Si un bateau ne peut pas être placé, la fonction continue avec le bateau suivant dans le fichier en ignorant le bateau qui ne peut pas être placé.
Caractéristiques des fichiers d’entrée :
L’entrée est un fichier contenant sur la première ligne, les
longueurs lengthX
et lengthY
de la grille. La deuxième ligne contient un entier M qui désigne la quantité de
bateaux. Les M lignes
suivantes décrivent les bateaux comme suit : d’abord le nom (une chaîne
de caractères sans espaces), suivie de la direction (UP,
DOWN, LEFT ou RIGHT), un entier
qui indique sa longueur, et finalement deux entiers positifs x et y pour la position de base du
bateau.
DIFFICULTÉ Niv. 1
lengthX et lengthY max: 1_000
Nombre de bateaux M max: 100
Longueur maximale des bateaux: 10
DIFFICULTÉ Niv. 2
lengthX et lengthY max: 1_000_000_000
Nombre de bateaux M max: 10_000
Longueur maximale des bateaux: 100Exemple :
10 10 --> taille de la grille
6 --> nombre de bateaux
A UP 5 0 0
B RIGHT 3 1 0
C RIGHT 3 4 0
D DOWN 5 9 9
E UP 5 9 1 --> E ne peut pas être placé
F LEFT 9 3 5 --> F ne peut pas être placéLa grille finale est la suivante, où . désigne une case
vide :
y
9 | . . . . . . . . . D
8 | . . . . . . . . . D
7 | . . . . . . . . . D
6 | . . . . . . . . . D
5 | . . . . . . . . . D
4 | A . . . . . . . . .
3 | A . . . . . . . . .
2 | A . . . . . . . . .
1 | A . . . . . . . . .
0 | A B B B C C C . . .
-------------------
0 1 2 3 4 5 6 7 8 9 xUne fois que les bateaux sont placés, l’autre joueur peut lancer des bombes. Pour cela, le joueur indique une case de la grille.
Implémenter la méthode bomb de
la classe Grid qui renvoie une Response qui
peut être du type Nothing, Hit (bateau touché)
ou Sunk (bateau coulé). Si on touche une case déjà touchée
d’un bateau, ou une case sans bateau, il ne se passe rien
(Nothing). Quand toutes les cases d’un bateau ont été
touchées par une bombe, le bateau coule on renvoie le record
Sunk(ship) où ship est le bateau en
question.
Implémenter la méthode correspondante de la classe
Grid
public Response bomb(int positionX, int positionY) Afin de tester avec des fichiers, nous allons implémenter une méthode
dans la classe Session3.
public static List<Response> bombGrid(Path path) qui renvoie la liste des résultats des lancers de bombes, sur la grille décrite dans le fichier.
Caractéristiques des fichiers d’entrée :
Les fichiers comportent une première partie qui décrit la grille,
comme dans la partie précédente. Nous rajoutons, après la description
des bateaux, des lignes qui décrivent les bombes. Chaque bombe est
décrite par une ligne comme suit : d’abord un symbole #
suivi par un espace et deux entiers x et y qui indiquent la position.
DIFFICULTÉ Niv. 1
lengthX et lengthY max: 1_000
Nombre de bateaux M max: 100
Longueur maximale des bateaux: 10
Nombre de bombes max: 10_000
DIFFICULTÉ Niv. 2
lengthX et lengthY max: 1_000_000_000
Nombre de bateaux M max: 10_000
Longueur maximale des bateaux: 100
Nombre de bombes max: 1_000_000Exemple :
10 10 --> taille de la grille
4 --> nombre de bateaux
A UP 5 0 0
B RIGHT 3 1 0
C RIGHT 3 4 0
D DOWN 5 9 9
# 9 5 --> HIT D
# 9 4 --> NOTHING
# 1 0 --> HIT B
# 1 0 --> NOTHING (déjà touché)
# 2 0 --> HIT B
# 3 0 --> SUNK, bateau B couléPour rendre le jeu plus intéressant, nous avons décidé que les
bateaux peuvent bouger ! Un bateau peut bouger que dans sa propre
direction
(UP,DOWN,LEFT,RIGHT).
Implémenter la méthode suivante de la classe Grid
public void advanceTime()qui fait avancer le temps d’un tour. Quand le temps avance d’un tour,
les bateaux avancent d’une position. Par exemple, si un bateau
avec la direction RIGHT occupe les positions (x,y) … (x+l−1,y), après
il occupera les positions (x+1,y) … (x+l,y). Bien sûr,
les bateaux bougent seulement si c’est possible. Si cela impliquerait
une collision avec un autre bateau ou de sortir de la grille, le bateau
en question ne bouge pas. Le joueur déplace les bateaux un par un, en
respectant l’ordre d’insertion des bateaux dans la grille.
Si un bateau qui a été touché par une bombe se déplace, les positions
touchées se déplacent aussi de façon relative. Par exemple, si un bateau
avec direction RIGHT et longueur 2 occupe les cases (x,y) et (x+1,y), et que sa première
case (celle en position (x,y)) a été touchée par
une bombe, après l’appel à advanceTime, le bateau occupe
les cases (x+1,y) et
(x+2,y) (en supposant
que x + 2 < lengthX)
et sa première case (désormais en position position (x+1,y)) reste toujours
touchée.
Afin de tester avec des fichiers, nous allons implémenter une méthode
correspondant dans la classe Session3.
public static List<Response> simulateGrid(Path path) Caractéristiques des fichiers d’entrée :
Après la descriptions des bateaux, chaque ligne décrit soit une
bombe, soit le passage d’un tour. Le passage d’un tour est indiqué par
une ligne contenant juste le symbol *.
DIFFICULTÉ Niv. 1
lengthX et lengthY max: 1_000
Nombre de bateaux M max: 100
Longueur maximale des bateaux: 10
Nombre de bombes max: 10_000
Nombre de tours max: 100
DIFFICULTÉ Niv. 2
lengthX et lengthY max: 1_000_000_000
Nombre de bateaux M max: 10_000
Longueur maximale des bateaux: 100
Nombre de bombes max: 1_000_000
Nombre de tours max: 10_000Exemple :
10 10 --> taille de la grille
4 --> nombre de bateaux
A UP 5 0 0
B RIGHT 3 1 0
C RIGHT 3 4 0
D DOWN 5 9 9
# 9 5 --> HIT D
*
# 9 4 --> HIT D
# 1 0 --> NOTHING
# 2 0 --> HIT B
# 3 0 --> HIT B
# 4 0 --> SUNK, bateau B couleCertains marins de votre flotte voudraient se déplacer d’un bateau à un autre.
Pour qu’il soit possible de passer d’un bateau à un autre :
Nous allons implémenter une méthode, dans la classe
Grid,
public List<Ship> findPath(Ship startShip, Ship endShip) qui renvoie, si un chemin existe, une liste avec les bateaux sur le chemin de startShip à endShip. Le premier élément de la liste doit être startShip et le dernier endShip, et tous deux éléments consécutifs de la liste doivent être des bateaux dans des cases voisines. La fonction doit renvoyer une liste vide si aucun chemin n’existe. S’il y a plusieurs chemins possibles, la fonction peut renvoyer n’importe lequel.
Afin de tester la fonction findPath, les tests utilisent
la méthode public static Grid buildGrid(Path path), de la
classe Session3, avant d’appeler findPath dans
la Grid renvoyée.