Maintain Social Distancing!

Question

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 code-golf rules apply.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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?

Answer 5

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

Answer 6

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!

Answer 7

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)

Answer 8

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)

Answer 9

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!

Answer 10

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

Answer 11

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.

Answer 12

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!

Answer 13

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.

Answer 14

Python 3.8 or newer, ¹³⁷ 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!