Bardzo powszechną potrzebą w klasach algorytmów i informatyce jest iteracja 4-kierunkowo po siatce lub macierzy (np. W BFS lub DFS). Wydaje się, że często powoduje to dużo nieporęcznego i pełnego kodu z dużą ilością arytmetyki i porównań w pętlach. Widziałem wiele różnych podejść do tego, ale nie mogę pozbyć się wrażenia, że ​​istnieje bardziej zwięzły sposób na zrobienie tego.

Wyzwanie polega na napisaniu czystej funkcji, która biorąc pod uwagę szerokość i wysokość skończonej płaszczyzny n, mrozpoczynającej się w punkcie (0,0)oraz współrzędne, (x,y)które mogą reprezentować dowolny ważny punkt w tej płaszczyźnie, zwraca iterowalny obiekt wszystkich punktów w płaszczyźnie, które są 4-kierunkowo przylegające do (x,y).

Celem jest zdefiniowanie tej funkcji w jak najmniejszej liczbie bajtów.

Kilka przykładów, które pomogą zilustrować prawidłowe dane wejściowe / wyjściowe:

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)]

A oto przykład (ten w Pythonie) funkcji spełniającej warunki:

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

W powyższym przykładzie zdefiniowano nazwaną funkcję, ale dopuszczalne są również funkcje anonimowe.

Wszystkie dane wejściowe n, m, x, ysą 32-bitowymi liczbami całkowitymi bez znaku w następujących zakresach:

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

Wynik musi mieć postać iterowalnej (jednak wybrany przez Ciebie język to określa) par (x, y).

Dodatkowe wyjaśnienia:

Liczby zespolone (i inne reprezentacje / serializacje) są w porządku, o ile konsument iterowalnego może uzyskać dostęp xi yjako liczby całkowite znające tylko ich lokalizację.

Indeksy niezerowe są dopuszczalne, ale tylko wtedy, gdy wybranym językiem jest język niezerowy. Jeśli język używa kombinacji systemów numerowania, domyślnie jest to system numeracji struktury danych najczęściej używany do reprezentacji macierzy. Jeśli nadal są to wszystkie obce pojęcia w danym języku, dopuszczalny jest każdy indeks początkowy.

Python 2 , 66 bajtów

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

Wypróbuj online!

Wyświetla listę czterech sąsiadów, a następnie używa wycinania listy, aby usunąć te, które są poza granicami.

Python 2 , 71 bajtów

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]

Wypróbuj online!

Zamiast sprawdzać, który z czterech sąsiadów znajduje się w granicach, robimy to w wolniejszy sposób, sprawdzając wszystkie punkty w granicach dla tych, którzy są sąsiadami, czyli mają odległość euklidesową dokładnie 1 od (x,y). Używamy również klasycznej sztuczki div-mod do iteracji po siatce , co pozwala uniknąć konieczności pisania dwóch pętli for i in range(m)for j in range(n).

Próbowałem użyć złożonej arytmetyki do napisania warunku odległości, ale okazało się, że pisanie trwało dłużej abs((k/n-x)*1j+k%n-y)==1.

Python 2 , 70 bajtów

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]

Wypróbuj online!

Oktawa , 90 bajtów

Wykorzystuje to podejście geometryczne: Najpierw tworzymy macierz zer o pożądanym rozmiarze i ustawiamy 1na pożądaną lokalizację. Następnie łączymy się z jądrem

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

która tworzy nową macierz tego samego rozmiaru z macierzami u 4 sąsiadów pierwotnego punktu. Następnie mamy find()indeksy niezerowych wpisów tej nowej macierzy.

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'));

Wypróbuj online!

^{_{splot jest kluczem do sukcesu.}}

Wolfram Language (Mathematica) , 42 bajty

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

Wypróbuj online!

1-indeksowany (zgodnie z konwencją Mathematica dotyczącą indeksowania). Pobiera dane wejściowe jako {x,y}, {m,n}.

dla We / Wy indeksowanych 0, 45 bajtów :

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

Wypróbuj online!

JavaScript (ES6), 74 bajty

Nudne podejście.

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

Wypróbuj online!

JavaScript (Node.js) , 74 bajty

Mniej nudne, ale równie długie. Pobiera dane wejściowe jako ([h,w,x,y]).

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

Wypróbuj online!

JavaScript (V8) , 67 bajtów

Gdyby dozwolone były wszystkie standardowe metody wyjściowe, moglibyśmy po prostu wydrukować prawidłowe współrzędne za pomocą:

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

Wypróbuj online!

Galaretka ,  13  12 bajtów

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

Dwójkowym link przyjmując listę dwóch (0 indeksowane) liczb po lewej stronie, [row, column]i dwie liczby po prawej stronie [height, width], co daje listę list liczb całkowitych [[adjacent_row_1, adjacent_column_1], ...].

Wypróbuj online!

W jaki sposób?

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 bajtów

-7 bajtów dzięki nwellnhof!

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

Wypróbuj online!

Usuwa elementy poza granicami, sprawdzając, czy po podzieleniu przez granice tablicy wynosi od 0 do 1. Pobiera dane wejściowe i wyjściowe za pomocą liczb zespolonych, w których rzeczywista część jest xwspółrzędną, a urojoną y. Możesz je wyodrębnić za pomocą funkcji .imi .re.

J , ^{30 29} 28 bajtów

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

Wypróbuj online!

W jaki sposób:

• Zamień prawą mx narg w siatkę liczb zespolonychj./&i./
• To samo dla lewego arg (nasz punkt) j./
• Utwórz maskę pokazującą, gdzie odległość między naszym punktem a siatką wynosi dokładnie 1 1=|@-
• Użyj tego do filtrowania siatki po spłaszczeniu obu #~&,
• Zamień wynik z powrotem w prawdziwe punkty +.@

C # (interaktywny kompilator Visual C #) , 91 bajtów

(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)

Wypróbuj online!

Alternatywnie:

(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)

Wypróbuj online!

Węgiel drzewny , 29 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Pobiera dane wejściowe w kolejności x, y, szerokość, wysokość. Wyjaśnienie:

Ｊθη#

Wydrukuj #w podanej pozycji.

ＦＩζＦＩε«

Pętla nad danym prostokątem.

Ｊικ

Przejdź do bieżącej pozycji.

¿№ＫＶ#⊞υ⟦ικ⟧

Jeśli jest sąsiad, #zapisz pozycję.

»⎚Ｉυ

Wyjście wykrytych pozycji na końcu pętli.

Nudna odpowiedź:

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

Wypróbuj online! Link jest do pełnej wersji kodu. Działa poprzez znalezienie matematycznie sąsiednich pozycji.

Haskell, 62 bajty

Za pomocą

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

Wypróbuj online!

Nudne podejście: 81 bajtów

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)]