Relever un défi de difficulté moyenne

Dans mon article précédent, j'ai relevé le défi de résoudre un problème sur leetcode.com pour prouver que le low-code est bien plus qu'une simple solution à formulaire unique : il possède la flexibilité nécessaire pour résoudre même les problèmes techniques les plus difficiles. J'ai choisi Two Sum, le premier défi du site et l'un des défis « faciles » (vous pouvez tout lire à ce sujet ici).

Cette fois-ci, je vais m'attaquer à quelque chose d'un peu plus délicat : le défi onze – «Récipient avec le plus d'eau" – un défi de difficulté moyenne. Ce problème consiste à prendre un ensemble de hauteurs de colonnes et à déterminer quelle paire de colonnes forme un récipient qui pourrait contenir le plus d'eau ; ou qui a la plus grande surface rectangulaire entre elles.

« Récipient contenant le plus d’eau » – Par où commencer

Dans le dernier défi, nous avons commencé par accepter le défi à sa juste valeur et l'avons abordé sur un pied d'égalité, en utilisant une approche aussi basique que possible, puis en nous penchant sur la manière dont cela devrait être fait en low-code. Nous allons ignorer cela cette fois-ci et passer directement à la résolution de ce problème en low-code.

Tout d'abord, nous avons besoin de quelques données. Nous allons créer une entité pour stocker notre résultat et une entité enfant pour créer les données de la « tour » :

Cela nous donnera un espace pour générer aléatoirement une série de valeurs et les placer dans un ordre défini et un endroit pour les regrouper afin de stocker les résultats de nos tentatives. Avant de générer aléatoirement un ensemble de données, il serait préférable de créer une liste de valeurs basée sur l'exemple. Faire cela en low-code n'est pas particulièrement élégant mais c'est simple : nous créons simplement chaque élément un par un, le lions à la tentative et renvoyons notre entité « Tentative ».

Ce n'est pas joli, mais cela nous amène là où nous devons être. Le graphique de droite est généré à partir des données que nous venons de créer.

Première tentative – force brute

Nous allons commencer par une tentative de force brute. Nous pouvons être sûrs que ce ne sera pas la meilleure solution, mais cela vaut toujours la peine de trouver la bonne réponse pour un tableau donné afin de pouvoir vérifier notre réponse lorsque nous passerons à une version plus efficace. Pour ce faire, nous utiliserons une boucle imbriquée : la première boucle parcourt toutes les tours et la seconde chaque tour qui suit l'itérateur actuel dans la boucle externe.

Comme vous pouvez le voir à partir du Microflow, il s'agit d'une efficacité O(n2), pas géniale, mais vérifions qu'elle donne la bonne réponse.

Comme nous pouvons le constater dans le tableau des résultats, nous sommes parvenus à la bonne conclusion. C'est formidable. L'étape suivante consiste à voir si nous pouvons le faire de manière plus efficace.

Prochaine tentative : visons l'efficacité

Pour ce faire, nous devrons déterminer quel est le moyen le plus rapide de trouver ce conteneur et, tout comme dans le dernier exemple que nous avons fait, il s'agit d'utiliser des pointeurs.
Nous commencerons aux deux extrémités et nous déplacerons vers l'intérieur en gardant la tour la plus haute de la paire et en déplaçant l'autre pointeur. Nous devrons vérifier chaque volume et conserver un journal afin de pouvoir ensuite le trier pour trouver le plus grand volume. En itérant de cette manière, nous passons de la vérification de la plus grande largeur à la plus grande hauteur et nous vérifions toutes les meilleures combinaisons pour calculer le volume.

Pour ce faire, nous allons remédier à une lacune du dernier exercice. Mendix, par défaut, ne permet pas de récupérer un élément d'une liste en mémoire par son index. Vous pouvez facilement le faire lors de l'extraction depuis la base de données, mais cela ne serait pas très efficace. Pour corriger cela, nous pouvons créer une action Java simple :

Extension des fonctionnalités dans Mendix avec des actions Java

L'un des véritables points positifs pour Mendix c'est que vous n'êtes pas limité par la plateforme aux seuls outils de la boîte à outils. Vous pouvez rapidement et facilement étendre les fonctionnalités en récupérant quelque chose sur le marché ou en créant votre propre action Java personnalisée ! Dans notre cas, il est assez simple de créer cette fonction, de passer une liste, puis un index, puis de renvoyer l'objet approprié.

Nous pouvons maintenant utiliser des pointeurs comme vous le feriez dans la plupart des langages de programmation pour accéder à des listes. Pour un passage efficace, nous aurons besoin de deux pointeurs entiers, pour suivre nos vérifications des deux côtés, et d'une liste dans laquelle placer nos résultats.

Ensuite, nous allons démarrer une boucle While et nous continuerons à itérer jusqu'à ce que nos deux pointeurs se rencontrent sur une seule tour, moment auquel nous saurons qu'il faut s'arrêter. Dans cette boucle, nous obtiendrons la tour pour chaque pointeur et calculerons le volume qui pourrait être contenu entre les tours. Au fur et à mesure que nous parcourons la boucle, nous garderons également une trace du plus grand volume que nous avons trouvé dans les attributs que nous avons ajoutés plus tôt dans l'entité Attempt. De cette façon, nous saurons quel est le plus grand volume et quelles sont les deux tours qui créent ce volume.

Avant de terminer l'itération de la boucle et de passer à la suivante, nous allons vérifier laquelle des deux tours que nous venons de comparer est la plus haute. Si c'est la tour 1, nous réduirons le pointeur 2, si c'est la tour 2, nous augmenterons le pointeur 1. Cela fait entrer les pointeurs jusqu'à ce qu'ils se rencontrent à la même tour et satisfassent notre clause d'échappement de boucle While. Tout cela ressemble à ceci…

Les résultats des tentatives d'efficacité

Quelques commits à la fin pour suivre nos tentatives et nous avons terminé. Nous pouvons alors exécuter le nouveau processus et voir les résultats :

Ici, nous pouvons voir que nous sommes parvenus à la bonne conclusion en seulement six tentatives au lieu des trente-six tentatives nécessaires avec l'approche par force brute. Cela signifie qu'un autre défi a été relevé avec succès en low-code, avec l'ajout d'une petite quantité de code juste pour rendre la vie un peu plus facile.