Write a function that returns an iterable object of all valid points 4-directionally adjacent to (x, y)

Question

A very common need in algorithms classes and computer science in general is to iterate 4-directionally over a grid or matrix (such as in BFS or DFS). This seems to often result in a lot of clunky and verbose code with a lot of arithmetic and comparisons within loops. I've seen many different approaches to this, but I can't shake the feeling that there's a more concise way to do this.

The challenge is to write a pure function that, given the width and height of a finite plane n, m originating at point (0,0), and coordinates (x,y) that can represent any valid point within that plane, returns an iterable object of all points within the plane that are 4-directionally adjacent to (x,y).

The goal is to define that function in as few bytes as possible.

Some examples to help illustrate valid input/output:

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

And here's an example (this one in Python) of a function that satisfies the 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

The example above defined a named function, but anonymous functions are also acceptable.

The inputs n, m, x, y are all unsigned 32-bit integers within the following ranges:

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

The output must take the form of an iterable (however your language of choice defines that) of (x, y) pairs.

Additional clarifications:

Complex numbers (and other representations/serializations) are OK as long as the consumer of the iterable can access x and y as integers knowing only their location.

Non-zero-based indexes are acceptable, but only if the language of choice is a non-zero-indexed language. If the language uses a mix of numbering systems, default to the numbering system of the data structure most commonly used to represent a matrix. If these are still all foreign concepts in the given language, any starting index is acceptable.

Answer 1

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]

Try it online!

Lists the four neighbors, then uses list slicing to remove those that are out-of-bounds.

---

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]

Try it online!

Instead of checking which of the four neighbors are in-bounds, we do it the slower way of checking all in-bounds points for those that are neighbors, that is have Euclidian distance exactly 1 from (x,y). We also use the classic div-mod trick to iterate over a grid, saving the need to write two loops like for i in range(m)for j in range(n).

I tried using complex arithmetic to write the distance condition, but it turned out longer to write 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]

Try it online!

Answer 2

Octave, 90 bytes

This uses a geometric approach: First we create an matrix of zeros of the desired size, and set a 1 to the desired location. Then we convolve with the kernel

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

which produces a new matrix of the same size with ones at the 4-neighbours of the original point. Then we find() the indices of the nonzero entries of this new matrix.

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

Try it online!

^{_{convolution is the key to success.}}

Answer 3

Wolfram Language (Mathematica), 42 bytes

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

Try it online!

1-indexed (which follows Mathematica's convention for indexing). Takes input as {x,y}, {m,n}.

---

for 0-indexed I/O, 45 bytes:

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

Try it online!

Answer 4

JavaScript (ES6), 74 bytes

Boring approach.

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

Try it online!

---

JavaScript (Node.js), 74 bytes

Less boring but just as long. Takes input as ([h,w,x,y]).

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

Try it online!

---

JavaScript (V8), 67 bytes

If all standard output methods were allowed, we could just print the valid coordinates with:

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

Try it online!

Answer 5

Perl 6, 56 49 bytes

-7 bytes thanks to nwellnhof!

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

Try it online!

Removes the out of bounds elements by checking if when divided by the array bounds it is between 0 and 1. Takes input and output via complex numbers where the real part is the x coordinate and the imaginary is the y. You can extract these through the .im and .re functions.

Answer 6

Jelly,  13  12 bytes

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

A dyadic Link accepting a list of two (0-indexed) integers on the left, [row, column], and two integers on the right, [height, width], which yields a list of lists of integers, [[adjacent_row_1, adjacent_column_1], ...].

Try it online!

How?

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

Answer 7

J, ^{30 29} 28 bytes

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

Try it online!

How:

• Turn the right hand m x n arg into a grid of complex numbers j./&i./
• Same for left arg (our point) j./
• Create a mask showing where the distance between our point and the grid is exactly 1 1=|@-
• Use that to filter the grid, after flattening both #~&,
• Turn the result back into real points +.@

Answer 8

C# (Visual C# Interactive Compiler), 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)

Try it online!

Alternatively:

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

Try it online!

Answer 9

Charcoal, 29 bytes

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

Try it online! Link is to verbose version of code. Takes inputs in the order x, y, width, height. Explanation:

Ｊθη#

Print a # at the provided position.

ＦＩζＦＩε«

Loop over the given rectangle.

Ｊικ

Jump to the current position.

¿№ＫＶ#⊞υ⟦ικ⟧

If there's an adjacent # then save the position.

»⎚Ｉυ

Output the discovered positions at the end of the loop.

Boring answer:

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

Try it online! Link is to verbose version of code. Works by finding the adjacent positions mathematically.

Answer 10

Haskell, 62 bytes

Using

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

Try it online!

Boring approach: 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)]