Quand vous devez jeter des œufs depuis le toit : problème de codage quotidien

Problème de codage quotidien 24

Bon retour avec un autre problème à résoudre ! Aujourd’hui, nous avons affaire à des œufs tombant des toits avec ce problème vraiment sympa, qui impliquera deux solutions possibles : une assez naïve et une plus intelligente. Ce dernier nous donnera également l'occasion de parler d'un algorithme assez célèbre.

Comme toujours, le problème d'aujourd'hui est fourni par la merveilleuse newsletter Problème de codage quotidien , auquel vous pouvez vous abonner gratuitement pour relever également votre défi de codage quotidien. Vérifiez-le et essayez également de résoudre vos problèmes !

Assez parlé alors ; voyons le problème !

Le problème

Ce problème a été posé par Goldman Sachs lors d'un entretien d'embauche. Voyons le problème.

Vous recevez N œufs identiques et accédez à un bâtiment de k étages. Votre tâche est de trouver l'étage le plus bas qui provoquera la rupture d'un œuf s'il tombe de cet étage. Une fois qu’un œuf se brise, il ne peut plus être laissé tomber. Si un œuf se brise lorsqu'il tombe du xth étage, vous pouvez supposer qu'il se brisera également lorsqu'il tombe d'un étage supérieur à x .

Écrivez un algorithme qui trouve le nombre minimum d'essais nécessaires, dans le pire des cas, pour identifier cet étage.

Par exemple, si N = 1 et k = 5 , nous devrons essayer de laisser tomber l'œuf à chaque étage, en commençant par le premier, jusqu'à atteindre le cinquième étage, notre solution sera donc 5 .

Ainsi, on nous donne des œufs à lancer depuis différents étages d’un immeuble. Nous sommes tristes qu'à partir d'un certain étage (que nous appellerons targetFloor ), les œufs jetés ne se brisent pas en tombant au sol.

De cet étage à tous les étages inférieurs, les œufs ne se briseront pas lorsqu'ils seront jetés par la fenêtre. Ce qu'on nous demande de faire, c'est de trouver une méthode efficace pour trouver le targetFloor .

Comme prévu, nous verrons deux méthodes pour résoudre ce problème : une méthode très simple, qui forcera brutalement la solution, mais elle ne sera pas efficace. Le second sera beaucoup plus efficace et tentera de résoudre le problème en cassant le moins d'étapes possible.

Cela nous donnera également l’occasion de parler d’un algorithme vraiment célèbre et important ; un de ceux qu’il faut savoir faire… en gros n’importe quoi !

Configuration de l'environnement

Pour commencer, nous devons configurer un peu l'environnement, à savoir le bâtiment et le targetFloor . Pour créer le bâtiment, nous créons simplement un tableau contenant les numéros des étages, du rez-de-chaussée jusqu'au nᵗʰ étage. Ensuite, nous générons un nombre aléatoire qui sera notre targetFloor .

Nous allons réécrire ce problème en Go : assez simple pour être lisible, mais suffisamment complexe pour comprendre la mécanique interne.

On crée d'abord le tableau qui nous servira de bâtiment : on peut lui donner la taille que l'on veut, plus la taille est grande, plus le bâtiment sera haut. Après cela, nous créons une instance de targetFlor à l'aide du module math/rand intégré à Go.

En gros, nous créons un nouvel entier aléatoire entre 0 et la hauteur du bâtiment (… la longueur du tableau :D) en utilisant comme source l'heure actuelle.

La solution de force brute

Bien entendu, la solution la plus simple possible serait de jeter chaque œuf à chaque étage, afin de voir à quel étage les œufs commencent à se casser. Puisque nous avons une variable contenant ces informations, on pourrait simplement faire une boucle for pour résoudre le problème :

Bien qu’il s’agisse de la solution la plus simple, elle s’avère malheureusement très inefficace. Imaginez si l'étage de droite est celui du haut : il faut casser 100 000 œufs pour résoudre le problème : ce serait une énorme omelette mais tout un gaspillage !

D’une manière générale, cette solution a une complexité temporelle de O(n) car la complexité de la solution croît linéairement avec la complexité du problème d’entrée. Ce n’est cependant pas la solution la plus efficace à laquelle nous pourrions penser.

Une solution efficace

Réfléchissons alors à une solution efficace. Au lieu de marcher étage par étage pour casser chaque œuf à chaque étage, nous pourrions faire une supposition et, en fonction du résultat de cette supposition, ajuster la supposition suivante.

Voici un exemple : supposons que nous ayons un bâtiment de 10 étages et que le targetFloor soit le 7ème étage (nous ne le savons pas, bien sûr). Nous pourrions faire les suppositions suivantes :

Fondamentalement, nous supposons que le targetFloor est l’étage intermédiaire du bâtiment. Nous jetons l’œuf à partir de là, et les résultats possibles sont au nombre de deux :

• l'œuf se brise, ce qui signifie que nous sommes trop hauts. Nous pouvons écarter l'étage supérieur à celui-ci, inclus, et continuer nos suppositions.

• L'œuf ne se casse pas, ce qui signifie que nous sommes trop bas ou au bon étage. Nous rejetons tous les étages inférieurs à celui-ci, inclus, et

Compte tenu de cela, nous prenons maintenant une autre hypothèse éclairée sur l’étage intermédiaire ou le bâtiment « restant », et appliquons la même stratégie vue ci-dessus. Nous pouvons poursuivre cette approche jusqu’à ce qu’il ne nous reste plus qu’un étage.

Si vous reconnaissez cette approche, vous avez parfaitement raison : il s’agit simplement d’une recherche binaire appliquée à un problème du « monde réel ». La recherche binaire est un algorithme simple et soigné de type diviser pour régner , ce qui signifie qu'à chaque étape, la taille du problème est réduite de moitié jusqu'à ce que nous trouvions la solution.

Cela signifie que cet algorithme, comparé au précédent, est bien plus rapide. Voyons le code !

Examinons plus en profondeur. La fonction de recherche binaire prend 4 arguments :

• overArray , un tableau d'entiers, qui est le bâtiment sur lequel nous effectuons une boucle ;

• bottom , l'index du bas du bâtiment ;

• top , l'index du dernier étage du bâtiment ;

• breakFloor , la variable contenant targetFloor pour vérifier si on peut le trouver dans le bâtiment.

Après cela, on boucle sur le bâtiment tandis que bottom est plus bas que top : en recherche binaire, lorsque les deux arguments de position s'entrelacent et s'échangent, cela signifie que l'élément recherché n'a pas été trouvé.

Par conséquent, si l'algorithme se retrouve dans cette situation, la boucle se termine et nous renvoyons -1 , ce qui signifie que l'élément que nous recherchons n'était pas présent dans le tableau. Si nous recherchons toujours l'élément, nous appliquons ce qui est montré dans l'image ci-dessus.

Nous calculons l'élément middlePoint comme plancher entre bottom et top et nous vérifions si middlePoint == breakFloor . Si c'est le cas, nous renvoyons le middlePoint comme résultat.

Si ce n'est pas le cas, nous ajustons bottom ou top en conséquence : si middlePoint est supérieur à breakFloor , cela signifie que nous sommes trop haut sur le bâtiment, nous réduisons donc notre prédiction en définissant le top étage possible à middlePoint — 1 .

Si middlePoint est plus petit que breakFloor , nous ajustons notre bottom en définissant comme middlePoint+1 .

Maintenant, pour tout vérifier, dans la fonction main , nous générons l'environnement comme avant, et créons une nouvelle variable appelée bsFloor qui contiendra notre résultat.

Pour confirmer que notre algorithme nous a amené au bon résultat, nous imprimons à la fois bsFloor et targetFloor , qui étaient auparavant générés de manière aléatoire.

Complexité temporelle

Comme nous l’avions prévu précédemment, cet algorithme est bien plus rapide que l’algorithme linéaire. Puisque nous réduisons de moitié le bâtiment à chaque étape, nous pouvons trouver le bon étage dans log₂(n) où n est égal à len(building) .

Cela signifie que la complexité temporelle de cet algorithme est O(log(n)) . Pour vous donner une comparaison entre la solution linéaire et cette dernière, si le bâtiment a 100 étages, l'algorithme linéaire prend dans le pire des cas 100 itérations, tandis que l'algorithme de recherche binaire prend log₂100 = 6,64, donc 7 itérations.

Aussi, cette dernière est de plus en plus efficace que la linéaire car plus le bâtiment s'agrandit, plus la recherche binaire est efficace. Pour un bâtiment de 1.000.000.000 d'étages, le linéaire prend 1.000.000.000 pas, tandis que le binaire prend log₂1.000.000.000 = 29,9, donc 30 pas. Une énorme amélioration!

Conclusion

Ça y est ...! J'espère que vous avez apprécié l'article autant que j'ai eu du plaisir à essayer de résoudre le défi ! Si c'est le cas, laissez un applaudissement ou deux, ce serait un grand soutien ! Si vous aimez ce type d'articles et souhaitez en voir plus, suivez la page car je publie ce type de contenu chaque fois que je le peux.

Enfin, si vous avez trouvé cet article intéressant ou utile et que vous souhaitez y contribuer en offrant un café, n'hésitez pas à le faire sur mon Kofi page!

Et comme toujours, merci d'avoir lu!

Nicolas

Également publié ici