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.
(x,y)sam jest w prostokącie, prawda?
