In Algorithmenklassen und in der Informatik im Allgemeinen besteht eine sehr häufige Anforderung darin, über ein Gitter oder eine Matrix (wie in BFS oder DFS) in vier Richtungen zu iterieren. Dies scheint oft zu viel klobigem und ausführlichem Code mit viel Arithmetik und Vergleichen innerhalb von Schleifen zu führen. Ich habe viele verschiedene Ansätze gesehen, aber ich kann das Gefühl nicht loswerden, dass es einen präziseren Weg gibt, dies zu tun.

Die Herausforderung besteht darin, eine reine Funktion zu schreiben, die unter Berücksichtigung der Breite und Höhe einer endlichen Ebene mit n, mUrsprung in einem Punkt (0,0)und der Koordinaten (x,y), die einen gültigen Punkt in dieser Ebene darstellen können, ein iterierbares Objekt aller Punkte in der Ebene mit vier Richtungen zurückgibt angrenzend an (x,y).

Ziel ist es, diese Funktion in möglichst wenigen Bytes zu definieren.

Einige Beispiele zur Veranschaulichung der gültigen Eingabe / Ausgabe:

n = 5 (y-axis), m = 3 (x-axis) (zero-based)

matrix = [
    [A, B, C],
    [D, E, F],
    [G, H, I],
    [J, K, L],
    [M, N, O],
]

(x, y) => [valid iterable points]

E: (1, 1) => [(1, 0), (2, 1), (1, 2), (0, 1)]
A: (0, 0) => [(1, 0), (0, 1)]
L: (2, 3) => [(2, 2), (2, 4), (1, 3)]
N: (1, 4) => [(1, 3), (2, 4), (0, 4)]

n = 1 (y-axis), m = 1 (x-axis) (zero-based)

matrix = [
    [A],
]

(x, y) => [valid iterable points]

A: (0, 0) => []

n = 2 (y-axis), m = 1 (x-axis) (zero-based)

matrix = [
    [A],
    [B],
]

(x, y) => [valid iterable points]

A: (0, 0) => [(0, 1)]
B: (0, 1) => [(0, 0)]

Und hier ist ein Beispiel (dieses in Python) für eine Funktion, die die folgenden Bedingungen erfüllt:

def four_directions(x, y, n, m):
    valid_coordinates = []
    for xd, yd in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        nx, ny = x + xd, y + yd
        if 0 <= nx < m and 0 <= ny < n:
            valid_coordinates.append((nx, ny))
    return valid_coordinates

Im obigen Beispiel wurde eine benannte Funktion definiert, aber auch anonyme Funktionen sind zulässig.

Die Eingaben n, m, x, ysind alle vorzeichenlose 32-Bit-Ganzzahlen in den folgenden Bereichen:

n > 0
m > 0
0 <= x < m
0 <= y < n

Die Ausgabe muss die Form eines iterablen (wie auch immer Ihre gewählte Sprache dies definiert) von (x, y) Paaren haben.

Zusätzliche Erläuterungen:

Komplexe Zahlen (und andere Darstellungen / Serialisierungen) sind in Ordnung, solange der Konsument des Iterablen auf sie zugreifen kann xund yals ganze Zahlen nur ihren Standort kennen.

Nicht auf Null basierende Indizes sind zulässig, jedoch nur, wenn die gewählte Sprache eine nicht auf Null basierende Sprache ist. Wenn die Sprache eine Mischung aus Nummerierungssystemen verwendet, wird standardmäßig das Nummerierungssystem der Datenstruktur verwendet, die am häufigsten zur Darstellung einer Matrix verwendet wird. Wenn dies immer noch alles fremde Begriffe in der angegebenen Sprache sind, ist jeder Startindex akzeptabel.

Python 2 , 66 Bytes

lambda m,n,x,y:[(x-1,y),(x+1,y)][~x:m-x]+[(x,y-1),(x,y+1)][~y:n-y]

Probieren Sie es online!

Listet die vier Nachbarn auf und entfernt dann mit List Slicing diejenigen, die außerhalb der Grenzen liegen.

Python 2 , 71 Bytes

lambda m,n,x,y:[(k/n,k%n)for k in range(m*n)if(k/n-x)**2+(k%n-y)**2==1]

Probieren Sie es online!

Anstatt zu prüfen, welche der vier Nachbarn eingegrenzt sind, prüfen wir langsamer alle eingegrenzten Punkte für diejenigen, die Nachbarn sind, dh von denen der euklidische Abstand genau 1 beträgt (x,y). Wir verwenden auch den klassischen Div-Mod-Trick, um über ein Gitter zu iterieren , ohne zwei Schleifen schreiben zu müssen for i in range(m)for j in range(n).

Ich habe versucht, die Entfernungsbedingung mit komplexer Arithmetik zu schreiben, aber es stellte sich heraus, dass das Schreiben länger dauert abs((k/n-x)*1j+k%n-y)==1.

Python 2 , 70 Bytes

lambda m,n,x,y:[(x+t/3,y+t%3-1)for t in-2,0,2,4if m>x+t/3>=0<y+t%3<=n]

Probieren Sie es online!

Oktave , 90 Bytes

Hierbei wird ein geometrischer Ansatz verwendet: Zuerst erstellen wir eine Matrix aus Nullen der gewünschten Größe und setzen a 1auf die gewünschte Position. Dann falten wir uns mit dem Kernel zusammen

[0, 1, 0]
[1, 0, 1]
[0, 1, 0]

Dadurch wird eine neue Matrix derselben Größe mit einer Matrix an den vier Nachbarn des ursprünglichen Punkts erstellt. Dann werden find()die Indizes der Nicht-Null-Einträge dieser neuen Matrix berechnet.

function [i,j]=f(s,a,b);z=zeros(s);z(a,b)=1;[i,j]=find(conv2(z,(v=[1;-1;1])*v'<0,'same'));

Probieren Sie es online!

^{_{Faltung ist der Schlüssel zum Erfolg.}}

Wolfram Language (Mathematica) , 42 Byte

Cases[List~Array~#2,a_/;Norm[a-#]==1,{2}]&

Probieren Sie es online!

1-indiziert (gemäß der Konvention von Mathematica für die Indizierung). Übernimmt die Eingabe als {x,y}, {m,n}.

für 0-indizierte E / A, 45 Bytes :

Cases[Array[List,#2,0],a_/;Norm[a-#]==1,{2}]&

Probieren Sie es online!

JavaScript (ES6), 74 Byte

Langweiliger Ansatz.

(h,w,x,y)=>[x&&[x-1,y],~x+w&&[x+1,y],y&&[x,y-1],++y-h&&[x,y]].filter(_=>_)

Probieren Sie es online!

JavaScript (Node.js) , 74 Byte

Weniger langweilig aber genauso lang. Übernimmt die Eingabe als ([h,w,x,y]).

a=>a.flatMap((_,d,[h,w,x,y])=>~(x+=--d%2)*~(y+=--d%2)&&x<w&y<h?[[x,y]]:[])

Probieren Sie es online!

JavaScript (V8) , 67 Byte

Wenn alle Standardausgabemethoden erlaubt wären, könnten wir einfach die gültigen Koordinaten ausdrucken mit:

(h,w,x,y)=>{for(;h--;)for(X=w;X--;)(x-X)**2+(y-h)**2^1||print(X,h)}

Probieren Sie es online!

Jelly ,  13  12 Bytes

2ḶṚƬNƬẎ+⁸%ƑƇ

Eine dyadische Link - Liste zwei (0 indizierte) ganze Zahlen auf der linken Seite, der Annahme [row, column]und zwei ganzen Zahlen auf der rechten Seite [height, width], die eine Liste von Listen von ganzen Zahlen ergibt [[adjacent_row_1, adjacent_column_1], ...].

Probieren Sie es online!

Wie?

2ḶṚƬNƬẎ+⁸%ƑƇ - Link: [row, column]; [height, width]   e.g. [3,2]; [5,3] (the "L" example)
2            - literal 2                                   2
 Ḷ           - lowered range                               [0,1]
   Ƭ         - collect up while distinct, applying:
  Ṛ          -   reverse                                   [[0,1],[1,0]]
     Ƭ       - collect up while distinct, applying:
    N        -   negate                                    [[[0,1],[1,0]],[[0,-1],[-1,0]]]
      Ẏ      - tighten                                     [[0,1],[1,0],[0,-1],[-1,0]]
        ⁸    - chain's left argument ([row, column])       [3,2]
       +     - add (vectorises)                            [[3,3],[4,2],[3,1],[2,2]]
           Ƈ - filter keep if:
          Ƒ  -   is invariant under:
         %   -     modulo ([height, width]) (vectorises)    [3,0] [4,2] [3,1] [2,2]
             - (...and [3,0] is not equal to [3,3] so ->)  [[4,2],[3,1],[2,2]]

Perl 6 , 56 49 Bytes

-7 bytes dank nwellnhof!

{grep 1>(*.reals Z/@^b).all>=0,($^a X+1,-1,i,-i)}

Probieren Sie es online!

Entfernt die Out-of-Bound-Elemente, indem überprüft wird, ob sie bei Division durch die Array-Grenzen zwischen 0 und 1 liegen. Nimmt die Eingabe und Ausgabe über komplexe Zahlen vor, bei denen der Realteil der ist x Koordinate und der Imaginärteil Koordinate ist y. Sie können diese mit den Funktionen .imund extrahieren .re.

J , ^{30 29} 28 Bytes

(([+.@#~&,1=|@-)j./)~j./&i./

Probieren Sie es online!

Wie:

• Verwandle das rechte mx narg in ein Gitter komplexer Zahlenj./&i./
• Gleiches gilt für linkes Argument (unser Punkt) j./
• Erstellen Sie eine Maske, aus der hervorgeht, wo der Abstand zwischen unserem Punkt und dem Gitter genau 1 beträgt 1=|@-
• Verwenden Sie diese Option, um das Raster zu filtern, nachdem Sie beide abgeflacht haben #~&,
• Verwandle das Ergebnis wieder in echte Punkte +.@

C # (Visual C # Interactive Compiler) , 91 Byte

(a,b,x,y)=>new[]{(x+1,y),(x-1,y),(x,y+1),(x,y-1)}.Where(d=>((x,y)=d,p:x>=0&x<a&y>=0&y<b).p)

Probieren Sie es online!

Alternative:

(a,b,x,y)=>new[]{(x+1,y),(x-1,y),(x,y+1),(x,y-1)}.Where(d=>((x,y)=d).Item1>=0&x<a&y>=0&y<b)

Probieren Sie es online!

Kohle , 29 Bytes

Ｊθη#ＦＩζＦＩε«Ｊικ¿№ＫＶ#⊞υ⟦ικ⟧»⎚Ｉυ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Übernimmt Eingaben in der Reihenfolge x, y, width, height. Erläuterung:

Ｊθη#

Drucken Sie a #an der angegebenen Position aus.

ＦＩζＦＩε«

Bewegen Sie sich über das angegebene Rechteck.

Ｊικ

Zur aktuellen Position springen.

¿№ＫＶ#⊞υ⟦ικ⟧

Wenn es einen Nachbarn gibt, #speichern Sie die Position.

»⎚Ｉυ

Die erkannten Positionen am Ende der Schleife ausgeben.

Langweilige Antwort:

ＦＩζＦＩε¿⁼¹⁺↔⁻ιＩθ↔⁻κＩηＩ⟦ικ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Funktioniert durch mathematisches Finden der angrenzenden Positionen.

Haskell, 62 Bytes

Verwenden

f m n a b = [(x,y)|x<-[0..m-1],y<-[0..n-1],(x-a)^2+(y-b)^2==1]

Probieren Sie es online!

Langweiliger Ansatz: 81 Bytes

f m n x y=filter (\(x,y)->x>=0&&y>=0&&x<m&&y<n) [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]