Indice d'une panne⚓︎
Une sonde interroge à intervalles réguliers l'état de fonctionnement d'un système électronique. Celui-ci peut être en marche ou en panne.
La sonde est programmée pour enregistrer les résultats de ses requêtes dans un log. Il s'agit d'un tableau de booléens (une list Python) dans lequel les valeurs True précèdent les False. La valeur True indique que le système est en marche, False qu'il est en panne.
Une panne nécessite une intervention humaine et ne peut donc pas disparaître seule : elle persiste jusqu'à la fin de l'enregistrement.
# 0 1 2 3 4
log = [True, True, False, False, False]
Lors d'une vérification on constate que le système est en panne : le log contient au moins une valeur False en dernière position. On se demande à quel moment a débuté cette panne.
Dans l'exemple précédent, le premier False est à l'indice 2 : la panne a débuté à l'instant 2.
Écrire la fonction indice_panne qui prend en paramètre le tableau de booléens log et renvoie l'instant du démarrage de la panne.
On garantit que le log n'est pas vide et que, au moment de la vérification, le système est en panne (la dernière valeur du tableau est False).
Attention
La panne du système a aussi corrompu le fichier de log. Vous ne pouvez pas lire plus de 500 valeurs dans celui-ci. Passé ce nombre de lectures, tout nouvel accès lèvera une erreur.
Il est donc important de bien concevoir votre algorithme car les logs utilisés dans les tests secrets peuvent être très longs : un milliard de valeurs !
Exemples
>>> indice_panne([True, False])
1
>>> indice_panne([False, False, False])
0
>>> indice_panne([True] * 10 + [False] * 100)
10
>>> indice_panne([True, True, False, False, False])
2
def indicepy-undpanne(log):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert indicepy-undpanne([True, False]) == 1bksl-nlassert indicepy-undpanne([False, False, False]) == 0bksl-nlassert indicepy-undpanne([True] py-str 10 + [False] py-str 100) == 10bksl-nlassert indicepy-undpanne([True, True, False, False, False]) == 2bksl-nlbksl-nldef indicepy-undpanne(log):bksl-nl if not log[0]:bksl-nl return 0bksl-nlbksl-nl debut = 0bksl-nl fin = len(log) - 1bksl-nlbksl-nl while debut <= fin:bksl-nl milieu = (debut + fin) // 2bksl-nl if log[milieu - 1] and not log[milieu]:bksl-nl return milieubksl-nl elif not log[milieu]:bksl-nl fin = milieu - 1bksl-nl else:bksl-nl debut = milieu + 1bksl-nlbksl-nl
A
On utilise une recherche dichotomique itérative.
Il est aussi possible de procéder de manière récursive en introduisant des paramètres :
-
debutdésigne l'indice inclus du début de la zone de recherche dans le log, -
findésigne l'indice exclu de la fin de la zone de recherche dans le log.
Afin de ne pas surcharger le premier appel indice_panne(log), on donne des valeurs par défaut à ces paramètres.
def indice_panne(log, debut=None, fin=None):
if debut is None:
debut = 0
fin = len(log)
if not log[debut]:
return debut
milieu = (debut + fin) // 2
if log[milieu - 1] and not log[milieu]:
return milieu
elif not log[milieu]:
return indice_panne(log, debut, milieu)
else:
return indice_panne(log, milieu + 1, fin)
On notera que dans cette version l'indice de fin de la zone de recherche est exclu de celle-ci. La recherche dans la zone (debut, fin) s'apparente alors au fonctionnement classique de la fonction range(debut, fin) : la valeur debut est incluse alors que fin est exclue.
Z
Astuce (1)
Il s'agit d'une recherche dans un tableau trié : les valeurs True sont au début, les False à la fin.
Astuce (2)
Si le log ne contient que des valeurs False, il faut renvoyer 0.
Dans le cas contraire, l'indice cherché est l'unique indice i qui vérifie log[i - 1] and not log[i].