13
\$\begingroup\$

Your goal is to make a function that takes the coordinates of a cell in 2D space and a distance \$r\$ and returns the coordinates of all cells in the input coordinate's von Neumann neighborhood of radius \$r\$. That is, all cells at most \$r\$ away in Manhattan distance. For example, given the following cell coordinates and radius pairs:

[1, 1], 1 -> [0, 1], [1, 0], [1, 1], [1, 2], [2, 1]  
[2, 2], 2 -> [0, 2], [1, 1], [1, 2], [1, 3], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [4, 2]

This is what the von Neumann neighborhood looks like:

Neighborhood

More information about the von Neumann neighborhood can be found here.

This is , so shortest amount of bytes wins!

Improve this question
\$\endgroup\$
10
  • 5
    \$\begingroup\$ Both the Wikipedia article and the images suggest the input cell should be included in the Von Neumann neighboorhood. Can we do this as well? \$\endgroup\$
    – ovs
    Jan 2, 2021 at 22:17
  • 3
    \$\begingroup\$ More test cases would be nice. \$\endgroup\$
    – Adám
    Jan 2, 2021 at 22:18
  • 4
    \$\begingroup\$ Voting "Leave Open" for now as I believe the question is answerable in its current state. While there are some things that would be nice to have clarified, it seems easy enough to determine the author's intent for most. \$\endgroup\$
    – Rydwolf Programs
    Jan 2, 2021 at 22:37
  • 7
    \$\begingroup\$ I think the output should include the input cell because the wikipedia article and the images (as ovs points out) as well as the description ("at most r away", and a cell is 0 units away from itself, which is at most r) all point towards that. \$\endgroup\$
    – hyper-neutrino ♦
    Jan 2, 2021 at 23:31
  • 5
    \$\begingroup\$ Can the output have repetitions? \$\endgroup\$
    – xnor
    Jan 4, 2021 at 3:54

19 Answers 19

Reset to default
5
\$\begingroup\$

APL (Dyalog Extended), 23 bytes

-4 thanks to ovs.

Anonymous tacit infix function, taking coordinates of a cell and radius as left and right arguments. Requires 0-based indexing.

{⍺∘+¨⍵-⍸⍵≥+/¨|∘.,⍨⍵…-⍵}

Try it online!

{…} "dfn"; left argument is ⍺ and right argument is ⍵:

 ⍵…-⍵ inclusive integer range from radius to negative radius

 ∘.,⍨ Cartesian selfie product

 ⊢m← assign to m and pass that

 | absolute values

 +/¨ sum each (gives matrix of Manhattan distances)

 ⍵≥ indicate which ones are less than or equal to the radius

 ⍸ ɩndices where true

 ⍵- subtract from radius

 ⍺∘+¨ add the cell coordinates to each

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ m[⍸...] is the same as ⍵-⍸... (in a different order) with index origin 0: tio.run/##SyzI0U2pTMzJT9dNrShJzUtJTfn/v/… \$\endgroup\$
    – ovs
    Jan 3, 2021 at 0:41
  • \$\begingroup\$ @ovs Thanks. That's clever. \$\endgroup\$
    – Adám
    Jan 3, 2021 at 0:43
3
\$\begingroup\$

Vyxal, 11 bytes

k□0zJẋΠṠUMṠ

Try it online! Takes \$r\$ then the coordinate.

k□          # cardinal directions [[0,1],[1,0],[0,-1],[-1,0]]
  0z        # 0 zipped into self  [[0,0]]
    J       # join                [[0,1],[1,0],[0,-1],[-1,0],[0,0]]
     ẋ      # repeated into a list r times
      Π     # reduce by cartesian product
       Ṡ    # vectorising sum
        U   # remove duplicates
         M  # pair each direction into the input coordinate
          Ṡ # and sum to it
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Perl 5, 64 bytes

sub n($x,$y,$d){map{//;map[$x+$',$y+$_],-$d+abs..$d-abs}-$d..$d}

Try it online!

Saved 4 bytes, thanks to Xcali.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can cut 2 bytes by eliminating $i: Try it online! \$\endgroup\$
    – Xcali
    Jan 5, 2021 at 3:19
  • 1
    \$\begingroup\$ Cut a couple more bytes: Try it online! \$\endgroup\$
    – Xcali
    Jan 5, 2021 at 3:57
2
\$\begingroup\$

05AB1E, 14 13 bytes

-1 thanks to ovs

D(ŸãʒÄO¹s@}€+

Try it online!

Takes input as range, coordinates

Explanation:

D duplicate the range in the stack
( negate
Ÿ push the range [-range..range]
ã Cartesian power
 ʒ filter
  Ä absolute value, vectorizes over each of the coordinates
   O sum - distance from 0,0
    ¹s@ less than or equals to the range
 } end filter
€ map
+ add, with the implicit center coordinate
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ D(Ÿ saves a byte \$\endgroup\$
    – ovs
    Jan 4, 2021 at 15:39
2
\$\begingroup\$

Jelly, 12 bytes

ŒRṗ2AS>³ƲÐḟ+

Try it online!

A dyadic link that accepts the radius and the point.

Explanation

ŒRṗ2AS>³ƲÐḟ+   Main dyadic link accepting r, [x,y]
ŒR             [-r..r]
  ṗ2           [-r..r]^2 (Cartesian product)
         Ðḟ    Filter out by
        Ʋ      (
    A            Absolute value (of both)
     S           Sum
      >³         Greater than r
        Ʋ      )
           +   Add [x,y] to each

Jelly, 13 bytes

ŒRAạ³ŒR;€Ʋ€Ẏ+

Try it online!

A dyadic link that accepts the radius and the point.

Explanation

ŒRAạ³ŒR;€Ʋ€Ẏ+   Main dyadic link accepting r, [x,y]
ŒR              [-r..r]
          €     For each i in [-r..r]
         Ʋ      (
  A               |i|
   ạ³             |(|i| - r)|
     ŒR           [-|(|i| - r)| .. |(|i| - r)|]
       ;€         Join each with i
         Ʋ      )
           Ẏ    Tighten (flatten by one level)
            +   Add [x,y] to each
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

R, 75 bytes

function(c,r)(d=t(expand.grid(c[1]+-r:r,c[2]+-r:r)))[,colSums(abs(d-c))<=r]

Try it online!

How? Un-golfed code

vnn=function(c,r)                       # c = (x,y) coordinates; r = radius
d=expand.grid(c[1]+(-r:r),c[2]+(-r:r))) # d = all combinations of coordinates from x-r to x+r, y-r to y+r
d=t(d)                                  # transpose d so that (x,y) coordinates are rows instead of columns
d[,colSums(abs(d-c))<=r]                # select the columns for which the sum of absolute differences to
                                        # the given (x,y) are less than or equal to r
                                        # (note that R recycles c to subtract it from every pair of elements
                                        # by row in d, so 'd-c' produces all the differences in x,y coordinates)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 41 bytes

oo+#&/@DiamondMatrix@#~Position~1-#-1&

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 52 bytes

(a,b)!r=[(a+k,b+j)|k<-[-r..r],j<-[abs k-r..r-abs k]]

Try it online!

I'm sure someone will figure out a more clever way to do this that isn't nearly so long. But for now I am stumped.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ You can get rid of 1 byte by taking the x and y-coordinates as seperate values instead of a tuple: tio.run/##y0gszk7Nyfn/… \$\endgroup\$
    – ovs
    Jan 4, 2021 at 15:48
  • 1
    \$\begingroup\$ @ovs I'd really don't like taking input and producing output in different manners. I'd prefer to keep it tuple in tuples out, even if a more unconventional/esoteric format saves a byte. \$\endgroup\$
    – Wheat Wizard ♦
    Jan 5, 2021 at 17:26
  • 1
    \$\begingroup\$ This one is a little byte shorter: tio.run/##y0gszk7Nyfn/… \$\endgroup\$
    – Donat
    Dec 23, 2022 at 20:15
1
\$\begingroup\$

J, 28 bytes

+"1](]#~(>:1#.|))>@,@{@;~@i:

Try it online!

  • +"1... Add the left argument (the center point) to each element of the right argument (the width) after transforming the right argument by ...
  • i: The first part of that transformation is the "both direction" integers of the width. Eg, i: 2 produces _2 _1 0 1 2.
  • >@,@{@;~@ Take the Cartesian product of that bi-directional integer list with itself {@;~, flatten the result , and unbox >@.
  • ](]#~...) Now filter that Cartesian product result by the following...
  • (>:1#.|) For each point on the list, is the sum 1#. of the absolute values | of the x and y coordinates greater than or equal to >: the original right arg (the width)?
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 3, 79 bytes

f=lambda s,r:{s}|{(a+x,b+d-x)for d in(1,-1)*r for a,b in f(s,r-1)for x in(0,d)}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 3, 81 bytes

lambda x,y,d:[(x+i,y+j)for i in range(-d,d+1)for j in range(abs(i)-d,d+1-abs(i))]

Try it online!

Three bytes saved, thanks to ovs.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can save a byte by removing the first lambda and you don't need to count the n=: 81 bytes, Try it online! \$\endgroup\$
    – ovs
    Jan 4, 2021 at 15:35
1
\$\begingroup\$

Scala, 61 bytes

(x,y,r)=>for(a<- -r to r;d=r-a.abs;b<-y-d to y+d)yield(x+a,b)

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 82 bytes

$x,$y,$r=$args;-$r..$r|%{$i=$_;($d=($i-replace'-')-$r)..-$d|%{,(($x+$i),($y+$_))}}

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ nice abs! ◕‿◕ \$\endgroup\$
    – mazzy
    Jan 7, 2021 at 19:40
1
\$\begingroup\$

Python 3, 75 bytes

f=lambda s,r:{s}|{(a+x//3,b-1+x%3)for x in(-2,4,0,2)*r for a,b in f(s,r-1)}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Scala, 59 bytes

(x,y,r)=>for(a<- -r to r;d=a.abs-r;b<-d to-d)yield(x+a,y+b)

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 146 bytes

int[][]f(int x,int y,int d){int i=~d,r[][]=new int[1-2*d*i][],p=0,a,j;for(;i++<d;)for(j=a=i<0?d+i:d-i;j>~a;)r[p++]=new int[]{x+i,y+j--};return r;}

Try it online!

minus 6 bytes, thanks to ceilingcat

minus 2 bytes, thanks to ceilingcat

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

JavaScript (V8), 75 bytes

p=>n=>{for(i=-n;i<=n;++i)for(j=k=n-(i*i)**.5;j>=-k;)print(p[0]+i,p[1]+j--)}

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pyth, 38 bytes

AQf!>+ahThGaeTeGH*r-hGHh+hGHr-eGHh+eGH

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Julia 1.0, 58 bytes

(x,y,d)->[(x+i,y+j) for i=-d:d,j=-d:d if abs(i)+abs(j)<=d]

Try it online!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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