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

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.

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.

• Welcome to the site! This challenge is pretty good by our standards, but there are a couple of things here that go against our style. For one we much prefer challenges that do not restrict to a single language if possible. It is much more fun when everyone can compete. We also generally score code-golf in bytes as opposed to characters, they are the same for most purposes but there are a couple of cheaty things you can do if answers are scored in characters. Hope you have fun here! Sep 12, 2019 at 1:31
• We're guaranteed that (x,y) itself is in the rectangle, right?
– xnor
Sep 12, 2019 at 1:50
• By default, CGCC allows full programs as well as functions as submissions. This helps allow languages that don't necessarily have a concept of functions to compete as well
– Jo King
Sep 12, 2019 at 2:00
• An output would be to STDOUT, rather than a code object. This can generally be any output with clear delimiters so it is unambiguous and follow the default Standard output formats
– Jo King
Sep 12, 2019 at 2:26
• Is it allowed to represent coordinates as complex numbers rather than integer tuples?
– Joel
Sep 12, 2019 at 2:50

# 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!

• Congrats on the 100k! Sep 12, 2019 at 8:19

# 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.

• Indeed it is, no matter how small the font Sep 12, 2019 at 12:14
• Supbpbpbpberb technique ;-)
– ojdo
Sep 17, 2020 at 14:54

# 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!

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

• You can replace ḶṚƬ with Ṭ€. 2ḶṚƬNƬẎ returns [[0, 1], [1, 0], [0, -1], [-1, 0]], while 2Ṭ€NƬẎ returns [[1], [0, 1], [-1], [0, -1]], and, since the singletons are wrapped, + only vectorizes with the first element of ⁸ for those, so they act as though their second element is 0 (the additive identity). As a result, only the order of the output may change. Sep 13, 2019 at 18:06

# Wolfram Language (Mathematica), 42 37 bytes

pNorm[{##}-p]&~Array~#~Position~1&


Try it online!

Input [{x,y}][{m,n}]. 1-indexed, following Mathematica's convention.

# 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. • 49 bytes Sep 13, 2019 at 11:32 • @nwellnhof Very nice! I'd build on it to do something like this, but div doesn't seem to work for Nums – Jo King Sep 13, 2019 at 11:45 • (*.reals>>.Int Zdiv@^b).none or (*.reals Z/@^b)>>.Int.none would work but the Int-cast seems too costly. Sep 13, 2019 at 11:52 # J, 3029 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 +.@ # 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)]  # 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! # 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. # Pip-xp, 18 bytes $ALaCGbFI1=$+:_ADc  Takes three command-line arguments: m, n, and a list containing x & y. Replit! Or, here's a similar program in Pip Classic with a header to simulate the -x flag: Try it online! ### Explanation Generates a list of all points in the valid rectangle and filters for the ones that are one unit away from the given point. $ALaCGbFI1=$+:_ADc aCGb Generate a coordinate grid of a rows and b columns$AL                 Fold on append-list: flatten once, giving a list of coord pairs
FI           Filter on this function:
_      The argument