staging.inyokaproject.org

Hallo zusammen,

ich schreibe in Python ein kleines Programm und habe irgendwie ein Brett vor dem Kopf. Daher die Denkaufgabe mit freundlicher Bitte um Mithilfe:

Ein Stack soll punktgenau befüllt werden. Sowohl der Stack, als auch die darin verstauten Elemente haben eine variable Größe, die vom Nutzer bestimmt werden können.

Ich generiere also in meinem Programm einen Speicher bzw. Stack. Dieser hat eine frei wählbare minimale und eine frei wählbare maximale Länge. Aus dieser Menge wird dann eine random Zahl gewählt. Beispiel: Angabe 1: min_lenth = 5 Angabe 2: max_length = 10 Das Programm ermittelt via random(5, 10) die length, z.B.: length == 7.

Der Wert quota gibt die Auslastung an und ist zu Beginn == 0 und addiert die folgenden Elemente, die in den Stack verschoben werden und ebenfalls eine variable Größe besitzen: Angabe 3: min_elem_length = 2 Angabe 4: max_elem_length = 4 Beispiel: Das Programm ermittelt via random(1, 4) fortlaufend Elemente (element), z.B.: 3, 3, 4, 2, 2, 1, 3, usw.

Diese Elemente sollen nun genau in meinen Speicher passen. Die letzten n Elemente (so wenige wie möglich) dürfen dabei eine variable Länge besitzen, die jedoch im Bereich von min_elem_length und min_elem_length liegen muss.

Beispiel: Length == 7, quota == 0 element0 = 2, daher quota == 2 element1 = 4, daher quota == 6 element3 muss daher 1 sein und alles passt. 😀

Meine Code sieht aktuell so aus:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

###### Function
def fill_the_stack(min_lenth, max_length, min_elem_length, max_elem_length):
    
    stack = []
    
    length = random.randint(min_lenth, max_length)
    print("Length == ", length)
    
    quota = 0
    while quota < length:                
        
        if (quota - max_length) >= max_elem_length:
            element = quota - max_length
        else:
            element = random.randint(min_elem_length, max_elem_length)
        
        quota += element
        stack.append(element)
        print("Quota:", quota, "\tAdded: +", element)
        
    print(stack)


######

min_lenth = 5
max_lenth = 10
min_elem_length = 3
max_elem_length = 7

fill_the_stack(min_lenth, max_length, min_elem_length, max_elem_length)

Trotzdem kommen hier (natürlich) auch immer wieder Werte raus, die length übersteigen. Mir fallen hier sehr, sehr viele schlechte Workarounds ein. Daher die Frage: Hat jemand hier im Forum vielleicht eine prägnante Idee, wie man length punktgenau befüllt? Ich kann mir irgendwie nicht vorstellen, dass ich der Erste bin, der dieses Problem hat... Von daher: Da gibt's doch sicher eine Lösung? ☺

Tausend Dank und VG! jaik

jAIk schrieb:

Diese Elemente sollen nun genau in meinen Speicher passen. Die letzten n Elemente (so wenige wie möglich) dürfen dabei eine variable Länge besitzen, die jedoch im Bereich von min_elem_length und min_elem_length liegen muss.

Du meinst vermutlich "im Bereich von min_elem_length und max_elem_length". Aber was bedeutet "variable Länge"?

Beispiel: Length == 7, quota == 0 element0 = 2, daher quota == 2 element1 = 4, daher quota == 6 element3 muss daher 1 sein und alles passt. 😀

Meine Code sieht aktuell so aus: [...]

Ansonsten habe ich verstanden:

• Was Du "length" nennst, ist die zu erreichende Summe aller Werte auf dem Stapel.

• Der Stapel soll mit Werten im Intervall [min_elem_length, max_elem_length] gefüllt werden.

Verstehe ich das richtig?

An Deinem Programm fällt mir als erstes auf, dass es keine Prüfung gibt, ob "min_elem_length" größer ist als "max_length" oder "length". In beiden Fällen ist die Aufgabe nämlich nicht zu lösen.

Trotzdem kommen hier (natürlich) auch immer wieder Werte raus, die length übersteigen. Mir fallen hier sehr, sehr viele schlechte Workarounds ein. Daher die Frage: Hat jemand hier im Forum vielleicht eine prägnante Idee, wie man length punktgenau befüllt? Ich kann mir irgendwie nicht vorstellen, dass ich der Erste bin, der dieses Problem hat... Von daher: Da gibt's doch sicher eine Lösung? ☺

Meine spontane Strategie wäre:

• Fülle den Stapel so lange, wie "length - quota > max_elem_length".

• Wenn "length - quota" in [min_elem_length, max_elem_length] liegt,

  • lege "length - quota" auf den Stapel. Fertig.

  • ansonsten lege min_elem_length auf den Stapel und gehe rückwärts und ersetze das gefundene Element mit "element - (quota - length)" aber mindestens "min_elem_length" so lange, bis "quota == length".

"quota" muss natürlich immer entsprechend aktualisiert werden - oder man berechnet es aus allen Elementen auf dem Stapel, was nicht so effizient aber weniger fehleranfällig wegen der fehlenden Redundanz ist.

...und das um diese Uhrzeit noch. Danke!

Hallo,

Ich kann mir irgendwie nicht vorstellen, dass ich der Erste bin, der dieses Problem hat...

Was ist denn das Ziel das ganzen, also warum brauchst du das? Das ganze Problem klingt erst mal ziemlich schräg, wenn man den potentiellen Nutzen nicht kannst.

Ansonsten solltest du _dringend_ die richtigen Begrifflichkeiten für Python verwenden, dann wird der Ausgangspost auch verständlicher. Die Begriffe, die du verwendest, sind schlicht falsch. Was das als "Stack" bezeichnest ist eine Liste. Das ist ein gewaltiger Unterschied zu dem, was mit beim Programmieren landläufig unter eine "Stack" versteht. Bildlich gesprochen ist eine Liste in Python eine Datenstruktur, wo die Werte nebeneinander liegen, bei einem Stack liegen die Elemente übereinander.

Listen haben in Python keine feste Länge und können dadurch auch nicht "voll" sein, weil das Limit nur der dem System zu Verfügung stehend Speicher ist. Und was du als "Größe der Elemente" bezeichnet, ist doch letztendlich der Zahlenwert eines Integers. Was du als min_elem_length und max_elem_length bezeichnest, sollte min_elemente_value und max_element_value heißen.

Du weißt, dass es Python-Modul itertools Methoden kennt, mit denen du dir _alle_ Kombinationen von Liste mit einer Länge X Elementen und Werten zwischen min_value und max_value sehr einfach generieren lassen kannst? Wenn du das in eine List Comprehension packst kannst du direkt noch die Listen verwerfen, wo z.B. die Summe der Elemente != irgend_eine_zahl ist.

Gruß, noisefloor