Array Aufgabe lösen, benötige Hilfe

[asadob1]

ich glaube, ich fange von 0 an:
ich habe jetzt einfache liste: a = [1,0,1,1,0]

Code: Alles auswählen

a=[1,0,1,1,0]
for i in a:
    if i==1:
        print(i)

wie kann ich die liste als Ergebnis = [1,2]
d.h. hier sind 2 Flüsse gefunden mit der Länge 1 und 2

[Sirius3]

Das ist ja DEINE Aufgabe, ein solches Programm zu schreiben.
Wie würdest Du es denn mit Worten beschreiben, was Du tun mußt?

[__blackjack__]

@asadob1: Ich weiss nicht ob das zielführend ist, denn eine Lösung dafür sieht anders aus als eine für die eigentliche Aufgabe. Das hier…

Code: Alles auswählen

In [134]: A                                                                     
Out[134]: [1, 0, 1, 1, 0]

In [135]: from itertools import groupby                                         

In [136]: [sum(1 for _ in group) for value, group in groupby(A) if value == 1]  
Out[136]: [1, 2]

…hilft Dir genau gar nicht bei der Lösung der Aufgabe.

Eine Karte mit nur einer Zeile wäre ein sinnvolles Teilproblem wenn man das Gesamtproblem lösen könnte in dem man das Problem für jede Kartenzeile löst und diese Teillösungen zu einer Gesamtlösung verrechnen könnte. Das wäre an sich vielleicht sogar ein Ansatz, aber da reicht als Zwischenergebnis nicht die Länge der Flüsse in der Zeile, denn man wüsste ja nicht wie man das dann mit der Teillösung einer benachbarten Zeile verrechnen muss. Sagen wir bei der nächsten Zeile käme als Ergebnis [1]. Müsste man dann aus den Teilergebnissen [1,2] und [1] dann [2,2] oder [1,3] machen? Das hängt davon ab, wie die nächste Zeile aussieht. Die notwendige Information steckt aber nicht mehr in diesen beiden Listen.

Grundsätzlich müsste man einen Algorithmus entwerfen können, der die Karte zeilenweise durchgeht und in der Laufzeit sogar effizienter ist als der, den ich in BASIC implementiert habe. Es gibt ja mehr als einen Weg nach Rom. Ich weiss aber nicht ob das zeilenweise verarbeiten einfacher zu erklären ist, oder offensichtlicher. In dem BASIC-Programm habe ich einen Weg gewählt der so ziemlich dem entsprechend dürfte, was die meisten machen würden wenn sie diese Aufgabe mit Stift und Papier lösen sollten. Man muss das dem Rechner halt deutlich kleinteiliger/detaillierter erklären als man das einem anderen Menschen erklären müsste.

Wenn Du das mit Stift und Papier lösen müsstest, wie würdest Du denn da vorgehen? Beschreibe das doch erst einmal in Worten ganz allgemein. Und geh dabei nicht von so einem kleinen Beispiel aus wo die Antwort noch, naja ich schaue halt drauf und das sieht man doch, ist. Stell Dir vor die Karte ist 100×100 Felder gross und es gibt da viele und lange Flüsse, so dass man das nicht mal eben ”im Kopf” machen kann, ohne gross darüber nachzudenken.

[asadob1]

du hast mir die Sache noch schwere gemacht.
ich dachte ich werde in meinem Code einfach erklärt wie man in eine´einfache liste [1,0,1,1,0]
den Verfahren lernen.

[__blackjack__]

@asadob1: Nee, die Aufgabe habe ich nicht gestellt, die hat halt einen bestimmten Schweregrad, da habe ich keine Schuld und keinen Einfluss drauf. Und auch wenn das vielleicht ein bisschen ärgerlich für Dich ist, dass ich verraten habe, das die Ergebnisliste für einen horizontalen Streifen der gesamten Geländekarte kein sinnvolles Zwischenergebnis ist, weisst Du jetzt zumindest, dass Du in diese Richtung nicht weiter denken musst. Beziehungsweise dass es zwar auch eine Lösung gibt, in der man die Karte Zeile für Zeile durcharbeiten kann, aber dass dabei das Zwischenergebnis anders aussehen muss als das Endergebnis. Das sind ja auch Informationen die Dich weiterbringen können.

Es gibt auch noch mindestens zwei weitere Lösungswege. Zum einen das ganze als Graphen aufzufassen wo die Flussfelder die Knoten sind, die eine Kante zu den benachbarten Feldern haben. Und dann sucht man die zusammenhängenden Graphen und zählt aus wie vielen Knoten die jeweils bestehen. Das wäre aber deutlich aufwändiger selber zu Programmieren. Das wäre ein Ansatz wenn man beispielsweise eine Bibliothek wie `networkx` verwenden dürfte, wo viele Graphenalgorithmen enthalten sind und man die Eingabedaten nur in eine passende Form bringen muss, so dass man eine passende Funktion aus dieser Bibliothek anwenden kann.

Noch einfacher könnte es mit der Bildverarbeitungsbibliothek OpenCV sein, die Funktionen zum “labeln” von zusammenhängenden Komponenten in einer Bitmap hat.

[asadob1]

ja, du hast recht, es ist meine Aufgabe, und das will ich jetzt nicht komplett lösen, deswegen ist meine Frage wie kann man nur einfach Zeile Liste zu programmieren: [1,0,1,1,0]

Code: Alles auswählen

a=[1,0,1,1,0]
for i in a:
    if i==1:
   
    (nachrechts der Nachbar suchen und die Ergebnisse merken
    danach die Liste ausgeben...........)
    
    
        print(i)
        
        

[__deets__]

Aber das bringt doch nichts. __blackjack__ hat doch schon gesagt, dass das Problem nicht von einer auf mehrere Zeilen generalisierbar ist.

[asadob1]

ja, das will ich nicht das ganze lösen, deswegen will ich das Problem zerlegen, und dann habe ich gemerkt, ich kann nicht mal eine einfache liste lösen, deswegen habe ich das gefragt wie ist es mit eine einfache liste a=[1,0,1,1,0] aussieht in meinem einfachen code

[__deets__]

Nochmal: das ist die falsche Zerlegung, wenn das Ziel die ganze Aufgabe ist.

Mit einer Liste wurde ja schon eine Lösung gezeigt.
Wenn du es selbst probieren willst, musst du in einer Schleife nacheinander die Position merken, wann eine Stelle i zum ersten Mal eine 1 war, und dann so lange weitermachen, bis die Stelle eine 0 ist. Die Differenz ist dann die Länge. Es gibt noch einen Spezialfall am Ende der Liste, aber erstmal kannst du so anfangen.

[__blackjack__]

@asadob1: Für eine einzelne Liste würde das letztendlich auf Lauflängenkodierung („run length encoding“, RLE) hinaus laufen bei der die 0en nicht im Ergebnis landen. Eine mögliche Lösung habe ich ja bereits gezeigt. Die Summe am Anfang kann man mit `more_itertools.ilen()` kürzer und IMHO auch ein bisschen verständlicher schreiben:

Code: Alles auswählen

In [141]: from more_itertools import ilen                                       

In [142]: [ilen(group) for value, group in groupby(A) if value == 1]            
Out[142]: [1, 2]

Wobei in dem Modul auch direkt etwas für RLE-Kodierung enthalten ist:

Code: Alles auswählen

In [147]: from more_itertools import run_length                                 

In [148]: [count for value, count in run_length.encode(A) if value == 1]        
Out[148]: [1, 2]

Wenn Du Dir das zu Fuss selbst programmieren willst, könntest Du Dir merken was für ein Wert zuletzt gesehen wurde, mit einem sinnvollen Startwert für den ersten Wert aus der Liste, und falls das aktuelle Element gleich dem zuletzt gesehenen ist, musst Du das zählen. Falls nicht, schauen ob es ein Fluss ist oder nicht. Falls es ein Fluss ist, den Zähler zum Ergebnis hinzufügen. Falls es kein Fluss ist, einfach ignorieren, denn die Landfelder sollen ja nicht gezählt werden. Und am Ende muss man noch mal aufpassen, dass man nichts vergisst.

Da Du bisher immer Code gezeigt hast, der einfach auf Modulebene steht: lass das sein. Pack so etwas in eine Funktion. Dann kann man auch einfach verschiedene Eingaben testen ob da das erwartete Ergebnis kommt. Und diese Tests auch als Funktion schreiben und braucht für verschiedene Tests nicht immer den Quelltext ändern.

[asadob1]

ich habe bis jetzt so erweitert, dass man hier alle Zeilen lieset.
jetzt ander Frage bitte:
kann man anstelle der Zeilen die Spalten lesen
soll man hier die Funktion reversed benutzen , oder gibt es andere Vorgehensweise

Code: Alles auswählen

a=[[1,0,0,1,0],
    [1,0,1,0,0],
    [0,0,1,0,1],
    [1,0,1,0,1],
    [1,0,1,1,0],
    ]
#Eingabe = input("bitte die Matrix Zeile eingeben: ")
for i in range(5):
    from itertools import groupby
    for value, group in groupby(a[i]):
        if value ==1:
            b= [sum (1 for _ in group )]
            print(list(b))

-------------------------------

oder verifacht wie mir bei gebracht habt:

Code: Alles auswählen

a=[[1,0,0,1,0],
    [1,0,1,0,0],
    [0,0,1,0,1],
    [1,0,1,0,1],
    [1,0,1,1,0],
    ]
for i in range(5):
    from itertools import groupby
    b=[sum(1 for _ in group) for value, group in groupby(a[i]) if value ==1]
    print(b)

[__blackjack__]

@asadob1: `reversed()` dreht die Reihenfolge um und transponiert nicht. Ich frage mich immer noch wo Du damit jetzt hin willst, denn das ist alles keine Lösung der Aufgabe und auch kein Zwischenschritt dort hin, sondern eher eine Sackgasse.