Un besoin très courant dans les classes d'algorithmes et l'informatique en général est d'itérer dans 4 directions sur une grille ou une matrice (comme dans BFS ou DFS). Cela semble souvent entraîner beaucoup de code maladroit et verbeux avec beaucoup d'arithmétique et de comparaisons dans les boucles. J'ai vu de nombreuses approches différentes à ce sujet, mais je ne peux pas me départir du sentiment qu'il existe une façon plus concise de le faire.

Le défi est d'écrire une fonction pure qui, étant donné la largeur et la hauteur d'un plan fini n, moriginaire d'un point (0,0), et les coordonnées (x,y)qui peuvent représenter n'importe quel point valide dans ce plan, renvoie un objet itérable de tous les points dans le plan qui sont dans 4 directions adjacent à (x,y).

Le but est de définir cette fonction en aussi peu d'octets que possible.

Quelques exemples pour illustrer une entrée / sortie valide:

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

Et voici un exemple (celui-ci en Python) d'une fonction qui remplit les conditions:

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

L'exemple ci-dessus a défini une fonction nommée, mais les fonctions anonymes sont également acceptables.

Les entrées n, m, x, ysont toutes des entiers 32 bits non signés dans les plages suivantes:

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

La sortie doit prendre la forme d'un itérable (cependant votre langue de choix le définit) de paires (x, y).

Précisions supplémentaires:

Les nombres complexes (et autres représentations / sérialisations) sont OK tant que le consommateur de l'itérable peut accéder xet en ytant qu'entiers ne connaissant que leur emplacement.

Les index non basés sur zéro sont acceptables, mais uniquement si la langue de choix est une langue non indexée sur zéro. Si le langage utilise un mélange de systèmes de numérotation, choisissez par défaut le système de numérotation de la structure de données la plus couramment utilisée pour représenter une matrice. Si ce sont encore tous des concepts étrangers dans la langue donnée, tout indice de départ est acceptable.

Python 2 , 66 octets

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

Essayez-le en ligne!

Répertorie les quatre voisins, puis utilise le découpage de liste pour supprimer ceux qui sont hors limites.

Python 2 , 71 octets

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]

Essayez-le en ligne!

Au lieu de vérifier lequel des quatre voisins sont entrants, nous le faisons plus lentement pour vérifier tous les points entrants pour ceux qui sont voisins, c'est-à-dire que la distance euclidienne est exactement à 1 (x,y). Nous utilisons également l' astuce div-mod classique pour parcourir une grille , ce qui évite d'écrire deux boucles comme for i in range(m)for j in range(n).

J'ai essayé d'utiliser une arithmétique complexe pour écrire la condition de distance, mais cela s'est avéré plus long à écrire abs((k/n-x)*1j+k%n-y)==1.

Python 2 , 70 octets

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]

Essayez-le en ligne!

Octave , 90 octets

Cela utilise une approche géométrique: d'abord, nous créons une matrice de zéros de la taille souhaitée, et définissons a 1à l'emplacement souhaité. Puis on convolue avec le noyau

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

ce qui produit une nouvelle matrice de la même taille avec celles aux 4 voisins du point d'origine. Nous avons ensuite find()les indices des entrées non nulles de cette nouvelle matrice.

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

Essayez-le en ligne!

^{_{la convolution est la clé du succès.}}

Wolfram Language (Mathematica) , 42 octets

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

Essayez-le en ligne!

1-indexé (qui suit la convention de Mathematica pour l'indexation). Prend l'entrée comme {x,y}, {m,n}.

pour les E / S indexées 0, 45 octets :

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

Essayez-le en ligne!

JavaScript (ES6), 74 octets

Approche ennuyeuse.

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

Essayez-le en ligne!

JavaScript (Node.js) , 74 octets

Moins ennuyeux mais tout aussi long. Prend l'entrée comme ([h,w,x,y]).

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

Essayez-le en ligne!

JavaScript (V8) , 67 octets

Si toutes les méthodes de sortie standard étaient autorisées, nous pourrions simplement imprimer les coordonnées valides avec:

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

Essayez-le en ligne!

Gelée ,  13  12 octets

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

Un lien dyadique acceptant une liste de deux (0 indexées) entiers sur la gauche, [row, column]et deux entiers sur le côté droit [height, width], ce qui donne une liste de listes de nombres entiers, [[adjacent_row_1, adjacent_column_1], ...].

Essayez-le en ligne!

Comment?

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 octets

-7 octets grâce à nwellnhof!

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

Essayez-le en ligne!

Supprime les éléments hors limites en vérifiant si, lorsqu'il est divisé par les limites du tableau, il est compris entre 0 et 1. Prend l'entrée et la sortie via des nombres complexes où la partie réelle est la xcoordonnée et l'imaginaire est la y. Vous pouvez les extraire via les fonctions .imet .re.

J , ^{30 29} 28 octets

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

Essayez-le en ligne!

Comment:

• Transformez la main droite mx narg en une grille de nombres complexesj./&i./
• Idem pour l'argument gauche (notre point) j./
• Créez un masque montrant où la distance entre notre point et la grille est exactement 1 1=|@-
• Utilisez-le pour filtrer la grille, après avoir aplati les deux #~&,
• Transformez le résultat en points réels +.@

C # (Visual C # Interactive Compiler) , 91 octets

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

Essayez-le en ligne!

Alternativement:

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

Essayez-le en ligne!

Fusain , 29 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Prend les entrées dans l'ordre x, y, largeur, hauteur. Explication:

Ｊθη#

Imprimez un #à l'emplacement prévu.

ＦＩζＦＩε«

Faites une boucle sur le rectangle donné.

Ｊικ

Aller à la position actuelle.

¿№ＫＶ#⊞υ⟦ικ⟧

S'il y a un adjacent, #enregistrez la position.

»⎚Ｉυ

Sortez les positions découvertes à la fin de la boucle.

Réponse ennuyeuse:

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Fonctionne en trouvant mathématiquement les positions adjacentes.

Haskell, 62 octets

En utilisant

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

Essayez-le en ligne!

Approche ennuyeuse: 81 octets

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