Очень распространенная потребность в классах алгоритмов и компьютерных науках в целом состоит в том, чтобы выполнять итерацию в четырех направлениях по сетке или матрице (например, в BFS или DFS). Это, кажется, часто приводит к большому количеству неуклюжего и многословного кода с большим количеством арифметики и сравнений внутри циклов. Я видел много разных подходов к этому, но я не могу избавиться от ощущения, что есть более краткий способ сделать это.

Задача состоит в том, чтобы написать чистую функцию, которая, учитывая ширину и высоту конечной плоскости, n, mисходящей из точки (0,0), и координаты, (x,y)которые могут представлять любую действительную точку в этой плоскости, возвращает итеративный объект всех точек в плоскости, которые направлены в 4 направлениях. рядом с (x,y).

Цель состоит в том, чтобы определить эту функцию как можно меньше байтов.

Некоторые примеры, которые помогут проиллюстрировать действительный ввод / вывод:

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

И вот пример (этот в Python) функции, которая удовлетворяет условиям:

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

В приведенном выше примере определена именованная функция, но также допустимы анонимные функции.

Входы n, m, x, y представляют собой 32-разрядные целые числа без знака в следующих диапазонах:

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

Выходные данные должны принимать форму итерируемой (однако это зависит от выбранного вами языка) пары (x, y).

Дополнительные уточнения:

Комплексные числа (и другие представления / сериализации) в порядке, пока потребитель итерируемого может получить доступ x и yкак целые числа, зная только их местоположение.

Индексы, не основанные на нулях, допустимы, но только в том случае, если выбранным языком является язык без нуля. Если язык использует сочетание систем нумерации, по умолчанию используется система нумерации структуры данных, наиболее часто используемая для представления матрицы. Если это все еще иностранные понятия в данном языке, любой начальный индекс приемлем.

Python 2 , 66 байт

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

Попробуйте онлайн!

Перечисляет четырех соседей, затем использует нарезку списка для удаления тех, кто находится за пределами.

Python 2 , 71 байт

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]

Попробуйте онлайн!

Вместо того, чтобы проверять, какие из четырех соседей являются внутренними, мы делаем это медленным способом проверки всех внутренних точек для тех, которые являются соседями, то есть имеют евклидово расстояние ровно 1 от (x,y). Мы также используем классический трюк div-mod для итерации по сетке. , избавляя от необходимости писать два цикла вродеfor i in range(m)for j in range(n) .

Я пытался использовать сложную арифметику, чтобы написать условие расстояния, но оказалось, что писать дольше abs((k/n-x)*1j+k%n-y)==1.

Python 2 , 70 байт

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]

Попробуйте онлайн!

октава , 90 байт

При этом используется геометрический подход: сначала мы создаем матрицу нулей желаемого размера и устанавливаем 1в нужное место. Затем мы свернем с ядром

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

которая производит новую матрицу того же размера с матрицами в 4-соседях исходной точки. Тогда мы find()индексы ненулевых элементов этой новой матрицы.

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

Попробуйте онлайн!

^{_{свертка является ключом к успеху.}}

Wolfram Language (Mathematica) , 42 байта

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

Попробуйте онлайн!

1-индексированный (что соответствует соглашению Mathematica об индексации). Принимает вход как {x,y}, {m,n}.

для 0-индексированного ввода-вывода 45 байтов :

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

Попробуйте онлайн!

JavaScript (ES6), 74 байта

Скучный подход.

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

Попробуйте онлайн!

JavaScript (Node.js) , 74 байта

Менее скучно, но так же долго. Принимает вход как ([h,w,x,y]).

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

Попробуйте онлайн!

JavaScript (V8) , 67 байт

Если бы были разрешены все стандартные методы вывода, мы могли бы просто напечатать действительные координаты с помощью:

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

Попробуйте онлайн!

Желе ,  13  12 байт

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

Двоичный Ссылка принимая список из двух (0-индексированных) целых чисел на левой стороне , [row, column]и два целых числа по правому [height, width], что дает список списков целых чисел, [[adjacent_row_1, adjacent_column_1], ...].

Попробуйте онлайн!

Как?

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 байт

-7 байт благодаря nwellnhof!

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

Попробуйте онлайн!

Удаляет элементы out of bounds, проверяя, находится ли он при делении на границы массива между 0 и 1. Принимает ввод и вывод через комплексные числа, где действительная часть - это xкоордината, а мнимая - это y. Вы можете извлечь их через .imи .reфункции.

J , ^{30 29} 28 байт

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

Попробуйте онлайн!

Как:

• Поверните правую руку mхn арг в сетку комплексных чиселj./&i./
• То же самое для левого arg (наша точка) j./
• Создайте маску, показывающую, где расстояние между нашей точкой и сеткой ровно 1 1=|@-
• Используйте это для фильтрации сетки, после выравнивания обоих #~&,
• Преврати результат в реальные очки +.@

C # (интерактивный компилятор Visual C #) , 91 байт

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

Попробуйте онлайн!

В качестве альтернативы:

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

Попробуйте онлайн!

Древесный уголь , 29 байт

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

Попробуйте онлайн! Ссылка на подробную версию кода. Принимает входные данные в порядке x, y, ширина, высота. Объяснение:

Ｊθη#

Распечатайте #в предоставленной позиции.

ＦＩζＦＩε«

Зациклите данный прямоугольник.

Ｊικ

Перейти к текущей позиции.

¿№ＫＶ#⊞υ⟦ικ⟧

Если есть соседний, #сохраните позицию.

»⎚Ｉυ

Вывести обнаруженные позиции в конце цикла.

Скучный ответ:

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

Попробуйте онлайн! Ссылка на подробную версию кода. Работает, находя соседние позиции математически.

Haskell, 62 байта

С помощью

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

Попробуйте онлайн!

Скучный подход: 81 байт

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