Array Aufgabe lösen, benötige Hilfe

[__blackjack__]

Als kleiner Hinweis, dass man da nicht zwingend Rekursion zu braucht, und das eine relativ einfache Lösung mit den eher primitiven Möglichkeiten eines klassischen BASICs möglich sind:

Code: Alles auswählen

   10 N=5:RL=0:DIM M(N,N),R(N*N)
   20 FOR I=1 TO N:FOR J=1 TO N:READ M(I,J):NEXT:NEXT
   30 FOR I=1 TO N:FOR J=1 TO N:IF M(I,J) THEN GOSUB 100:NEXT:NEXT
   40 IF RL=0 THEN PRINT"NO RIVERS FOUND.":END
   50 PRINT RL;"RIVERS FOUND:":GOSUB 300:FOR I=0 TO RL-1:PRINT R(I);:NEXT:END
  100 X=I:Y=J
  110 GOSUB 200:IF C>1 THEN RETURN
  120 M(X,Y)=0:R(RL)=R(RL)+1:IF C=0 THEN RL=RL+1:RETURN
  130 X=NX:Y=NY:GOTO 110
  200 C=0:NX=-1:NY=-1
  210 IF X>0 THEN IF M(X-1,Y) THEN C=C+1:NX=X-1:NY=Y
  220 IF X<N THEN IF M(X+1,Y) THEN C=C+1:NX=X+1:NY=Y
  230 IF Y>0 THEN IF M(X,Y-1) THEN C=C+1:NX=X:NY=Y-1
  240 IF Y<N THEN IF M(X,Y+1) THEN C=C+1:NX=X:NY=Y+1
  250 RETURN
  300 F=0:FOR I=0 TO RL-2:IF R(I)>R(I+1) THEN T=R(I):R(I)=R(I+1):R(I+1)=T:F=-1
  310 NEXT:IF F THEN 300
  320 RETURN
20000 DATA 1,0,0,1,0
20010 DATA 1,0,1,0,0
20020 DATA 0,0,1,0,1
20030 DATA 1,0,1,0,1
20040 DATA 1,0,1,1,0

Sogar inklusive sortieren so schnell durchlaufen, dass sich nicht wirklich gelohnt hat eine Zeitmessung einzubauen. Programmlauf:

Code: Alles auswählen

RUN
 5 RIVERS FOUND:
 1  2  2  2  5
READY.

[asadob1]

ich denke das ganze wir noch viel schneller wenn man in eine While Schleife tuet.
ich habe es bis jetzt nicht geschaft, da ich kein Programmierer bin, aber mir geht es nur um Algorithmus.
d.h. while a[j] == 1 dann erstmal den gefundnen wert zu Laenge zuweisen und dann die nachbaren auch über If Abfrage nach rechts und nach unten, aber ich habe hier Schwierigkeiten mit dem L Form.

[asadob1]

sorry ich meine a[j]

Code: Alles auswählen

a=[a[i][j].......a[i][j+1]
[a[i+1][j]..................]

[asadob1]

das habe ich einfach bis jetzt geschaft, mir fehlt noch die Ausgabe der Flüsse in einer liste:
also bei mir werden Fluss 5x mal ausgegeben, jetzt muss die laenge einzelne fluss als summe i+j ausgegeben--> bitte einfache vorgehensweise, da ich kein programmierer bin

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],
    ]
print (a)
for i in a:
    for j in a:
        if i== j:
            print("fluss")
            

[__blackjack__]

@asadob1: Das da findet gar keine Flüsse, nicht mal Teile von Flüsse. Schau Dir mal die Ausgabe an wenn garantiert *gar kein* Fluss in `a` enthalten ist:

Code: Alles auswählen

In [98]: a = [ 
    ...:     [0, 0, 0, 0, 0], 
    ...:     [0, 0, 0, 0, 0], 
    ...:     [0, 0, 0, 0, 0], 
    ...:     [0, 0, 0, 0, 0], 
    ...:     [0, 0, 0, 0, 0], 
    ...: ] 
    ...: print(a) 
    ...: for i in a: 
    ...:     for j in a: 
    ...:         if i == j: 
    ...:             print("fluss") 
    ...:                                                                        
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss

``for``- oder ``while``-Schleife ist nicht primär eine Frage der Geschwindigkeit, sondern welche im gegebenen Fall sinnvoller ist. ``for``-Schleifen verwendet man, wenn man über eine Folge von Elementen von irgendwas iteriert was man entweder schon hat, oder sich leicht erstellen kann. ``while``-Schleifen wenn man eine sinnvolle Abbruchbedingung formulieren kann, oder sich erst *im* Schleifenkörper entscheidet ob man fertig ist und die Schleife abbrechen kann, oder nicht.

Die Aufgabe erfordert mehr als eine Schleife und die müssen auch nicht alle vom gleichen Typ sein, wenn man an einigen Stellen etwas hat über das man iterieren kann und an anderen Stellen etwas solange wiederholen möchte, bis eine bestimmte Bedingung eingetreten ist.

Es wurde ja schon gesagt, dass das keine ganz triviale Aufgabe ist. Aber ganz so komplex ist sie halt auch nicht. Man braucht für eine relativ unkomplizierte Lösung beispielsweise keine Rekursion, sondern kann das mit ein paar Schleifen machen. Also ohne das man sich Rekursion mit einem eigenen Stapel nachprogrammiert oder ähnlich komplex. Ich habe das mit einer Lösung in CBM BASIC ja gezeigt, dass das bei den gegebenen Vorbedingungen mit sehr primitiven Mitteln überschaubar machbar ist.

Von der Komplexität her ist das aber schon so umfangreich, dass ich, insbesondere einem Anfänger, dringend dazu rate das in kleinere Teilprobleme zu zerlegen, und nicht zu versuchen das alles in *ein* tief verschachteltes Schleifenkonstrukt zu schreiben. Die BASIC-Lösung verwendet letztlich drei Schleifenebenen um die Flusslängen zu ermitteln, und das ist auf das Hauptprogramm und zwei Unterprogramme verteilt. Wobei man in Python vielleicht den einen Zeilenblock mit den vier nahezu identischen Inhalten vielleicht auch noch mit einer Schleife ausdrücken würde. Und ich würde da auch mehr als zwei Funktionen schreiben. Also klar, die Unterprogramme in dem BASIC-Programm wären heisse Kandidaten für eigene Funktionen in Python, aber auch das was dort drin gemacht wird, lässt sich noch sinnvoll zerlegen. Der Vorteil ist, dass man damit Codestücken einen Namen geben kann, der beschreibt, was der Code im Kontext der Problemlösung macht. Gerade als Anfänger ist es IMHO gut eher zu viele Funktionen zu definieren und lesbaren und damit verständlichen Code damit zu schreiben. Wenn man fertig ist, kann man die immer noch ”inlinen”. Das ist einfach. Schwieriger ist dagegen bei zu umfangreichem/komplexen/nicht mehr überschaubaren Code anzufangen Teile in Funktionen heraus zu ziehen. Dabei muss man deutlich mehr nachdenken und dabei können deshalb auch mehr Fehler passieren.

Möglicher Grundablauf beim Programmieren ganz allgemein: Problem in Teilprobleme zerlegen. Teilprobleme in kleinere Teilprobleme zerlegen. Solange wiederholen bis man Teilprobleme hat, die sich mit einer Funktion mit wenigen Zeilen Code lösen lassen. Diese Funktion erst testen, ob sie tatsächlich das macht was sie soll bevor man zur nächsten Teillösung/Funktion weitergeht. Es nützt nichts auf ungetesteten oder gar nachweislich nicht funktionierenden Funktionen aufzubauen. Aus funktionierenden Teillösungen lassen sich dann grössere Teillösungen zusammenbauen, bis man am Ende das Gesamtproblem gelöst hat.

Das ganze Schritt für Schritt *entwickeln*. Also nicht alles runterschreiben und *dann* erst das erste mal ausführen, sondern immer mal wieder schauen wie weit das was man hat, der Lösung näher kommt.

Vor alledem musst Du aber erst einmal einen Algorithmus überlegen. In der Regel ohne Rechner, mit Stift und Papier überlegen und an Beispielen durchspielen, wie man das grundsätzlich Lösen und diese Lösung in einer vollständigen und präzisen schriftlichen Anleitung erklären kann. Jemandem der nicht sehr schlau ist, und der sich alles notieren muss, weil er es sonst vergisst. Denn mit dem Programm musst Du das letztlich noch formaler und präziser jemandem beibringen der ultimativ dumm ist und kein Stück selbst denkt: dem Rechner.

[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.