Rabbit in the hole: solution d'un problème d'algorithme

Je suis récemment tombé sur cette vidéo : Coding interview with Dan Abramov où le créateur de Redux se prête au jeu d'une fausse interview par le Youtubeur Ben Awad. Durant cette interview, une question d'algorithmie lui est posée et comme ce genre de challenge m'émoustille, je me prête ici au jeu de vous en proposer la question et une solution.

Note : cet énoncé semble être une version à 100 trous du problème dit "Fox in the hole" attribué à K. Rustan M. Leino de chez Microsoft Research. J'aurais bien aimé vous citer ici l'auteur de façon certaine, mais comme tout classique, son attribution se perd dans l'histoire ! Le problème original se présente avec 5 trous.

Soit 100 trous alignés et un lapin qui se cache aléatoirement dans l'un de ces trous. Vous ne pouvez regarder que dans un seul trou à la fois - n'importe lequel - mais à chaque fois que vous le faites, le lapin saute dans un trou adjacent.

Quelques précisions techniques :

• Les actions du lapin sont considérées comme aléatoires. Nous ne ferons pas les malins en inférant le caractère aléatoire ou pseudo-aléatoire de celles-ci
• Le lapin se trouve en position l, inconnu à l'instant t. Nous vérifions le trou à l'index x.
• L'ordre des actions est le suivant :
  • nous vérifions un trou à l'index x
  • si le lapin si trouve, nous gagnons
  • si le lapin (en position k ≠ x) ne s'y trouve pas, il saute aléatoirement en k-1 ou k+1

Je vais dans ce paragraphe utiliser quelques lettres et symboles mathématiques pour représenter et décrire mon propos. Ne soyez pas effrayés : c'est paradoxalement moins compliqué et moins long qu'en le racontant avec des mots ! Si les mathématiques ne vous intéressent pas, je vous invite à sauter directement à la solution !

Quelques prérequis

La première chose sur laquelle nous devons nous mettre d'accord est la définition de la parité. J'entends par là de savoir si un nombre est pair ou impair, c'est à dire s'il est divisible par 2. Un nombre pair peut nécessairement s'écrire sous la forme 2k avec k ∈ ℕ, c'est à dire un nombre entier positif. Un nombre impair au contraire s'écrit sous la forme 2k+1.

La seconde chose est que par définition, la parité de deux nombres consécutifs s'inverse. C'est à dire qu'un nombre impair suit toujours un nombre pair et vice-versa.

De là, nous pouvons démontrer que peu importe le nombre n, n+2 est de même parité que n.

Soit n un nombre pair n = 2k, alors n+2 = 2k+2 = 2(k+1) s'écrit sous forme 2x avec x=k+1, donc n+2 est pair.
Soit n un nombre impair n = 2k+1, alors n+2 = 2k +1+2 = 2(k+1) +1 s'écrit sous forme 2x+1 avec x=k+1, donc n+2 est impair.

En étendant cette réflexion, deux nombres dont la différence est paire sont de même parité. Alors si n est pair, n+2x est pair. Et si n est impair, n+2x est impair.

Soit un nombre pair n = 2k, alors n+2x = 2k+2x = 2(k+x) est pair.
Soit un nombre impair n = 2k+1, alors n+2x = 2k +1+2x = 2(k+x)+1 est impair.

Démonstration mathématique

Notons N le nombre de trous.
Notons p la position du lapin.
Notons i l'index du trou que l'on vérifie à l'instant.

Considérons la procédure suivante : les trous sont testés successivement dans l'ordre, du premier au dernier. Ainsi, si l'on teste le trou i, le prochain testé sera i+1, jusqu'à N le nombre de trous.

Au début de chaque étape de la procédure, lorsque nous nous apprêtons à vérifier le i^ème trou, trois scénarios sont possibles :

1. Si p=i : le lapin est dans le trou.
2. Si p0 et i0 était de même parité : alors p et i le sont toujours (cf prérequis).
3. Si p0 et i0 était de parité différente : alors p et i sont toujours de parité différente (cf prérequis).

Cas 1: p=i

Le lapin est dans le trou... rien à dire, la partie est finie !

Cas 2: p=i+2x

Nous avons commencé la partie sur des trous de même parité, nous sommes donc toujours sur des trous de même parité (cf prérequis) et nous avons donc p=i+2x avec un x inconnu. Si le lapin est derrière nous (x<0), nous ne trouverons jamais le lapin, c'est évident.
Si le lapin est devant nous (x>0) alors nous avons deux options :

• Si le lapin passe au trou p+1 :
  Alors nous ne le trouverons pas au prochain tour car il fuit. Cependant, comme il y a un nombre fini N de trous, le lapin ne pourra pas toujours fuir. Il fera nécessairement demi-tour à un moment où un autre.
• Si le lapin passe au trou p-1 :
  Alors au prochain tour nous trouvons le lapin uniquement dans s'il sont dans le même trou, c'est à dire si p-1 = i+1.
  Comme p=i+2x, nous ne trouverons le lapin que si i+2x-1 = i+1. Et cette condition n'est vraie que pour x=1
  En d'autres termes, si le lapin se trouve deux trous devant nous au début de ce tour et qu'il saute dans notre direction, nous le trouverons nécessairement au prochain tour. Et ce scénario arrivera forcément dans ce cas 2, car le lapin ne peut pas fuir éternellement.

Ce que nous venons de montrer c'est que notre procédure débusquera nécessairement le lapin si en début de partie il se trouve à un nombre pair de trous de nous.

Cas 3: p=i+2x+1

Dans ce cas-ci, nous n'avons pas commencé la partie sur des trous de mêmes parités. Ainsi à tout instant, p=i+2x+1 (cf prérequis). Tout comme précédemment :
Si le lapin est derrière nous (x<0), nous ne trouverons jamais le lapin, c'est évident.
Si le lapin est devant nous (x>0) alors nous avons deux options :

• Si le lapin passe au trou p+1 : le raisonnement est le même qu'au cas 2.
• Si le lapin passe au trou p-1 :
  Alors au prochain tour nous trouvons le lapin uniquement s'ils sont dans le même trou, c'est à dire si p-1 = i+1.
  Comme p=i+2x+1, nous ne trouverons le lapin que si i+2x+1-1 = i+1. Et cette condition n'est vraie que pour 2x=1. Ce n'est pas possible avec x entier. Cela montre que nous ne trouverons jamais le lapin car nous ne pouvons matériellement jamais nous trouver dans le même trou au moment où nous regardons dedans !

Ce que nous venons de montrer c'est que notre procédure loupera toujours le lapin si en début de partie il se trouve à un nombre impair de trous de nous.

Fort de toutes les observations et démonstrations du chapitre précédent, nous pouvons à présent construire un algorithme solide.

Parcourons les trous de l'index 0 à 100. Nous savons par le cas 2 que si le lapin se trouve sur un trou pair {0, 2, 4..., 98} nous le trouverons forcément. Comme nous commençons au premier trou possible, il ne peut pas être derrière nous en début de partie et nous avons montré qu'en avançant ainsi, nous le débusquerons forcément.

Si - ayant vérifié le dernier trou - nous n'avons pas trouvé notre lapin, nous savons maintenant qu'il se trouve sur un trou de parité différente de la nôtre, donc sur un trou impair, c'est à dire {1, 3, 5... 99}. En recommençant le procédure une seconde fois, mais depuis le trou 1 cette fois-ci, nous savons que nous nous trouvons maintenant sur un trou impair tous les deux, et donc encore une fois par notre démonstration précédente, que nous le trouverons.

En conclusion, voici l'algorithme de résolution que je vous propose.

Pour start variant de 0 à 1:
|  Pour i variant de start à N:
|  |  Vérifier le trou i:
|  |  |  - si le lapin s'y trouve:
|  |  |    |  => fin du jeu "Le lapin est dans le trou i"
|  |  |  - sinon continuer

Cet algorithme - dans le pire des cas - va parcourir l'ensemble des N trous deux fois. Pour chaque trou, un ensemble fini et constant d'opération est effectué (la vérification du trou et le lapin qui saute à sa prochaine position).

La complexité d'un tel algorithme est donc notée O(2N)
(prononcer grand-O de deux N)

Limitations

Notre algorithme repose sur un certain nombre de limitation qu'il convient d'avoir compris :

• Le monde est fini : il y a un nombre fini de trou, le lapin ne peut donc pas éternellement nous fuir
• Les sauts du lapin ne sont pas aléatoires : nous connaissons son mode de déplacement
• Les déplacements sont adjacents dans un monde à une seule dimension : les positions des trous suivent donc une loi de parité connue sur laquelle repose notre algorithme.
• Le monde a une seule dimension, non repliée : il n'y a pas de boucle possible. Le monde n'est ni un enchevêtrement (graphe) de tunnel souterrain, ni un cercle

Vous avez une meilleure solution ou des remarques ?
Laissez un commentaire !