53
\$\begingroup\$

You're given the map of a cinema theatre as a boolean matrix: 0 represents a free seat, 1 - occupied. Each Finn who walks in chooses the seat farthest away (Euclidean distance) from the nearest occupied one, or if several such exist - the first among them in row-major order. Output a matrix showing the order seats will eventually be occupied in; that is, replace the 0s with 2, 3, 4, etc

// in
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
// out
 2  8  3  9  1
10  5 11  6 12
 4 13 14 15  7
16 17  1  1 18

// in
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 1 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1 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 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 1 0 0 0
// out
  5  43  17  44  45  46  18  47   8  48  49   6  50  19  51   2
 52  24  53  54   1  55  56  25  57  26  58  59  27  60  28  61
 20  62  63  29  64  65   1  66  30  67  68  21  69   9  70  71
 72  73   1  74  31  75  76  77  78   1  79  80  32  81  82  11
 12  83  84   1  85  86  87  13  88  89  90  14  91  92  33  93
 94  34  95  96  97  15  98  99  35 100  36 101 102   1 103  22
104 105  37 106  38 107  39 108 109  16 110  40 111 112  41 113
  4 114 115   7 116  23 117   3 118 119  42 120   1 121 122  10

// in
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 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 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
// out
  2  38 39  26  40   6 41  42  12  43  44   7  45  46  27  47   3
 48  49 15  50  28  51 52  29  53  30  54  55  56  16  57  31  58
 32  59 60  33  61  62 17  63  64  65  18  66  67  68  34  69  35
 70  10 71  72  13  73 74  75   1  76  77  78  11  79  80  14  81
 82  83 36  84  85  86 21  87  88  89  22  90  91  37  92  93  94
 19  95 96  97  23  98 99 100  24 101 102 103  25 104 105 106  20
107 108  4 109 110 111  8 112 113 114   9 115 116 117   5 118 119

I/O format is flexible within the established code golfing norms for your language. You can assume the input is correct, of size at least 3x3, and doesn't consist entirely of the same boolean value. Write a function or a complete program. The shortest solution per language is considered the winner; no answer will be accepted. Standard loopholes are forbidden.

\$\endgroup\$
9
  • 6
    \$\begingroup\$ @Mego As an antisocial person, I can confirm that I would rather sit two seats to the side or two seats behind someone rather than diagonally one seat behind and to the side. \$\endgroup\$
    – Pavel
    Apr 15, 2018 at 16:47
  • 17
    \$\begingroup\$ @Mego personal space is calculated with euclidean distance :) \$\endgroup\$
    – Angs
    Apr 15, 2018 at 16:47
  • 2
    \$\begingroup\$ @Pavel Asocial, not antisocial? \$\endgroup\$
    – Chromatix
    Apr 15, 2018 at 18:21
  • 2
    \$\begingroup\$ @Chromatix Nope. I want society to burn. :P \$\endgroup\$
    – Pavel
    Apr 15, 2018 at 18:32
  • 13
    \$\begingroup\$ @Pavel infernosocial :) \$\endgroup\$
    – ngn
    Apr 15, 2018 at 18:39

12 Answers 12

12
\$\begingroup\$

MATL, 37 bytes

!t~z:Q"@yX:gG&n:!J*w:+X:&-|w/X<&X>(]!

Try it online! Or verify all test cases. You may also want to see the cinema being filled up in ASCII art.

Explanation

!t        % Implicit input: M×N matrix of zeros and ones. Transpose and duplicate.
          % The transpose is needed because MATL uses column-major (not row-major)
          % order. It will be undone at the end
~z        % Number of zeros, say Z
:Q        % Range, add 1 element-wise: gives the array [2, 3, ..., Z+1]. These are
          % the new values that will be written into the matrix
"         % For each k in that array
  @       %   Push k. Will be written in a position to be determined
  y       %   Duplicate from below: pushes a copy of the current matrix, that has
          %   values up to k-1 already written in
  X:      %   Linearize into an (R*C)×1 vector, in column-major order
  g       %   Convert to logical: this replaces non-zero values by 1 
  G&n     %   Push input size as two separate numbers: M, N
  :!      %   Range, transpose: gives the column vector [1; 2; ...; N]
  J*      %   Multiply by imaginary unit, 1j, element-wise
  w:      %   Swap, range: gives the row vector [1, 2, ..., M]
  +       %   Add, with broadcast. Gives an N×M complex matrix defining a grid of
          %   coordinates: [1+1j, ..., M+1j; 2+1j, ... 2+1j; ...; N+1j, ..., N+Mj]
  X:      %   Linearize into an (M*N)×1 vector, in column-major order
  &-|     %   (M*N)×(M*N) matrix of absolute differences. This gives all distances
          %   between seats. Rows of this matrix represent currently used seats,
          %   and columns correspond to potential new positions
  w/      %   Swap, divide with broadcast. This divides the rows representing
          %   occupied seats by 1, and those with unocuppied seats by 0. So the
          %   latter rows are set to infinity, which effectively removes them for
          %   the subsequent minimization
  X<      %   Mimimum of each column: this gives the minimum distance to currently
          %   occupied seats for each potential new seat
  &X>     %   Argument maximum: gives the index of the first maximizing value
  (       %   Write value k at that position, using linear indexing
]         % End
!         % Transpose. Implicit display
\$\endgroup\$
11
\$\begingroup\$

JavaScript (ES6), 156 137 bytes

Saved 18 bytes thanks to @l4m2

That's quite a lot of map() ...

f=(a,n=1)=>a.map(B=(r,y)=>r.map((_,x)=>a.map(b=q=>q.map(v=>b=b<(d=X*X--+Y*Y)|!v?b:d,X=x)&Y--,Y=y)|v|b<=B||(R=r,C=x,B=b)))|B?f(a,R[C]=++n):a

Try it online!

Commented

f = (a, n = 1) =>               // a = input array; n = seat counter
  a.map(B =                     // initialize B to a non-numeric value
    (r, y) =>                   // for each row r at position y in a[]:
    r.map((_, x) =>             //   for each target seat at position x in r[]:
      a.map(b =                 //     initialize b to a non-numeric value
        q =>                    //     for each row q in a[]:
        q.map(v =>              //       for each reference seat v in q[]:
          b = b < (             //         if b is less than d, defined as
            d = X * X-- + Y * Y //           the square of the Euclidean distance
          ) | !v ?              //           or the reference seat is empty
            b                   //             let b unchanged
          :                     //           else:
            d,                  //             update b to d
          X = x                 //         start with X = x
        ) & Y--,                //       end of q.map(); decrement Y
        Y = y                   //       start with Y = y
      ) |                       //     end of inner a.map()
      b <= B ||                 //     unless b is less than or equal to B,
      (R = r, C = x, B = b)     //     update B to b and save this position in (R, C)
    )                           //   end of r.map()
  ) | B ?                       // end of outer a.map(); if B was updated:
    f(a, R[C] = ++n)            //   update the best target seat and do a recursive call
  :                             // else:
    a                           //   stop recursion and return a[]
\$\endgroup\$
3
  • \$\begingroup\$ Try it online! \$\endgroup\$
    – l4m2
    Apr 16, 2018 at 3:44
  • \$\begingroup\$ b=b<(d=X*X--+Y*Y)|!v?b:d \$\endgroup\$
    – l4m2
    Apr 16, 2018 at 3:58
  • \$\begingroup\$ v|b<=B v| is unnecessary cuz if v then b=0 \$\endgroup\$
    – l4m2
    Apr 16, 2018 at 18:03
3
\$\begingroup\$

Haskell, 216 213 185 184 bytes

import Data.Array
m a=[snd$maximum a|a/=[]]
f k=k//m[(r,((a,b),maximum(elems k)+1::Int))|s<-[assocs k],((a,b),0)<-s,r<-[minimum[(x-a)^2+(y-b)^2|((x,y),i)<-s,i>0]]]
(until=<<((==)=<<))f

Takes the input as an array. Input and output are in reverse order. Credit for fixed point magic to Laikoni.

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 180 bytes with until((==)=<<f)f \$\endgroup\$
    – ovs
    Sep 15, 2018 at 9:31
3
\$\begingroup\$

Python 2, 200 187 bytes

a=input()
z=len(a[0]);P=[divmod(i,z)for i in range(len(a)*z)];i=2
while 0in sum(a,[]):t,y,x=max((min((u-U)**2+(v-V)**2for V,U in P if a[V][U]),-v,-u)for v,u in P);a[-y][-x]=i;i+=1
print a

Try it online!

-13 bytes thx to a tip from Not that Charles by removing unneeded check for cells being 0.

\$\endgroup\$
5
  • \$\begingroup\$ I have nearly the same solution, but Python3, a function, and 194 bytes \$\endgroup\$ Apr 17, 2018 at 17:59
  • \$\begingroup\$ Instead of posting mine, the main savings is that I add ,v,u to the end of the generator inside max, and you don't need to do if a[v][u]<1 since those will be 0 and therefore not max. So my line is basically *_,y,x=max((min(...),-v,-u,v,u)for v,u in P) \$\endgroup\$ Apr 17, 2018 at 18:04
  • \$\begingroup\$ amazingly similar code, though. wow. \$\endgroup\$ Apr 17, 2018 at 18:05
  • \$\begingroup\$ honestly, i'm not sure adding the *,v,u characters ISN'T a saving vs. the -- you have. :) \$\endgroup\$ Apr 17, 2018 at 18:11
  • \$\begingroup\$ @Not that Charles: Nice, totally missed that the if a[v][u]<1 is redundant (since non-zero cells will have a min() of 0). \$\endgroup\$
    – Chas Brown
    Apr 17, 2018 at 21:30
3
\$\begingroup\$

J, 74 70 60 bytes

(+(1+>./@,)*i.@$(=]i.>./)*<./@(#|@-/])&,j./&i./@$)^:(1#.0=,)

Try it online!

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

APL (Dyalog), 39 bytes

Thanks Cows quack for saving one byte, and ngn for saving another

1⌈2-≢∘⍸-⍴⍴∘⍋⍸∘~{⍵∪⍺[⊃⍒⌊/+.×⍨¨⍺∘.-⍵]}⍣≡⍸

Try it online!

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

Jelly, 43 bytes

,¬J;Ѐ"T€Ẏ©Ʋ€ạ²Sɗþ/Ṃ€MḢị®⁸⁸ẎṀ‘¤ṛ¦€Ḣ}¦µẎċ0Ɗ¡

Try it online!

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

APL (Dyalog Unicode), 44 bytes

{×⍵:⍵⋄≢∪∊⍺}@1@{q=⌈/,q←⌊⌿+.×⍨¨(⍸×⍵)∘.-⍳⍴⍵}⍨⍣≡

Try it online!

Alternate solution at 44 bytes

{≢∪∊⍺}@1@{q=⌈/,q←⌊⌿+.×⍨¨(⍸×⍵)∘.-⍳⍴⍵}⍨⍣(~0∊⊣)
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 121 bytes

Nest[p=Position;ReplacePart[#,#&@@Pick[a=#~p~0,m=Min/@DistanceMatrix[a,N@p[#,x_/;x>0]],Max@m]->Max@#+1]&,#,Total[1-#,2]]&

Try it online!

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

Clojure, 247 bytes

#(let[R(range(count %))C(range(count(% 0)))](loop[M % s 2](if-let[c(ffirst(sort-by last(for[x R y C :when(=((M x)y)0)][[x y](-(nth(sort(for[i R j C :when(>((M i)j)0)](+(*(- i x)(- i x))(*(- j y)(- j y)))))0))])))](recur(assoc-in M c s)(inc s))M)))

Input is a vec-of-vecs M, which is modified in a loop by assoc-in. When no free spot is found (if-let) then the result is returned.

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

Jelly, 35 33 30 29 bytes

ZJæịþJFạþx¥F«/MḢṬ×FṀ‘Ɗo@FṁµÐL

Try it online!

Replaced the ×ı+ with æị (complex combine), a new dyad based on j. from J, saving a byte.

Here is a more efficient version for TIO. Try it online!

Explanation

ZJæịþJFạþx¥F«/MḢṬ×FṀ‘Ɗo@FṁµÐL  Input: matrix M
Z                              Transpose
 J                             Enumerate indices - Get [1 .. # columns]
     J                         Enumerate indices - Get [1 .. # rows]
  æịþ                          Outer product using complex combine
                                 (multiply RHS by 1j and add to LHS)
      F                        Flatten
           F                   Flatten input
          ¥                    Dyadic chain
         x                       Times - Repeat each of LHS by each of RHS
       ạþ                        Outer product using absolute difference
            «/                 Reduce by minimum
              M                Indices of maximal values
               Ḣ               Head
                Ṭ              Untruth - Return a Boolean array with 1's at the indices
                 ×             Times
                     Ɗ         Monadic chain
                  F              Flatten input
                   Ṁ             Maximum
                    ‘            Increment
                      o@       Logical OR
                        F      Flatten input
                         ṁ     Mold - Reshape to match the input
                          µÐL  Repeat until result converges
\$\endgroup\$
0
\$\begingroup\$

K (ngn/k), 81 75 73 72 70 bytes

{(~&/,/){a[*>A*&/+/''b*b:i[&~A:~a]-/:\:i:+!n:(#x;#*x)]:#?a:,/x;n#a}/x}

Try it online!

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