Uma necessidade muito comum nas classes de algoritmos e ciência da computação em geral é iterar de forma quadridirecional em uma grade ou matriz (como no BFS ou DFS). Isso geralmente resulta em muitos códigos desajeitados e detalhados, com muita aritmética e comparações em loops. Eu já vi muitas abordagens diferentes disso, mas não posso deixar de pensar que há uma maneira mais concisa de fazer isso.

O desafio é escrever uma função pura que, dada a largura e a altura de um plano finito com n, morigem no ponto (0,0), e as coordenadas (x,y)que podem representar qualquer ponto válido dentro desse plano, retorne um objeto iterável de todos os pontos no plano que sejam de direção 4 adjacente a (x,y).

O objetivo é definir essa função no menor número possível de bytes.

Alguns exemplos para ajudar a ilustrar entrada / saída 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)]

E aqui está um exemplo (este em Python) de uma função que satisfaz as condições:

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

O exemplo acima definiu uma função nomeada, mas funções anônimas também são aceitáveis.

As entradas n, m, x, ysão todos números inteiros de 32 bits não assinados dentro dos seguintes intervalos:

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

A saída deve assumir a forma de um iterável (no entanto, seu idioma de escolha define isso) de pares (x, y).

Esclarecimentos adicionais:

Números complexos (e outras representações / serializações) são válidos desde que o consumidor do iterável possa acessar xe ycomo números inteiros sabendo apenas sua localização.

Índices que não sejam baseados em zero são aceitáveis, mas apenas se o idioma de escolha for um idioma que não seja zero. Se o idioma usar uma combinação de sistemas de numeração, use como padrão o sistema de numeração da estrutura de dados mais comumente usado para representar uma matriz. Se esses ainda são todos conceitos estranhos no idioma especificado, qualquer índice inicial é aceitável.

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]

Experimente online!

Lista os quatro vizinhos e usa o fatiamento de lista para remover aqueles que estão fora dos limites.

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]

Experimente online!

Em vez de verificar qual dos quatro vizinhos está dentro dos limites, fazemos isso da maneira mais lenta de verificar todos os pontos dentro dos limites daqueles que são vizinhos, ou seja, com a distância euclidiana exatamente a 1 (x,y). Também usamos o clássico truque div-mod para iterar sobre uma grade , economizando a necessidade de escrever dois loops como for i in range(m)for j in range(n).

Tentei usar aritmética complexa para escrever a condição de distância, mas ficou mais tempo para escrever 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]

Experimente online!

Oitava , 90 bytes

Isso usa uma abordagem geométrica: primeiro criamos uma matriz de zeros do tamanho desejado e configuramos 1a no local desejado. Então nós convolvemos com o kernel

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

que produz uma nova matriz do mesmo tamanho com as dos 4 vizinhos do ponto original. Então nós find()os índices das entradas diferentes de zero desta nova 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'));

Experimente online!

^{_{convolução é a chave para o sucesso.}}

Wolfram Language (Mathematica) , 42 bytes

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

Experimente online!

Indexado a 1 (que segue a convenção do Mathematica para indexação). Toma entrada como {x,y}, {m,n}.

para E / S indexada em 0, 45 bytes :

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

Experimente online!

JavaScript (ES6), 74 bytes

Abordagem chata.

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

Experimente online!

JavaScript (Node.js) , 74 bytes

Menos chato, mas tão longo. 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]]:[])

Experimente online!

JavaScript (V8) , 67 bytes

Se todos os métodos de saída padrão fossem permitidos, poderíamos simplesmente imprimir as coordenadas válidas com:

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

Experimente online!

Geléia ,  13  12 bytes

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

Um link diádico que aceita uma lista de dois números inteiros (indexados 0) à esquerda [row, column]e dois inteiros à direita [height, width], que produz uma lista de listas de números inteiros [[adjacent_row_1, adjacent_column_1], ...],.

Experimente online!

Quão?

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 graças ao nwellnhof!

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

Experimente online!

Remove os elementos fora dos limites, verificando se, quando dividido pelos limites da matriz, está entre 0 e 1. Obtém entrada e saída através de números complexos, onde a parte real é a xcoordenada e o imaginário é o y. Você pode extraí-los através das funções .ime .re.

J , ^{30 29} 28 bytes

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

Experimente online!

Quão:

• Transforme a mão direita mx narg em uma grade de números complexosj./&i./
• O mesmo para arg esquerdo (nosso ponto) j./
• Crie uma máscara mostrando onde a distância entre o nosso ponto e a grade é exatamente 1 1=|@-
• Use isso para filtrar a grade, depois de achatar os dois #~&,
• Transforme o resultado novamente em pontos reais +.@

C # (compilador interativo do 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)

Experimente online!

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)

Experimente online!

Carvão , 29 bytes

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

Experimente online! Link é a versão detalhada do código. Recebe entradas na ordem x, y, largura, altura. Explicação:

Ｊθη#

Imprima a #na posição fornecida.

ＦＩζＦＩε«

Faça um loop sobre o retângulo especificado.

Ｊικ

Salte para a posição atual.

¿№ＫＶ#⊞υ⟦ικ⟧

Se houver um adjacente #, salve a posição.

»⎚Ｉυ

Saída as posições descobertas no final do loop.

Resposta chata:

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

Experimente online! Link é a versão detalhada do código. Funciona encontrando as posições adjacentes matematicamente.

Haskell, 62 bytes

Usando

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

Experimente online!

Abordagem chata: 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)]