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!

\$\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\$ 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

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

\$\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
\$\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.

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

Wolfram Language (Mathematica), 41 bytes

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

Try it online!

\$\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.

\$\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)?
\$\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!

\$\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.

\$\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!

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 82 bytes

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

Try it online!

\$\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!

\$\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!

\$\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

\$\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!

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

Pyth, 38 bytes

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

Try it online!

\$\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!

\$\endgroup\$

Your Answer

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

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