19
\$\begingroup\$

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.

\$\endgroup\$
10
  • 6
    \$\begingroup\$ 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! \$\endgroup\$
    – Wheat Wizard
    Sep 12 '19 at 1:31
  • \$\begingroup\$ We're guaranteed that (x,y) itself is in the rectangle, right? \$\endgroup\$
    – xnor
    Sep 12 '19 at 1:50
  • 4
    \$\begingroup\$ 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 \$\endgroup\$
    – Jo King
    Sep 12 '19 at 2:00
  • 3
    \$\begingroup\$ 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 \$\endgroup\$
    – Jo King
    Sep 12 '19 at 2:26
  • 2
    \$\begingroup\$ Is it allowed to represent coordinates as complex numbers rather than integer tuples? \$\endgroup\$
    – Joel
    Sep 12 '19 at 2:50

10 Answers 10

13
\$\begingroup\$

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!

\$\endgroup\$
1
  • 11
    \$\begingroup\$ Congrats on the 100k! \$\endgroup\$
    – Arnauld
    Sep 12 '19 at 8:19
6
\$\begingroup\$

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.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ Indeed it is, no matter how small the font \$\endgroup\$
    – Luis Mendo
    Sep 12 '19 at 12:14
  • \$\begingroup\$ Supbpbpbpberb technique ;-) \$\endgroup\$
    – ojdo
    Sep 17 '20 at 14:54
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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]]
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 13 '19 at 18:06
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 49 bytes \$\endgroup\$
    – nwellnhof
    Sep 13 '19 at 11:32
  • \$\begingroup\$ @nwellnhof Very nice! I'd build on it to do something like this, but div doesn't seem to work for Nums \$\endgroup\$
    – Jo King
    Sep 13 '19 at 11:45
  • \$\begingroup\$ (*.reals>>.Int Zdiv@^b).none or (*.reals Z/@^b)>>.Int.none would work but the Int-cast seems too costly. \$\endgroup\$
    – nwellnhof
    Sep 13 '19 at 11:52
1
\$\begingroup\$

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 +.@
\$\endgroup\$
1
\$\begingroup\$

Haskell, 62 bytes

Using thecircle equation

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)]
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 29 bytes

Jθη#FIζFIε«Jικ¿№KV#⊞υ⟦ικ⟧»⎚Iυ

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

Jθη#

Print a # at the provided position.

FIζFIε«

Loop over the given rectangle.

Jικ

Jump to the current position.

¿№KV#⊞υ⟦ικ⟧

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

»⎚Iυ

Output the discovered positions at the end of the loop.

Boring answer:

FIζFIε¿⁼¹⁺↔⁻ιIθ↔⁻κIηI⟦ικ

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.