Entrainement avec France-IOI⚓︎
Concours Algorea 2015 : Tour 2
On suppose que, comme indiqué à la page travaux pratiques, vous vous êtes entrainés sur France-IOI avec
Concours Algorea 2015 : Tour 2
Regardons, pas à pas, comment améliorer votre solution.
Pas à pas
Vous devez dérouler chaque admonition, bien lire le contenu et faire l'exercice à nouveau en ligne.
Feu de forêt⚓︎
Comparaison d'algorithmes
L'objectif principal de cette section sera de comparer différents algorithmes.
Nous verrons des méthodes récursives et on prépare le terrain pour évoquer des méthodes qui sont utilisées avec les graphes : l'utilisation de piles ou de files.
Écrire un programme qui indique à quelle date chaque case de la forêt sur la carte va bruler.
Solution officielle
from lib import *
ecrireDate(1, 2, 0)
ecrireDate(1, 1, 1)
ecrireDate(0, 2, 1)
ecrireDate(1, 0, 2)
ecrireDate(2, 1, 2)
ecrireDate(0, 3, 2)
ecrireDate(0, 0, 3)
ecrireDate(2, 0, 3)
ecrireDate(3, 1, 3)
ecrireDate(0, 4, 3)
1] Factorisez ce code pour n'avoir qu'un seul ecrireDate
On pourra stocker les paramètres dans une liste.
Réponse 1]
from lib import *
solution = [
(1, 2, 0),
(1, 1, 1),
(0, 2, 1),
(1, 0, 2),
(2, 1, 2),
(0, 3, 2),
(0, 0, 3),
(2, 0, 3),
(3, 1, 3),
(0, 4, 3),
]
for i, j, date in solution:
ecrireDate(i, j, date)
2] Factoriser encore ce code
Réécrire la liste des solutions afin que la réponse soit ensuite
from lib import *
solution = [...] # À compléter
for date in range(len(solution)):
for i, j in solution[date]:
ecrireDate(i, j, date)
Réponse 2]
solution = [
[(1, 2)], # jour 0
[(1, 1), (0, 2)], # jour 1
[(1, 0), (2, 1), (0, 3)], # jour 2
[(0, 0), (2, 0), (3, 1), (0, 4)], # jour 3
]
Ici, le feu se propage vers la gauche d'une case par jour, jusqu'au premier obstacle.
Solution officielle
from lib import *
iCol = colDepart()
while (iCol >= 0) and not (estObstacle(ligDepart(), iCol)):
ecrireDate(ligDepart(), iCol, colDepart()-iCol)
iCol -= 1
1] Reprenez ce code...
i_0, j_0comme coordonnées initiales, puisi, jcomme coordonnées variables- avec un calcul progressif de la
date - avec des lignes plus courtes
On pourra relire l'énoncé concernant la fonction estObstacle et son comportement en dehors de la grille.
Réponse 1]
from lib import *
i = i_0 = ligDepart()
j = j_0 = colDepart()
date = 0
while not estObstacle(i, j):
ecrireDate(i, j, date)
j -= 1 # on va à gauche
date += 1
2] Reprenez ce code...
- on remplace le dernier bloc par
- une fonction d'entête
def marque(i, j, date):- en version itérative
- puis en version récursive
Réponse 2]
from lib import *
def marque(i, j, date):
while not estObstacle(i, j):
ecrireDate(i, j, date)
j -= 1 # on va vers la gauche
date += 1
i_0 = ligDepart()
j_0 = colDepart()
date = 0
marque(i_0, j_0, date)
from lib import *
def marque(i, j, date):
if not estObstacle(i, j):
ecrireDate(i, j, date)
marque(i, j - 1, date + 1)
i_0 = ligDepart()
j_0 = colDepart()
date = 0
marque(i_0, j_0, date)
Ici, la carte ne contient aucun obstacle et le feu se propage vers le bas et vers la droite, d'une case par jour.
Solution officielle
from lib import *
for iLig in range(ligDepart(), tailleCote()):
for iCol in range(colDepart(), tailleCote()):
date = (iLig - ligDepart()) + (iCol - colDepart())
ecrireDate(iLig, iCol, date)
1] Reprenez ce code...
- avec une fonction d'entête
def marque(i_0, j_0, date): - en incluant des informations de l'énoncé qui différencient cette version des autres.
Réponse 1]
from lib import *
"""
- `tailleCote()` renvoie nb_cases sur un côté de la zone carrée.
- `ligDepart()` renvoie la ligne `i` de départ du feu, à `date` 0
- `colDepart()` renvoie la colonne `j` de départ du feu, à `date` 0
- `estObstacle(i, j)` renvoie
- 1 si
- la case donnée est un obstacle qui ne brûle pas
- ou bien si la case se trouve en dehors du terrain,
- 0 sinon.
- `ecrireDate(i, j, date)` enregistre le fait que la case donnée
- va brûler à la date donnée.
- (Ne fait rien si la case se trouve en dehors du terrain.)
- `lireDate(i, j)` renvoie la date qui a été enregistrée pour la case donnée,
- ou bien -1 si aucune date n'a été enregistrée.
- Renvoie -1 si la case se trouve en dehors du terrain.
Version C
: pas d'obstacle
: le feu se propage vers le bas et vers la droite,
d'une case par jour.
"""
def marque(i_0, j_0, date):
# version mathématique
for i in range(i_0, tailleCote()):
for j in range(j_0, tailleCote()):
# distance de Manhattan
date = (i - i_0) + (j - j_0)
ecrireDate(i, j, date)
i_0 = ligDepart()
j_0 = colDepart()
marque(i_0, j_0, 0)
2] Reprenez ce code...
- avec une fonction récursive.
Si votre code est trop lent, c'est que vous faites des appels multiples sur les mêmes paramètres sans vous en rendre compte. Il faut alors vérifier que le travail est à faire, ou bien déjà fait...
Réponse 2]
from lib import *
"""
- `tailleCote()` renvoie nb_cases sur un côté de la zone carrée.
- `ligDepart()` renvoie la ligne `i` de départ du feu, à `date` 0
- `colDepart()` renvoie la colonne `j` de départ du feu, à `date` 0
- `estObstacle(i, j)` renvoie
- 1 si
- la case donnée est un obstacle qui ne brûle pas
- ou bien si la case se trouve en dehors du terrain,
- 0 sinon.
- `ecrireDate(i, j, date)` enregistre le fait que la case donnée
- va brûler à la date donnée.
- (Ne fait rien si la case se trouve en dehors du terrain.)
- `lireDate(i, j)` renvoie la date qui a été enregistrée pour la case donnée,
- ou bien -1 si aucune date n'a été enregistrée.
- Renvoie -1 si la case se trouve en dehors du terrain.
Version C
: pas d'obstacle
: le feu se propage vers le bas et vers la droite,
d'une case par jour.
"""
def marque(i, j, date):
# version récursive
ecrireDate(i, j, date)
date += 1
i_ = i + 1
if i_ < tailleCote():
if lireDate(i_, j) == -1:
marque(i_, j, date)
j_ = j + 1
if j_ < tailleCote():
if lireDate(i, j_) == -1:
marque(i, j_, date)
i_0 = ligDepart()
j_0 = colDepart()
date = 0
marque(i_0, j_0, date)
Ici, le feu se propage vers le bas et vers la droite, d'une case par jour, jusqu'à rencontrer des obstacles.
Solution officielle
from lib import *
ecrireDate(ligDepart(), colDepart(), 0)
for iJour in range(1, 2*tailleCote()):
for iLig in range(tailleCote(), ligDepart()-1, -1):
for iCol in range(tailleCote(), colDepart()-1, -1):
if not (estObstacle(iLig, iCol) and (lireDate(iLig, iCol) == -1) and ((lireDate(iLig, iCol-1) != -1) or (lireDate(iLig-1, iCol) != -1)):
ecrireDate(iLig, iCol, iJour)
1] Reprenez ce code...
- avec des lignes plus courtes
- qui balaye la zone
- si la
dateexacte est trouvée- marquer en bas et à droite si ce n'est pas un obstacle.
Réponse 1]
from lib import *
i_0, j_0 = ligDepart(), colDepart()
ecrireDate(i_0, j_0, 0)
for date in range(2 * tailleCote() - 1):
for i in range(tailleCote()):
for j in range(tailleCote()):
if lireDate(i, j) == date:
if not estObstacle(i + 1, j):
ecrireDate(i + 1, j, date + 1)
if not estObstacle(i, j + 1):
ecrireDate(i, j + 1, date + 1)
Ce code reste assez inélégant et lent ; mais il peut amener à une solution récursive.
2] Reprenez ce code...
- avec une fonction récursive
Réponse 2]
from lib import *
def marque(i, j, date):
ecrireDate(i, j, date)
if not estObstacle(i + 1, j):
if lireDate(i + 1, j) == -1:
marque(i + 1, j, date + 1)
if not estObstacle(i, j + 1):
if lireDate(i, j + 1) == -1:
marque(i, j + 1, date + 1)
i_0 = ligDepart()
j_0 = colDepart()
date = 0
marque(i_0, j_0, date)
Ici, le feu se déplace dans les quatre directions (haut, bas, gauche, droite), d'une case par jour, jusqu'à rencontrer des obstacles.
Solution officielle
from lib import *
def courant(lig, col, masque):
if estObstacle(lig, col):
return False
if (lireDate(lig, col) != -1):
return False
if lireDate(lig+1, col) == masque:
return True
if lireDate(lig-1, col) == masque:
return True
if lireDate(lig, col+1) == masque:
return True
if lireDate(lig, col-1) == masque:
return True
return False
def remplir(jour):
for iLig in range(tailleCote()):
for iCol in range (tailleCote()):
if courant(iLig, iCol, jour-1):
ecrireDate(iLig, iCol, jour)
ecrireDate(ligDepart(), colDepart(), 0)
for iJour in range(1, tailleCote()*tailleCote()):
remplir(iJour)
1] Reprenez un autre code...
- le code récursif de la version D
- mais avec 4 directions à traiter
- commencer par un copier/coller et quelques ajustements pour les 4 directions
Attention, il faudra ajouter une condition
- Si la date n'est pas marquée
- ou bien si la date marquée est plus ancienne que
date + 1!
En effet, les trajets jusqu'à un point sont plus ou moins longs en fonction des obstacles. Dans la version D, tous les trajets d'un points à un autre on la même distance de Manhattan.
Réponse 1]
from lib import *
def marque(i, j, date):
ecrireDate(i, j, date)
if not estObstacle(i + 1, j):
if (lireDate(i + 1, j) == -1) or (lireDate(i + 1, j) > date + 1):
marque(i + 1, j, date + 1)
if not estObstacle(i, j + 1):
if (lireDate(i, j + 1) == -1) or (lireDate(i, j + 1) > date + 1):
marque(i, j + 1, date + 1)
if not estObstacle(i - 1, j):
if (lireDate(i - 1, j) == -1) or (lireDate(i - 1, j) > date + 1):
marque(i - 1, j, date + 1)
if not estObstacle(i, j - 1):
if (lireDate(i, j - 1) == -1) or (lireDate(i, j - 1) > date + 1):
marque(i, j - 1, date + 1)
i_0 = ligDepart()
j_0 = colDepart()
date = 0
marque(i_0, j_0, date)
2] Reprenez ce code...
- factoriser en utilisant une liste de 4 vecteurs de direction
Réponse 2]
from lib import *
def marque(i, j, date):
ecrireDate(i, j, date)
for di, dj in [(+1, 0), (-1, 0), (0, +1), (0, -1)]:
i_, j_ = i + di, j + dj
if not estObstacle(i_, j_):
if lireDate(i_, j_) == -1 or lireDate(i_, j_) > date + 1:
marque(i_, j_, date + 1)
i_0 = ligDepart()
j_0 = colDepart()
date = 0
marque(i_0, j_0, date)
Commentaires
-Pour cette version récursive, il est important de vérifier, une fois qu'une case n'est pas un obstacle - si une date n'a pas été écrite - on peut écrire une proposition de date ; peut-être que d'autres appels récursifs arriveront à cette case avec une date plus précoce - sinon, on vérifie si notre nouvelle date proposée est plus récente - dans ce cas, on met à jour (de manière récursive)
Une situation schématisée
- On part d'une situation avec des appels récursif, comme dans le code précédent,
- d'abord en bas,
- puis en haut,
- puis à droite,
- puis à gauche.
Chaque appel récursif se décompose en 4 appels potentiels...
Observons le déroulé avec plusieurs étapes à la fois.
- On part de
(4, 3)à la date 0- On fait un appel vers le bas en
(5, 3)à la date 1- Un appel vers le bas en
(6, 3)n'est pas concluant (obstacle) - Un appel vers le haut en
(4, 3)n'est pas concluant (date plus courte déjà placée) - On fait un appel vers la droite en
(5, 4)à la date 2- Un appel vers le bas n'est pas concluant (obstacle)
- On fait un appel vers le haut en
(4, 4)à la date 3- On fait de nombreux appels et on se retrouve...
- ... à la diapo suivante !!!
- Un appel vers le bas en
- On fait un appel vers le bas en
- On reprend à la case
(5, 3)à la date 1- L'appel vers le bas est traité à la diapo 1
- L'appel vers le haut est traité à la diapo 1
- L'appel vers la droite est traité à la diapo 1
- On fait un appel vers la gauche en
(5, 2)à la date 2 ; la date 12 écrite est plus tardive que la date 2 proposée, on met à jour et on poursuit donc- Un appel vers le bas en
(6, 2)à la date 3 permet de mettre à jour le 13 en 3 ; rien de plus - Un appel vers le haut en
(4, 2)n'est pas concluant (obstacle) - Un appel vers la droite en
(5, 3)à la date 3 n'est pas concluant, la date 1, plus précoce, est déjà inscrite - Un appel vers la gauche en
(5, 1)à la date 3 est concluant- Il y aura de nombreuses mises à jour...
- Un appel vers le bas en
Et il reste des appels récursifs en attente, par exemple, depuis (4, 3) à la date 0, il y aura ensuite
- un appel en
(3, 3)à la date 1 qui remplacera le 7 (qui sera devenu un 5 entre temps)- et fera de nombreuses mises à jour
- un appel en
(4, 4)à la date 1 qui remplacera le 3- et fera de nombreuses mises à jour
Ici toutes les cases sont remplies, mais il reste des appels récursifs en attente qui peuvent faire des mises à jour.
- Le dernier appel depuis
(5, 1), vers la gauche, fera une petite mise à jour. - L'avant dernier appel depuis
(4, 3), le départ, vers le haut, fera de nombreuses mises à jour. - Le dernier appel depuis
(4, 3), le départ, vers la gauche n'est pas concluant (obstacle)
C'est un succès !
Cependant, la méthode n'est pas très performante, il y a eu de nombreuses mises à jour. Cela dépend des obstacles mais le cout est de la forme \(n^2\) à \(n^3\) suivant les obstacles, en notant \(n\) la taille du carré.
Regardons à nouveau la solution officielle. Elle propose de traiter jour après jour ce qu'il se passe. Une fois que toutes les dates précédentes à iJour ont été écrites, on lance remplir(iJour) en parcourant toute la grille, et si on est pas sur un obstacle, que la case est libre et qu'une case voisine est marquée au jour précédent, on la marque !
Cette méthode n'est pas non plus performante, pour chaque date potentielle, on parcourt toute la grille. Pour un grille de côté \(n\), un parcourt coute \(n^2\) opérations, et il y a presque \(n^2\) dates potentielles. Imaginez un grand serpent qui fait une ligne sur deux pour contourner des obstacles qui font presque toute la ligne... Bref le cout total pourrait être en \(n^4\). C'est donc pire.
À la fin du chapitre sur les structures linéaires, nous verrons une nouvelle approche avec une pile ou une file pour stocker les dates fraichement marquées. Jour par jour, sans mise à jour nécessaire. Et là, on pourra garantir une solution en \(n^2\).
Billes⚓︎
Comparaison de styles
Le but de cette section sera essentiellement de comparer des styles d'écriture de code.
Il n'y a pas, ici, de récursivité.
Il suffit de modifier la position finale en fonction du cas présenté.
Solution officielle
from lib import *
positionFinale(5)
Rien de particulier à signaler ici
C'était simple.
Dans cette version, on lance la bille à l'extrémité gauche du plateau, c'est-à-dire la marche 0. Vous devez écrire un programme qui, étant donné les hauteurs des marches, détermine jusqu'où la bille va aller.
Solution officielle
from lib import *
posBille = 0
while(hauteur(posBille) >= hauteur(posBille+1)):
posBille += 1
positionFinale(posBille)
Quelques variations possibles
Propositions pour un style moins Java et plus Python
- sur l'aération du code
- sur les noms de variable
from lib import *
x = 0
while hauteur(x) >= hauteur(x + 1):
x += 1
positionFinale(x)
On part de la gauche x = 0, et tant que c'est possible, on va vers la droite.
Dans cette version, on lance plusieurs billes successivement, à l'extrémité gauche du plateau (marche 0). À la fin de leur parcours, on laisse les billes là où elles s'arrêtent : elles ajoutent 1 à la hauteur de la marche sur laquelle elles se sont arrêtées.
Solution officielle
from lib import *
altitude = []
for iPos in range(0, nbMarches()):
altitude.append(hauteur(iPos))
for iBille in range(0, nbLancers()):
posBille = 0
while(altitude[posBille] >= altitude[posBille+1]):
posBille += 1
altitude[posBille] += 1
positionFinale(posBille)
Reprenez ce code...
- avec un style plus Python et moins Java.
Réponse
On a besoin de stocker les nouvelles hauteurs pour les mettre à jour quand de nouvelles billes s'arrêtent.
En reprenant le code précédent, pour chaque bille, on utilise le tableau altitude au lieu de la fonction, et on pense à la mettre à jour.
from lib import *
altitude = []
for x in range(nbMarches()):
altitude.append(hauteur(x))
for _ in range(nbLancers()):
x = 0
while altitude[x] >= altitude[x + 1]:
x += 1
altitude[x] += 1
positionFinale(x)
Dans cette version, on lance plusieurs fois une bille à des positions données différentes, en la retirant du plateau à la fin de son parcours.
Version lente
On reprend le code de la version B, et on l'adapte un peu.
from lib import *
for i in range(nbLancers()):
x = marcheLancer(i)
while hauteur(x) >= hauteur(x + 1):
x += 1
positionFinale(x)
- Objectif
- Ne pas faire de double boucle et répondre instantanément pour chaque requête.
Solution officielle
from lib import *
destinationBille = [nbMarches()-1] * nbMarches()
for iPos in range(nbMarches() - 2, -1, -1):
if(hauteur(iPos) < hauteur(iPos+1)):
destinationBille[iPos] = iPos
else:
destinationBille[iPos] = destinationBille[iPos+1]
for iBille in range(0, nbLancers()):
posBille = marcheLancer(iBille)
positionFinale(destinationBille[posBille])
Reprendre ce code...
Avec un autre style d'écriture.
Réponse
from lib import *
nb_marches = nbMarches()
reponses = [None] * (nb_marches - 1)
for x in range(nb_marches - 2, -1, -1):
if hauteur(x + 1) > hauteur(x):
x_fin = x
reponses[x] = x_fin
for i in range(nbLancers()):
x = marcheLancer(i)
x_fin = reponses[x]
positionFinale(x_fin)
Dans cette version, on lance plusieurs billes successivement, à l'extrémité gauche du plateau (marche 0). À la fin de leur parcours, on laisse les billes là où elles s'arrêtent : elles ajoutent 1 à la hauteur de la marche sur laquelle elles se sont arrêtées.
Solution officielle
posBille = 0
for iBille in range(nbLancers()):
posBille = max(posBille - 1, 0)
while(altitude[posBille] >= altitude[posBille+1]):
posBille += 1
altitude[posBille] += 1
positionFinale(posBille)
Elle est incomplète, il manque une partie.
Reprenez ce code...
Avec un autre style.
Réponse
from lib import *
altitude = []
for x in range(nbMarches()):
altitude.append(hauteur(x))
x = 0
for _ in range(nbLancers()):
while altitude[x] >= altitude[x + 1]:
x += 1
altitude[x] += 1
positionFinale(x)
if x > 0: # si la bille a déjà réussi à avancer jusqu'en x > 0
x -= 1 # elle pourra aller au moins jusqu'en x - 1