dynamisch muster in matrix finden

[elbarto132]

ich habe eine matrix die 8x8 zeichen groß ist und mit beliebigen werten gefüllt ist, also so:

Code: Alles auswählen

########
########
########
########
########
########
########
########

nun geht es darum bestimmte muster in dieser matrix zu finden z.b. so etwas

Code: Alles auswählen

##y#
xx?y
##x#
##x#

(alle x den gleichen wert, #? sind beliebige werte, eins der y = x)

erklärung dazu:
es soll also ein muster gefunden werden wo die werte auf x gleich sind. als ausgabe wäre die position von ? am besten, und eins der y muss =x sein
die muster sind unterschiedlich groß, können auch z.b. 4x2 groß sein

also es würde z.b. auf so etwas zutreffen:

Code: Alles auswählen

##1#
11?#
##1#
##1#

die sache mit dem y ist nicht so wichtig, das kann ich auch danach noch abfragen
aber wie finde ich so ein muster über mehrere zeilen/spalten?
ich denke das müsste gehen indem ich alles in eine zeile schreibe und dann per regexp abfrage, zwischen x und y koordinaten kann ich dann ja unterscheiden indem ich per m[8*y+x] darauf zugreife und die koordinaten kann ich bestimmen indem ich die position durch 8 teile und der rest is dann der x wert.
allerdings ist mir nicht klar wie ich die regexp pattern so verändere das ich alle positionen ordentlich abfrage und das ganze für unterschiedlich große muster

ich hoffe mir kann da jemand helfen

[BlackJack]

Könntest Du's vielleicht noch einmal anders erklären!? Warum gibt es für beliebige Werte zwei unterschiedliche Zeichen '#' und '?' und warum trifft das dritte Beispiel auf das zweite zu, wo doch beim Zweiten neben dem '?' ein 'y' steht, im dritten dort aber ein '#' zu finden ist!?

[elbarto132]

(rot = die koordinaten muss ich ermitteln, welchen wert meine matrix an der position hat ist egal
blau = die werte müssen alle gleich sein
grün = eins davon muss den gleichen wert haben wie blau)

also wenn die werte auf x z.b. 1 sind muss entweder das obere oder das rechte y auch 1 sein, und das jeweils andere y ist dann egal
als rückgabewert brauche ich dann die koordinaten von "?", also sowas wie "muster 1 bei (4,2) gefunden"

ich hoffe man versteht es was ich meine

das mit dem y kann ich ja aber auch nachdem ich die "?" koordinate habe noch überprüfen muss also nicht zwangsläufig direkt mit rein

[BlackJack]

Müsste etwas in dieser Art nicht funktionieren?

Code: Alles auswählen

def search(matrix):
    m = matrix
    coordinates = (x, y for x in xrange(len(m[0])) for y in xrange(len(m)))
    for x, y in coordinates:
        a = m[y][x - 2]
        if (all(a == m[y + j][x + i] for i, j in [(-1, 0), (0, 1), (0, 2)])
            and (a in [m[y - 1][x], m[y][x + 1]])):
            return (x, y)
    raise Exception('pattern not found')

Was ist denn Deine "Matrix" für ein Objekt?

[elbarto132]

momentan is meine matrix nen 2 dimensionales tupel, aber das is ja eigentlich egal, kann man ja umwandeln

deine lösung sieht glaube ich ganz gut aus, allerdings blick ich bei deiner art der ausführung noch nicht ganz durch, kannste das mal etwas weniger kompakt (oder wie man es nennen will ) schreiben?

[BlackJack]

@elbarto132: Hm, ich gehe alle Koordinaten durch und betrachte `x` und `y` sozusagen als Kandidaten für das '?'. In `a` hole ich mir den Inhalt von dem Feld in Zeile der Zeile mit dem '?' und zwei Felder links davon.

Dann überprüfe ich ob der Wert mit dem aller anderen 'x'-Felder übereinstimmt. Dazu iteriere ich über eine Liste mit den relativen Koordinaten. Das wird Und-Verknüpft, mit der Frage, ob der Wert in den beiden 'y'-Feldern vorkommt.

Das war's auch schon.

[HWK]

Um nicht über den Rand hinaus zu suchen, vielleicht besser:

Code: Alles auswählen

coordinates = (x, y for x in xrange(2, len(m[0]) - 1) for y in xrange(1, len(m) - 2))

MfG
HWK

[BlackJack]

Stimmt, da hatte ich gar nicht dran gedacht.

[numerix]

Um nicht über den Rand hinaus zu suchen, vielleicht besser:

Code: Alles auswählen

coordinates = (x, y for x in xrange(2, len(m[0]) - 1) for y in xrange(1, len(m) - 2))

Das war auch mein erster Gedanke, aber möglicherweise gehen damit dann auch Treffer verloren. Das wird anhand der bisherigen Problembeschreibung für mich aber noch nicht ganz klar: Wenn das eine der beiden y den Wert von x hat, ist der Wert des anderen ja egal. Wenn "egal" auch heißt, dass da gar kein Wert stehen muss, dann könnte der Fall eintreten, dass Treffer verloren gehen, wenn man die Ränder herausnimmt.

[elbarto132]

Code: Alles auswählen

    coordinates = (x, y for x in xrange(2, len(m[0]) - 1) for y in xrange(1, len(m) - 2))
                          ^
SyntaxError: invalid syntax

hab das so noch nie benutzt, daher ist mir unklar was da falsch ist, also was stimmt da nicht?
(dachte erst das es evtl in python 3 eingeführt wurde, aber auch damit kommt der fehler)

das problem mit den rändern meiner matrix habe ich atm gelöst indem ich nen rand aus nullen drum gezogen habe und ne null als treffer ignoriere

[derdon]

Wie wärs mit

Code: Alles auswählen

((x, y) for x in xrange(2, len(m[0]) - 1) for y in xrange(1, len(m) - 2))