Am 29.07.2017 um 09:15 schrieb tomas@tuxteam.de:

On Sat, Jul 29, 2017 at 12:28:26AM +0200, Urs Liska wrote:

> Am 28.07.2017 um 23:31 schrieb tomas@tuxteam.de:

[...]

>> Ich habe mir die mal angeschaut. Ich nehme mal an, die ist:
>>
>> 02-data-structures/06-binary-search-trees/is_bst/is_bst.py

> Ja.
> Allerdings ist die bereits im master-Branch, was bedeutet, dass die
> Aufgabe schon erfolgreich absolviert wurde (inzwischen, d.h. seit meinem
> ersten Post).

Congrats :)

>> Bei der Methode is_bst(self, indeex=0) stehe ich noch auf der
>> Leitung: was soll die Methode als Rückgabewert liefern?
>> Ich meine: was für eine Art Objekt?
>>
>> Wenn ich nicht ganz auf der Leitung stehe, dann vermute ich
>> hier den Knoten :-)

> Das ist in der Tat recht kryptisch und hätte wohl eine bessere
> Kommentierung verdient. Dann hätte ich auch den (allerdings
> konsequenzlosen) Fehler bemerkt ...

+1

> Der Rückgabewert der rekursiven Funktion ist eine Liste mit den
> Randwerten der linken und rechten Kinder und dem aktuellen Knoten in der
> Mitte. "Natürlicher" wäre die Rückgabe von "left + [index] + right",

OK. Darauf wäre ich allerdings nicht gekommen, zumal is_bst einem das
Hirn schon auf ein boolean "polt" (is this thing a binary search tree?).

Grrr, das muss ich zugeben. Die Funktion sollte anders heißen.
Im Wesentlichen ist es so, dass der Baum in seiner natürlichen Ordnung durchlaufen wird. Sofern eine Fehlerbedingung festgestellt wird, bricht sie ab, andernfalls läuft sie durch und gibt "irgendwas" zurück - dann ist der Baum korrekt.

Semantisch richtig wäre wohl

def main():
    tree = TreeOrders()
    if len(tree.nodes) == 0:
        print("CORRECT")
    tree.traverse()
    print("CORRECT")

Das verführt einem dazu, sich diese "Frage" rekursiv vorzustellen

is_bst(tree):
    return tree.left.val < tree.val \
       and tree.val < tree.right.var \
       and is_bst(tree.left) \
       and is_bst(tree.right)

(das ist natürlich salopp formuliert, bei Deiner Darstellung des Baums
müssen eher solche Dinge stehen wie

    self.value(self.left(index)) < self.value(index) ...

bzw.

    is_bst(self.left(index))...

... you get the idea. Man muss natürlich damit klarkommen, dass diese
Methoden manchmal None liefern, was den Ausdruck etwas unübersichtlich
macht (bei den Vergleichen).

Ich glaube nicht, dass das funktionierten würde. Wenn ich an einem gegebenen Knoten für links und rechts nur einen Boolean-Wert zurückbekomme, kann ich nicht mit dem aktuellen Knoten vergleichen (wie du unten auch schreibst). Daher muss die rekursive Funktion schon die Knoten-Werte des Subtrees zurückgeben.

Anders als bei Deinem Ansatz muss man also nicht "mittendrin"
herausspringen (d.h. fail()), sondern das Ergebnis entsteht rekursiv. Im
Fehlerfall ist das "Herausspringen" schneller, natürlich.

> wodurch rekursiv eine Liste mit dem gesamten Inhalt des Baums in
> natürlicher Ordnung entsteht. Diese Liste kann allerdings recht lang
> werden und kostet offensichtlich zu viel Rechenzeit.

> Falsch ist, dass das mittlere Element nicht "[index]" sein dürfte,
> sondern der tatsächliche Schlüsselwert, nämlich "[self.value(index)]".
> Da dieser mittlere Wert aber überhaupt nicht gebraucht wird, ist der

Das verstehe ich nicht: der mittlere Wert muss doch zwischen den linken
und den rechten liegen, damit der Baum sortiert ist? Muss man das nicht
auch prüfen?

Ja, natürlich. Am gegebenen Knoten muss ich prüfen, ob der höchste Wert des linken Teilbaums kleiner als und der niedrigste Wert des rechten Teilbaums größer als der aktuelle Wert ist. Nach oben weitergeben muss ich aber nur den niedrigsten und größten Wert des sich ergebenden Teilbaums, damit der nächsthöhere Knoten ebendiesen Vergleich anstellen kann. Der Wert des aktuellen Knotens wird überhaupt nicht weiter verwendet, und deswegen ist es auch nicht aufgefallen, dass ich hier den Index statt des Werts weitergegeben habe.
Ich glaube, ich probiere das nochmal zu korrigieren (auch wenn die Aufgabe ja schon offiziell akzeptiert wurde.

> Fehler nicht aufgefallen. DIESE Aufgabe ist also inzwischen erfolgreich
> gelöst.

Bestens. Hängst Du noch irgendwo?

Ja, wie gesagt habe ich offene Fragen auf dem Issue-Tracker abgelegt (ich habe das Repository jetzt doch auch öffentlich sichtbar gemacht): https://git.openlilylib.org/uliska/algorithms-and-datastructures/issues

Im Moment sind es zwei unterschiedlich geartete Fragen:
1)
Bei der Aufgabe, Substrings zu hashen, komme ich einfach nicht über einen Testfall hinweg, bei dem der Algorithmus zu lange braucht. Hier muss es entweder eine Optimierung geben, die ich nicht gefunden habe (z.B. dass unnötig String-Kopien erzeugt werden oder es eine unnötige Schleife gibt) oder einen Sonderfall, der meinen Algorithmus in die Ecke (bzw. in einen Kreis) treibt):
https://git.openlilylib.org/uliska/algorithms-and-datastructures/issues/3

2)
Bei der Frage, ob ein Graph bipartit ist, scheitere ich an einer "falschen Antwort". Hier muss ich sagen, dass mir die Implikationen der Aufgabe noch etwas schwammit sind und mein Ansatz daher vielleicht zu naiv ist. Ich suche per Breitensuche nach erreichbaren Knoten und färbe alle Nachbarn eines Knotens mit der "anderen" Farbe ein. Wenn ich auf einen Knoten stoße, der bereits entdeckt wurde, aber dieselbe Farbe wie ein aktueller Knoten hat, erkenne ich den Graphen als nicht bipartit.
Bei allen angegebenen Beispiel-Eingaben funktioniert das auch, aber der Grader weist einen (mir unbekannten) Test-Fall ab.

Es gibt noch ein paar weitere Aufgaben, die ich noch nicht gelöst habe, aber die sind noch in dem Stadium, in dem ich versuche, alleine klarzukommen (wie schon gesagt: Es geht mir ja nicht darum, die Aufgaben zu bestehen und das Zertifikat zu bekommen, sondern darum, die Sachen zu verstehen).

HG
Urs

lg
-- t

> _______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de > Mailingliste verwalten (u.a. abbestellen): https://lug-freiburg.de/mailman/listinfo/flug

--
ul@openlilylib.org
https://openlilylib.org
http://lilypondblog.org