Sitzplätze in einem finnischen Kino

52

Sie erhalten die Karte eines Kinos als boolesche Matrix: 0 steht für einen freien Platz, 1 - belegt. Jeder hereinkommende Finne wählt den Sitz, der am weitesten ( euklidische Entfernung ) vom nächsten besetzten Platz entfernt ist, oder, falls es mehrere solcher Plätze gibt, den ersten in der Reihe nach . Geben Sie eine Matrix aus, die zeigt, in welcher Reihenfolge die Plätze belegt sein werden. das heißt, ersetzen Sie die Nullen durch 2, 3, 4 usw

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

Das I / O-Format ist innerhalb der für Ihre Sprache geltenden Code-Golfnormen flexibel. Sie können davon ausgehen, dass die Eingabe korrekt ist, mindestens 3x3 groß ist und nicht vollständig aus demselben Booleschen Wert besteht. Schreiben Sie eine Funktion oder ein vollständiges Programm. Die kürzeste Lösung pro Sprache wird als Sieger gewertet. Es wird keine Antwort akzeptiert. Standardlücken sind verboten.

code-golf matrix ngn
quelle
6
@Mego Als unsozialer Mensch kann ich bestätigen, dass ich lieber zwei Sitze zur Seite oder zwei Sitze hinter jemandem sitze als diagonal einen Sitz hinter und zur Seite.
Pavel
17
@ Mego persönlichen Raum wird mit euklidischen Abstand berechnet :)
Angs
2
@Pavel Asozial, nicht asozial?
Chromatix
2
@ Chromatix Nope. Ich möchte, dass die Gesellschaft brennt. : P
Pavel
12
@Pavel infernosocial :)
ngn

Antworten:

11

MATL , 37 Bytes

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

Probieren Sie es online! Oder überprüfen Sie alle Testfälle . Vielleicht möchten Sie auch sehen, wie das Kino mit ASCII-Kunst gefüllt wird .

Erläuterung

!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
Luis Mendo
quelle
11

JavaScript (ES6), 156 137 Bytes

18 Bytes dank @ l4m2 eingespart

Das ist ziemlich viel 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

Probieren Sie es online!

Kommentiert

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[]
Arnauld
quelle
Probieren Sie es online!
l4m2
b=b<(d=X*X--+Y*Y)|!v?b:d
14 m²,
v|b<=B v|ist unnötig, denn wenn vdannb=0
l4m2
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

Nimmt die Eingabe als Array. Eingang und Ausgang sind in umgekehrter Reihenfolge. Gutschrift für Fixpunktzauber nach Laikoni .

Probieren Sie es online!

Angs
quelle
1
180 Bytes mituntil((==)=<<f)f
ovs
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

Probieren Sie es online!

-13 Bytes danke an einen Tipp von Not that Charles durch Entfernen der nicht benötigten Prüfung auf Zellen mit dem Wert 0.

Chas Brown
quelle
Ich habe fast die gleiche Lösung, aber Python3, eine Funktion und 194 Bytes
Nicht das Charles
Anstatt meine zu posten, ist die größte Ersparnis, dass ich ,v,udas Ende des Generators nach innen hinzufüge max, und Sie müssen es nicht tun, if a[v][u]<1da dies sein wird 0und daher nicht max. Also meine Linie ist im Grunde*_,y,x=max((min(...),-v,-u,v,u)for v,u in P)
Nicht, dass Charles
Erstaunlich ähnlicher Code. Beeindruckend.
Nicht dass Charles
Ehrlich gesagt, ich bin mir nicht sicher, ob das Hinzufügen der *,v,uZeichen eine Ersparnis im Vergleich zu den Zeichen ist, die --Sie haben. :)
Nicht dass Charles
@Not that Charles: Nett, total verpasst, dass das if a[v][u]<1überflüssig ist (da von Null verschiedene Zellen eine min()von haben 0).
Chas Brown
3

APL (Dyalog) , 39 Bytes

Danke Cows quack für das Speichern eines Bytes und ngn für das Speichern eines anderen

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

Probieren Sie es online!

H.PWiz
quelle
2

APL (Dyalog Unicode) , 44 Byte

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

Probieren Sie es online!

Alternative Lösung bei 44 Bytes

{≢∪∊⍺}@1@{q=⌈/,q←⌊⌿+.×⍨¨(⍸×⍵)∘.-⍳⍴⍵}⍨⍣(~0∊⊣)
Kritixi Lithos
quelle
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 ist ein Vec-of-Vecs M, der in a loopvon geändert wird assoc-in. Wenn kein freier Platz gefunden wird ( if-let), wird das Ergebnis zurückgegeben.

NikoNyrh
quelle
1

Jelly , 35 33 30 29 Bytes

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

Probieren Sie es online!

Ersetzte die ×ı+mit æị(Komplexer Mähdrescher), eine neue Dyade, die auf j.von J basiert und ein Byte spart.

Hier ist eine effizientere Version für TIO. Probieren Sie es online!

Erläuterung

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
Meilen
quelle