Eine mittelschwere Herausforderung meistern

In meinem vorherigen Beitrag habe ich mich der Herausforderung gestellt, ein Problem von leetcode.com zu lösen, um zu beweisen, dass Low-Code mehr als nur eine Lösung in einer Form ist – es bietet die nötige Flexibilität, um auch die schwierigeren technischen Probleme zu lösen. Ich habe mich für Two Sum entschieden, die erste Herausforderung auf der Website und eine der „einfachen“ Herausforderungen (alles dazu könnt ihr hier nachlesen).

Dieses Mal werde ich mich an etwas Schwierigeres wagen: Herausforderung elf – „Behälter mit dem meisten Wasser„“ – eine Herausforderung mittleren Schwierigkeitsgrades. Bei diesem Problem geht es darum, anhand einer Reihe von Säulenhöhen herauszufinden, welches Säulenpaar einen Behälter bildet, der das meiste Wasser aufnehmen kann oder den größten rechteckigen Bereich zwischen ihnen aufweist.

„Behälter mit dem meisten Wasser“ – Wo soll ich anfangen?

Bei der letzten Herausforderung haben wir die Herausforderung zunächst für bare Münze genommen und sie auf Augenhöhe angegangen, indem wir einen möglichst einfachen Ansatz verwendet und uns dann damit befasst haben, wie dies mit Low-Code erfolgen sollte. Diesmal überspringen wir das und gehen dieses Problem direkt mit Low-Code an.

Zunächst benötigen wir einige Daten. Wir erstellen eine Entität, in der wir unser Ergebnis speichern, und eine untergeordnete Entität, in der wir die „Turm“-Daten erstellen:

Dadurch haben wir Platz, um eine Reihe von Werten zufällig zu generieren, sie in einer festgelegten Reihenfolge zu platzieren und sie irgendwo zu gruppieren, um die Ergebnisse unserer Versuche zu speichern. Bevor wir jedoch zufällig einen Datensatz generieren, wäre es am besten, eine Liste von Werten basierend auf dem Beispiel zu erstellen. Dies in Low-Code zu tun, ist nicht besonders elegant, aber unkompliziert: Wir erstellen einfach jedes Element einzeln, verknüpfen es mit dem Versuch und geben unsere Entität „Versuch“ zurück.

Das ist nicht schön, aber es bringt uns ans Ziel. Das Diagramm rechts wird aus den Daten erstellt, die wir gerade erstellt haben.

Erster Versuch – rohe Gewalt

Wir beginnen mit einem Brute-Force-Versuch. Wir können sicher sein, dass dies nicht die beste Lösung sein wird, aber es lohnt sich immer, die richtige Antwort für ein gegebenes Array zu finden, damit wir unsere Antwort überprüfen können, wenn wir zu einer effizienteren Version übergehen. Dazu verwenden wir eine verschachtelte Schleife: Die erste Schleife durchläuft alle Türme und die zweite jeden Turm, der dem aktuellen Iterator in der äußeren Schleife folgt.

Wie Sie am Mikrofluss sehen können, handelt es sich um eine O(n2)-Effizienz, also nicht großartig, aber lassen Sie uns überprüfen, ob die richtige Antwort dabei herauskommt.

Wie wir aus der Ergebnistabelle ersehen können, haben wir es geschafft, die richtige Schlussfolgerung zu ziehen. Das ist großartig. Im nächsten Schritt wollen wir sehen, ob wir es effizienter machen können.

Nächster Versuch – auf zur Effizienz

Dazu müssen wir den besten und schnellsten Weg finden, diesen Container zu finden. Und ähnlich wie in unserem letzten Beispiel müssen wir dazu Zeiger verwenden.
Wir beginnen an beiden Enden und bewegen uns nach innen, wobei wir den höchsten Turm des Paares behalten und den anderen Zeiger bewegen. Wir müssen jedes Volumen prüfen und ein Protokoll führen, damit wir es dann sortieren können, um das größte Volumen zu finden. Indem wir auf diese Weise iterieren, bewegen wir uns von der Prüfung der größten Breite zur größten Höhe und prüfen alle besten Kombinationen zur Berechnung des Volumens.

Dazu werden wir einen Mangel der letzten Übung beheben. Mendixerlaubt standardmäßig nicht, ein Element einer im Arbeitsspeicher befindlichen Liste über seinen Index abzurufen. Sie können dies problemlos tun, wenn Sie es aus der Datenbank abrufen, aber das wäre nicht sehr effizient. Um dies zu korrigieren, können wir eine einfache Java-Aktion erstellen:

Erweiterung der Funktionalität in Mendix mit Java-Aktionen

Einer der echten Pluspunkte für Mendix ist, dass Sie durch die Plattform nicht nur auf die Tools in der Toolbox beschränkt sind. Sie können die Funktionalität schnell und einfach erweitern, indem Sie entweder etwas vom Marktplatz nehmen oder Ihre eigene benutzerdefinierte Java-Aktion erstellen! In unserem Fall ist es ganz einfach, diese Funktion zu erstellen, eine Liste und dann einen Index zu übergeben und dann das entsprechende Objekt zurückzugeben.

Jetzt können wir Zeiger wie in den meisten Programmiersprachen beim Zugriff auf Listen verwenden. Für einen effizienten Durchgang benötigen wir zwei ganzzahlige Zeiger, um unsere Prüfungen von beiden Enden aus zu verfolgen, und eine Liste, in die wir unsere Ergebnisse eintragen.

Dann starten wir eine While-Schleife und iterieren weiter, bis unsere beiden Zeiger auf einen einzigen Turm treffen. An diesem Punkt wissen wir, dass wir aufhören müssen. Innerhalb dieser Schleife holen wir uns den Turm für jeden Zeiger und berechnen das Volumen, das zwischen den Türmen liegen könnte. Während wir die Schleife durchlaufen, behalten wir auch das größte Volumen im Auge, das wir in den Attributen gefunden haben, die wir zuvor in der Attempt-Entität hinzugefügt haben. Auf diese Weise wissen wir, welches das größte Volumen ist und welche beiden Türme dieses Volumen bilden.

Bevor wir die Schleifeniteration beenden und zur nächsten übergehen, prüfen wir, welcher der beiden Türme, die wir gerade verglichen haben, höher ist. Wenn es Turm eins ist, verkleinern wir Zeiger zwei, wenn es Turm zwei ist, vergrößern wir Zeiger eins. Dadurch werden die Zeiger zusammengeführt, bis sie sich am selben Turm treffen und unsere Escape-Klausel für While-Schleifen erfüllen. Das Ganze sieht so aus …

Die Ergebnisse der Effizienzbemühungen

Ein paar Commits am Ende, um unsere Versuche zu verfolgen, und wir sind fertig. Dann können wir den neuen Prozess ausführen und die Ergebnisse sehen:

Hier sehen wir, dass wir in nur sechs Versuchen zum richtigen Ergebnis gekommen sind, statt in den 36 Versuchen, die wir mit der Brute-Force-Methode benötigten. Das bedeutet, dass eine weitere Herausforderung erfolgreich mit Low-Code bewältigt wurde, wobei nur ein kleiner Teil Code hinzugefügt wurde, um das Leben ein wenig einfacher zu machen.