35
\$\begingroup\$

Task

Given the situation with this global pandemic, you've been enlisted to help maintain social distancing. Your challenge, should you choose to accept it, is to write a program that takes in the positions of a group of people and checks whether the group is following social distancing rules. Your program must output a truthy value if social distancing guidelines are being met else output a falsy value.

People must always be six spaces apart:

[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]] -> True

[[1, 0, 0, 0, 0, 0, 0, 1]] -> True

[[1, 0, 0, 0, 0, 0, 1]] -> False

[[1, 0, 0, 1]] -> False

[[1],
 [0],
 [0],
 [0],
 [0],
 [1]] -> False

[[1],
 [0],
 [0],
 [0],
 [0],
 [0],
 [0],
 [1]] -> True

For the purpose of this challenge, instead of measuring distance with Pythagoras's theorem, we measure the distance as the length of the shortest path between two people, so this example outputs true:

[[1, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 1,]] -> True

Since the shortest path passes through at least six squares.

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

Your algorithm must be deterministic (i.e., always produce the same output).

Your program should also, at least in theory, work for inputs containing more than five people and needs to work for a two dimensional input.

Input and Output

Your input can be the a nested array in STDIN or any other input format that doesn't break the standard loopholes.

Output has to be written to STDOUT or closest alternative. Output should consist of a truthy or falsy value (or a string representation thereof).

Additional Rules and Examples

[[1, 0, 0, 0, 0, 0, 1, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 1, 0, 0, 0, 0, 0, 1,]] -> False

[[1, 0, 0, 0, 0, 0, 0, 1, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 1, 0, 0, 0, 0,]] -> True

[[1, 0, 0, 0, 0, 0, 0, 1, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 1, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [1, 0, 0, 0, 0, 0, 0, 0, 1,]] -> True

[[1, 0, 0, 0, 0, 0, 0, 1, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 1, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 1, 0,],
 [0, 1, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 1, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 1, 0,],
 [0, 0, 0, 1, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0,],
 [1, 0, 0, 0, 0, 0, 0, 0, 1,]] -> False
  • Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

    The language Piet, for example, will be scored in codels, which is the natural choice for this language.

    Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

  • If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

  • Unless they have been overruled earlier, all standard rules apply.

\$\endgroup\$
  • 2
    \$\begingroup\$ I've removed my comment asking you not to assume that I/O is processed through STDIN/STDOUT exclusively, because you do mention or closest alternative. Still, you should just rely on our default rules rather than re-writing them. Nice first challenge anyway! \$\endgroup\$ – Arnauld May 19 at 12:58
  • 2
    \$\begingroup\$ Consider converting your test cases to valid JSON (without trailing ,s in lists). \$\endgroup\$ – Adám May 19 at 13:24
  • 3
    \$\begingroup\$ FWIW, the way you calculate the distance is called Manhattan distance or Taxicab metric, more info en.wikipedia.org/wiki/Taxicab_geometry \$\endgroup\$ – SJuan76 May 19 at 20:16
  • 6
    \$\begingroup\$ I am sorry but I have downvoted this for what others may perceive to be a trivial reason: Code Golf is one of the few things I have left where I can escape how fucked my world has become; I absolutely do not want to come here to be reminded that I can't hug my family and friends. \$\endgroup\$ – Shaggy May 19 at 21:19
  • 4
    \$\begingroup\$ @Shaggy I feel you (although I upvoted, because it’s a good challenge in general). Also, I don’t like challenges that seem to exploit a popular but unfortunate situation \$\endgroup\$ – Luis Mendo May 19 at 22:07

14 Answers 14

26
\$\begingroup\$

Python 2 with SciPy, 105 101 99 bytes

-1 byte thanks to @vroomfondel !

lambda l:N.all(S.convolve2d(l,N.outer(*[N.r_[:7]-3]*2)**2<9)<2)
import numpy as N,scipy.signal as S

Try it online!

A function that takes in a 2D list, and returns a boolean representing whether social distancing guidelines are met.

Big idea

For each position in the array, there can only be at most 1 person within a 3 unit radius around that position. (If there are 2 people near that position, then they are at most 5 units apart.)

We can use convolution to count how many people are within a 3 unit radius of any point. The kernel specifies all positions at most 3-unit away from the current point:

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

After convolution, we just need to check if all positions are less than 2.

The following examples show the results of the convolution (0 is replaced with . for visual clarity):

                   ...1......1....
                   ..111....111...
                   .11111..11111..
1......1.          11111111111111.
.........          .11111..11111..
.........          ..111....111...
.........     -->  ...1...1..1....
.........          ......111......
.........          .....11111.....
....1....          ....1111111....
                   .....11111.....
                   ......111......
                   .......1.......

                   ...1......1....
                   ..111....111...
                   .11111.111111..
1......1.          11111122211111.
.........          .111121122211..
....1....          ..1131111332...
.........          ...2121222211..
.......1.          ..111133311111.
.1.......     -->  .111122322211..
....1....          ..1122311332...
.........          ...1132222211..
.......1.          ...12123311211.
...1.....          ..12211222222..
.........          .1112211122211.
1.......1          111112211121111
                   .111111..11111.
                   ..111.....111..
                   ...1.......1...

Code explanation

The only tricky part is to create the kernel. First, we use numpy.outer to find the outer product of 2 arrays:

>> numpy.r_[:7]
[0 1 2 3 4 5 6]

>> numpy.r_[:7] - 3
[-3 -2 -1 0 1 2 3]

>> numpy.outer([-3,-2,-1,0,1,2,3], [-3,-2,-1,0,1,2,3])
[[ 9  6  3  0 -3 -6 -9]
 [ 6  4  2  0 -2 -4 -6]
 [ 3  2  1  0 -1 -2 -3]
 [ 0  0  0  0  0  0  0]
 [-3 -2 -1  0  1  2  3]
 [-6 -4 -2  0  2  4  6]
 [-9 -6 -3  0  3  6  9]]

Then, we only keep the elements whose absolute value is less than 3.

>> numpy.outer(...)**2 < 9

[[0 0 0 1 0 0 0]
 [0 0 1 1 1 0 0]
 [0 1 1 1 1 1 0]
 [1 1 1 1 1 1 1]
 [0 1 1 1 1 1 0]
 [0 0 1 1 1 0 0]
 [0 0 0 1 0 0 0]]
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Always an upvote for convolution :-) \$\endgroup\$ – Luis Mendo May 19 at 20:18
  • 1
    \$\begingroup\$ Nice! You can save a byte by changing the second argument of the convolve call to N.outer(*[range(-3,4)]*2)**2<9 \$\endgroup\$ – vroomfondel May 20 at 22:01
10
\$\begingroup\$

R, 42 bytes

function(m)all(dist(which(m>0,T),"man")>6)

Try it online!

Pretty self-explanatory - anonymous function that checks whether Manhattan distances between the coordinates of each non-zero entry of the input is greater than 6.

| improve this answer | |
\$\endgroup\$
9
\$\begingroup\$

APL (Dyalog Unicode), 18 17 bytes

-1 thanks to Bubbler.

Full program. Input: Expression for Boolean (0/1) matrix via STDIN. Output: 0 or 1 to STDOUT.

(×≡6∘<)+/¨|∘.-⍨⍸⎕

Try it online!

 prompt for matrix

ɩndices of trues

∘.-⍨ (y,x) distances between all combinations of coordinate pairs

| absolute value

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

() apply the following tacit function to that:

6∘< the matrix mask indicating (0/1) where greater than six

×≡ does it match the matrix of signums (0/1)?

In effect, this checks if all non-zero distances are greater than six.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ ~1∊1 7⍸, -> (×≡6∘<); tacit (×≡6∘<)1⊥¨∘|⍸∘.-⍸ has the same byte count. \$\endgroup\$ – Bubbler May 20 at 0:30
  • \$\begingroup\$ @Bubbler Thanks. \$\endgroup\$ – Adám May 20 at 6:59
6
\$\begingroup\$

Jelly, 11 bytes

ŒṪŒcạ/€§>6Ạ

A monadic Link accepting a multi-dimensional list which yields an integer: 1 if distancing has been maintained; 0 if not.

Try it online! Or see the test-suite.

How?

ŒṪŒcạ/€§>6Ạ - Link: list
ŒṪ          - multi-dimensional truthy indices
  Œc        - pairs
      €     - for each:
     /      -   reduce by:
    ạ       -     absoulute difference (vectorises)
       §    - sums
        >6  - greater than six? (vectorises)
          Ạ - all truthy?
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

Wolfram Language (Mathematica), 59 48 bytes

Saved 11 bytes and removed the imperfections thanks to user202729's great comment!

Min[Tr@Abs[#-#2]&@@@#~Position~1~Subsets~{2}]>5&

Try it online!

Unnamed function taking an array of 0s and 1s as input and returning True or False.

  • #~Position~1 finds the coordinates of the people in the input array.
  • ~Subsets~{2} collects all unordered pairs of such coordinates.
  • Tr@Abs[#-#2]&@@@ sums the absolute values of coordinatewise differences inside each such pair.
  • Min[...]>5& tests whether the differences comprise sufficient social distancing.

In addition to being shorter than the other Mathematica answer, this implementation has the property that it works on inputs of any dimensions (even uneven arrays). Social distancing in spacetime, anyone...?

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Can be reduced to 48 bytes with Subsets (and also work when there is no person present). \$\endgroup\$ – user202729 May 20 at 1:55
  • \$\begingroup\$ Norm[#-#2,1] also works in place of Tr@Abs[#-#2], but doesn't seem to work with the ~ syntax and is as long :( \$\endgroup\$ – my pronoun is monicareinstate May 20 at 3:05
  • \$\begingroup\$ still, nice to know that Norm has that flexibility! \$\endgroup\$ – Greg Martin May 20 at 5:30
6
\$\begingroup\$

JavaScript (ES6),  93 84 82  80 bytes

Takes a binary matrix as input and returns a Boolean value.

f=(m,X,Y)=>m.every((r,y)=>r.every((v,x)=>v?1/X?x<X|x-X+y-Y>6:f(m,x,y,r[x]--):1))

Try it online!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 20 bytes

˜ƶ0K<Iнg‰2.Æε`αO7@}P

Try it online or verify all test cases.

Explanation:

˜                     # Flatten the (implicit) input-matrix
 ƶ                    # Multiply each value by its 1-based index
  0K                  # Remove all 0s
    <                 # Decrease each by 1 to make it 0-based indexing
     I                # Push the input-matrix again
      нg              # Pop and get the width of the matrix (length of the first row)
        ‰             # Divmod each integer by this row-length to get all coordinates
         2.Æ          # Get all possible pairs of coordinates
            ε         # Map each pair of coordinates to:
             `        #  Pop and push the coordinates separated to the stack
              α       #  Take the absolute differences of both the x and y coordinates
               O      #  Sum those two together
                7@    #  And check whether it's >= 7
                  }P  # After the map: check if all were truthy
                      # (after which the result is output implicitly)
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 63 bytes

2>Max@ListConvolve[Table[Boole[i<j],{i,8},{j,8}],#~ArrayPad~9]&

Try it online!

The list convolution kernel Table[Boole[i<j],{i,8},{j,8}] can be generated as UpperTriangularize@ConstantArray[1,{7, 7}] too (using more built-in), but that's longer.

Unlike most (all?) other solutions posted, this solution only have time complexity O(n) in terms of the input size (with a possibly large constant factor)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice use of convolution \$\endgroup\$ – Luis Mendo May 19 at 20:19
5
\$\begingroup\$

Python 3, 99 bytes

Takes as input a list of lists \$ l \$, and outputs True if social distancing is not followed, and False otherwise.

eval(f"lambda l:any(s&q>0<abs(a-c)+abs(b-d)<7{'for %s,%s in enumerate(%s)'*4%(*'aplbqpcrldsr',)})")

Try it online!

Explanation

We can reduce the following code to 99 bytes by using the fact that the expression for a,b in enumerate(c) is used a total of four times, which can be condensed.

Python 3, 111 bytes

lambda l,E=enumerate:any(s&q>0<abs(a-c)+abs(b-d)<7for a,p in E(l)for b,q in E(p)for c,r in E(l)for d,s in E(r))

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

MATL, 18 17 bytes

1Ya&fht1&ZP7<zGz=

Outputs 1 if the input satisfies the distance rule, and 0 otherwise.

Try it online! Or verify all test cases.

Explanation

Consider the following input as an example:

[1 0 0 0 0 0 1 0 0 0;
 0 0 0 0 0 0 0 0 0 0;
 0 0 0 0 0 0 0 0 0 0;
 0 0 0 0 0 0 0 0 0 0;
 0 0 0 1 0 0 0 0 0 1]

      % Implicit input
1Ya   % Padarray with size 1 along the first dimension. This extends the
      % input with two rows of zeros. The purpose if this is to ensure that
      % the modified input will never be a row vector
      % STACK: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
                1, 0, 0, 0, 0, 0, 1, 0, 0, 0;
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
                0, 0, 0, 1, 0, 0, 0, 0, 0, 1;
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
&f    % Two-output find: row and column indices of nonzeros. This gives the
      % result as column vectors (it would give row vectors if the input
      % argument were a row vector, but the previou steps ensures that will
      % not happen) 
      % STACK: [1; 5; 1; 5], [1; 4; 7; 10]
h     % Concatenate horizontally
      % STACK: [1 1; 5 4; 1 7; 5 10]
t     % Duplicate
      % STACK: [1 1; 5 4; 1 7; 5 10], [1 1; 5 4; 1 7; 5 10]
1&ZP  % Cityblock distance between rows of the two matrices. Gives a matrix
      % with the distances. The diagonal contains 0
      % STACK: [0  7  6 13;
                7  0  7  6;
                6  7  0  7;
               13  6  7  0]
7<    % Less than 7? Element-wise. The diagonal contains 1. An off-diagonal
      % entry is 1 if and only the distance condition is not satisfied for
      % that pair of people
      % STACK: [1 0 1 0;
                0 1 0 1;
                1 0 1 0;
                0 1 0 1]
z     % Number of nonzeros
      % STACK: 8
Gz    % Push input again. Number of nonzeros
      % STACK: 8, 4
=     % Equal?
      % STACK: 0
      % Implicit display
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 87 bytes

M`10{0,5}1|(?<=(.)*)(?=(1)){6}(?<-2>.*\n)+(?>(?<-1>.)*)((?<-2>0)*1|0(?<=1(?<-2>0)*))
^0

Try it online! Takes input as a linefeed-separated character array and outputs 1 or 0 (outputting 0 or 1 would save 3 bytes; outputting 0 or non-0 would save 5 bytes). Explanation:

10{0,5}1|

Are two 1s on the same row fewer than 6 0s apart? Otherwise,

(?<=(.)*)

Count the current column in $#1.

(?=(1)){6}

Store 6 in $#2, plus ensure that we're matching a 1.

(?<-2>.*\n)+

Move down rows, decrementing $#2 each time. (If $#2 runs out, this match fails, so the regex engine has to try fewer rows or starting at a different 1.)

(?>(?<-1>.)*)

Move across to column $#1.

((?<-2>0)*1|0(?<=1(?<-2>0)*))

Try looking either right or left for a 1 that is no more than $#2 0s away, meaning that it is not sufficiently distant.

M`
^0

The above regex looks for insufficiently distant pairs, so check whether none were found to give the desired result.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8), 126 bytes

e=>(e.map((w,x)=>w.map((t,y)=>t?p.push({x,y}):''),p=[],d=Math.abs),p.every(r=>p.filter(t=>d(r.x-t.x)+d(r.y-t.y)<7).length==1))

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

perl -E, 157 bytes

@b=map{[/\d/g]}<>;for$x(@a=keys@b){for$z(@a){for$y(@c=keys@{$b[0]}){for$w(@c){$t||=$b[$x][$y]&&$b[$z][$w]&&abs($x-$z)+abs($y-$w)<7&&($x!=$z||$y!=$w)}}}}say$t

Try it online!

Prints a false value (0, or empty string) if all people are at least distance 6 away, and prints 1 if there is at least one pair of people with less distance.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 3.8 or newer, 137 135 bytes

lambda m:(p:=[(r,c)for r in range(len(m))for c in range(len(m[0]))if m[r][c]])and all(abs(a-c)+abs(b-d)>6for(a,b),(c,d)in zip(p,p[1:]))

Try it online!

| improve this answer | |
\$\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.