Seats in a Finnish cinema

Question

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.

@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. — Pavel, Apr 15, 2018 at 16:47
@Mego personal space is calculated with euclidean distance :) — Angs, Apr 15, 2018 at 16:47

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

\$\begingroup\$ Try it online! \$\endgroup\$
– l4m2
Apr 16, 2018 at 3:44 — 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 — 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 — l4m2, Apr 16, 2018 at 18:03

Angs · Accepted Answer · 2018-04-16 10:14:50Z

3

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!

edited Apr 16, 2018 at 10:14

answered Apr 15, 2018 at 17:55

Angs

4,9572 gold badges15 silver badges36 bronze badges

1

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

Add a comment |

Chas Brown · Accepted Answer · 2018-04-17 21:28:54Z

3

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.

edited Apr 17, 2018 at 21:28

answered Apr 15, 2018 at 20:50

Chas Brown

9,7471 gold badge12 silver badges39 bronze badges

\$\begingroup\$ I have nearly the same solution, but Python3, a function, and 194 bytes \$\endgroup\$
– Not that Charles
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\$
– Not that Charles
Apr 17, 2018 at 18:04
\$\begingroup\$ amazingly similar code, though. wow. \$\endgroup\$
– Not that Charles
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\$
– Not that Charles
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

Add a comment |

miles · Accepted Answer · 2018-04-18 16:00:03Z

3

J, 74 70 60 bytes

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

Try it online!

edited Apr 18, 2018 at 16:00

answered Apr 16, 2018 at 12:29

miles

16.9k2 gold badges28 silver badges94 bronze badges

Add a comment |

H.PWiz · Accepted Answer · 2018-12-19 10:02:28Z

3

APL (Dyalog), 39 bytes

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

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

Try it online!

edited Dec 19, 2018 at 10:02

answered Dec 19, 2018 at 9:40

H.PWiz

11.6k2 gold badges20 silver badges56 bronze badges

Add a comment |

Erik the Outgolfer · Accepted Answer · 2018-04-16 20:03:19Z

2

Jelly, 43 bytes

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

Try it online!

edited Apr 16, 2018 at 20:03

answered Apr 16, 2018 at 12:51

Erik the Outgolfer

40.5k5 gold badges41 silver badges121 bronze badges

Add a comment |

user41805 · Accepted Answer · 2018-12-19 07:07:43Z

2

APL (Dyalog Unicode), 44 bytes

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

Try it online!

Alternate solution at 44 bytes

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

answered Dec 19, 2018 at 7:07

user41805

13.1k6 gold badges40 silver badges87 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2018-04-16 13:23:59Z

1

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!

edited Apr 16, 2018 at 13:23

answered Apr 16, 2018 at 13:07

alephalpha

46.6k7 gold badges61 silver badges172 bronze badges

Add a comment |

NikoNyrh · Accepted Answer · 2018-04-18 15:09:12Z

1

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.

answered Apr 18, 2018 at 15:09

NikoNyrh

2,6319 silver badges8 bronze badges

Add a comment |

miles · Accepted Answer · 2018-04-21 14:26:25Z

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

ngn · Accepted Answer · 2018-12-15 19:40:25Z

0

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!

edited Dec 15, 2018 at 19:40

answered Apr 18, 2018 at 9:11

ngn

15.2k2 gold badges42 silver badges87 bronze badges

Add a comment |

Stack Exchange Network

Seats in a Finnish cinema

12 Answers 12

MATL, 37 bytes

Explanation

JavaScript (ES6), 156 137 bytes

Commented

Haskell, 216 213 185 184 bytes

Python 2, 200 187 bytes

J, 74 70 60 bytes

APL (Dyalog), 39 bytes

Jelly, 43 bytes

APL (Dyalog Unicode), 44 bytes

Wolfram Language (Mathematica), 121 bytes

Clojure, 247 bytes

Jelly, 35 33 30 29 bytes

Explanation

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

Your Answer

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

Linked

Hot Network Questions

Seats in a Finnish cinema

12 Answers 12

MATL, 37 bytes

Explanation

JavaScript (ES6), 156 137 bytes

Commented

Haskell, 216 213 185 184 bytes

Python 2, 200 187 bytes

J, 74 70 60 bytes

APL (Dyalog), 39 bytes

Jelly, 43 bytes

APL (Dyalog Unicode), 44 bytes

Wolfram Language (Mathematica), 121 bytes

Clojure, 247 bytes

Jelly, 35 33 30 29 bytes

Explanation

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

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

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