Una necesidad muy común en las clases de algoritmos y la informática en general es iterar en 4 direcciones sobre una cuadrícula o matriz (como en BFS o DFS). Esto a menudo parece dar como resultado una gran cantidad de código torpe y detallado con mucha aritmética y comparaciones dentro de los bucles. He visto muchos enfoques diferentes para esto, pero no puedo evitar la sensación de que hay una forma más concisa de hacerlo.

El desafío es escribir una función pura que, dado el ancho y la altura de un plano finito que se n, morigina en el punto (0,0), y las coordenadas (x,y)que pueden representar cualquier punto válido dentro de ese plano, devuelva un objeto iterable de todos los puntos dentro del plano que sean 4 direcciones adyacente a (x,y).

El objetivo es definir esa función en la menor cantidad de bytes posible.

Algunos ejemplos para ayudar a ilustrar la entrada / salida válida:

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

Y aquí hay un ejemplo (este en Python) de una función que satisface las condiciones:

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

El ejemplo anterior definió una función con nombre, pero las funciones anónimas también son aceptables.

n, m, x, yTodas las entradas son enteros de 32 bits sin signo dentro de los siguientes rangos:

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

La salida debe tomar la forma de un iterable (sin embargo, su lenguaje de elección define eso) de pares (x, y).

Aclaraciones adicionales:

Los números complejos (y otras representaciones / serializaciones) están bien siempre que el consumidor del iterable pueda acceder xy ycomo enteros conociendo solo su ubicación.

Los índices no basados ​​en cero son aceptables, pero solo si el idioma de elección es un idioma no indexado en cero. Si el lenguaje usa una combinación de sistemas de numeración, el sistema de numeración de la estructura de datos más comúnmente usado para representar una matriz es el predeterminado. Si estos todavía son todos conceptos extraños en el idioma dado, cualquier índice inicial es aceptable.

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]

Pruébalo en línea!

Enumera los cuatro vecinos, luego usa el corte de lista para eliminar aquellos que están fuera de los límites.

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]

Pruébalo en línea!

En lugar de verificar cuál de los cuatro vecinos está dentro de los límites, lo hacemos de la manera más lenta de verificar todos los puntos dentro de los límites para aquellos que son vecinos, es decir, tener una distancia euclidiana exactamente a 1 de (x,y). También usamos el clásico truco div-mod para iterar sobre una cuadrícula , ahorrando la necesidad de escribir dos bucles como for i in range(m)for j in range(n).

Intenté usar aritmética compleja para escribir la condición de distancia, pero resultó más largo escribir 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]

Pruébalo en línea!

Octava , 90 bytes

Esto utiliza un enfoque geométrico: primero creamos una matriz de ceros del tamaño deseado y establecemos 1a en la ubicación deseada. Luego nos involucramos con el núcleo

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

que produce una nueva matriz del mismo tamaño con unos en los 4 vecinos del punto original. Luego tenemos find()los índices de las entradas distintas de cero de esta nueva matriz.

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

Pruébalo en línea!

^{_{la convolución es la clave del éxito.}}

Wolfram Language (Mathematica) , 42 bytes

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

Pruébalo en línea!

1-indexado (que sigue la convención de Mathematica para indexar). Toma entrada como {x,y}, {m,n}.

para E / S indexadas a 0, 45 bytes :

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

Pruébalo en línea!

JavaScript (ES6), 74 bytes

Aburrido enfoque.

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

Pruébalo en línea!

JavaScript (Node.js) , 74 bytes

Menos aburrido pero igual de largo. Toma entrada como ([h,w,x,y]).

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

Pruébalo en línea!

JavaScript (V8) , 67 bytes

Si se permitieran todos los métodos de salida estándar, podríamos imprimir las coordenadas válidas con:

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

Pruébalo en línea!

Jalea ,  13  12 bytes

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

Un Enlace diádica aceptar una lista de dos números enteros (0 reajustables) a la izquierda, [row, column]y dos enteros por la derecha [height, width], lo que da una lista de listas de números enteros, [[adjacent_row_1, adjacent_column_1], ...].

Pruébalo en línea!

¿Cómo?

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 gracias a nwellnhof!

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

Pruébalo en línea!

Elimina los elementos fuera de los límites comprobando si cuando se divide entre los límites de la matriz está entre 0 y 1. Toma entrada y salida a través de números complejos donde la parte real es la xcoordenada y el imaginario es el y. Puede extraerlos a través de las funciones .imy .re.

J , ^{30 29} 28 bytes

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

Pruébalo en línea!

Cómo:

• Girar la mano derecha m xn arg en una cuadrícula de números complejosj./&i./
• Lo mismo para el argumento izquierdo (nuestro punto) j./
• Cree una máscara que muestre dónde la distancia entre nuestro punto y la cuadrícula es exactamente 1 1=|@-
• Úselo para filtrar la cuadrícula, después de aplanar ambos #~&,
• Convertir el resultado nuevamente en puntos reales +.@

C # (compilador interactivo de Visual C #) , 91 bytes

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

Pruébalo en línea!

Alternativamente:

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

Pruébalo en línea!

Carbón , 29 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Toma entradas en el orden x, y, ancho, alto. Explicación:

Ｊθη#

Imprima a #en la posición provista.

ＦＩζＦＩε«

Pase sobre el rectángulo dado.

Ｊικ

Salta a la posición actual.

¿№ＫＶ#⊞υ⟦ικ⟧

Si hay un adyacente #, guarde la posición.

»⎚Ｉυ

Salida de las posiciones descubiertas al final del bucle.

Respuesta aburrida:

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

Pruébalo en línea! El enlace es a la versión detallada del código. Funciona encontrando las posiciones adyacentes matemáticamente.

Haskell, 62 bytes

Utilizando

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

Pruébalo en línea!

Aburrido enfoque: 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)]