Kursi di bioskop Finlandia

51

Anda diberi peta teater bioskop sebagai matriks boolean: 0 mewakili kursi gratis, 1 - ditempati. Setiap orang Finlandia yang berjalan memilih kursi yang paling jauh ( jarak Euclidean ) dari yang diduduki terdekat, atau jika ada beberapa yang ada - yang pertama di antara mereka dalam urutan baris utama . Keluaran matriks yang menunjukkan urutan kursi pada akhirnya akan ditempati; yaitu, ganti 0s dengan 2, 3, 4, dll

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

Format I / O fleksibel dalam norma-norma kode golf yang ada untuk bahasa Anda. Anda dapat berasumsi bahwa inputnya benar, dengan ukuran minimal 3x3, dan tidak seluruhnya terdiri dari nilai boolean yang sama. Tulis fungsi atau program lengkap. Solusi terpendek per bahasa dianggap sebagai pemenang; tidak ada jawaban yang akan diterima. Celah standar dilarang.

code-golf matrix ngn
sumber
6
@Mego Sebagai orang yang antisosial, saya dapat mengkonfirmasi bahwa saya lebih suka duduk dua kursi di samping atau dua kursi di belakang seseorang daripada diagonal satu kursi di belakang dan ke samping.
Pavel
17
@Mego ruang pribadi dihitung dengan jarak euclidean :)
Angs
2
@Pavel Asocial, bukan antisosial?
Chromatix
2
@Chatiatix Tidak. Saya ingin masyarakat terbakar. : P
Pavel
12
@Pavel infernosocial :)
ngn

Jawaban:

11

MATL , 37 byte

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

Cobalah online! Atau verifikasi semua kasus uji . Anda mungkin juga ingin melihat sinema yang diisi oleh seni ASCII.

Penjelasan

!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
sumber
11

JavaScript (ES6), 156 137 byte

Disimpan 18 byte berkat @ l4m2

Itu cukup banyak 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

Cobalah online!

Berkomentar

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
sumber
Cobalah online!
l4m2
b=b<(d=X*X--+Y*Y)|!v?b:d
l4m2
v|b<=B v|tidak perlu karena kalau vbegitub=0
l4m2
3

Haskell , 216 213 185 184 byte

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

Mengambil input sebagai array. Input dan output dalam urutan terbalik. Penghargaan untuk magis fixed point ke Laikoni .

Cobalah online!

Angs
sumber
1
180 byte denganuntil((==)=<<f)f
ovs
3

Python 2 , 200 187 byte

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

Cobalah online!

-13 byte thx ke ujung dari Not that Charles dengan menghapus cek yang tidak dibutuhkan untuk sel menjadi 0.

Chas Brown
sumber
Saya memiliki solusi yang hampir sama, tetapi Python3, sebuah fungsi, dan 194 byte
Bukannya Charles
Alih-alih memposting milik saya, penghematan utama adalah bahwa saya menambahkan ,v,uke ujung generator di dalam max, dan Anda tidak perlu melakukan if a[v][u]<1karena itu akan 0dan karena itu tidak maks. Jadi baris saya pada dasarnya*_,y,x=max((min(...),-v,-u,v,u)for v,u in P)
Bukan Charles
kode yang sangat mirip. Wow.
Bukan Charles
jujur, saya tidak yakin menambahkan *,v,ukarakter TIDAK penghematan dibandingkan yang --Anda miliki. :)
Bukan itu Charles
@Not bahwa Charles: Nice, benar-benar merindukan bahwa if a[v][u]<1berlebihan (karena non zero-sel akan memiliki min()dari 0).
Chas Brown
3

APL (Dyalog) , 39 byte

Terima kasih Sapi dukun untuk menyimpan satu byte, dan ngn untuk menyimpan yang lain

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

Cobalah online!

H.Piz
sumber
2

Jelly , 43 byte

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

Cobalah online!

Erik the Outgolfer
sumber
2

APL (Dyalog Unicode) , 44 byte

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

Cobalah online!

Solusi alternatif pada 44 byte

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

Clojure, 247 byte

#(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 adalah vec-of-vecs M, yang dimodifikasi loopoleh assoc-in. Ketika tidak ada tempat bebas ditemukan ( if-let) maka hasilnya dikembalikan.

NikoNyrh
sumber
1

Jelly , 35 33 30 29 byte

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

Cobalah online!

Diganti ×ı+dengan æị(menggabungkan kompleks), angka dua baru berdasarkan j.dari J, menyimpan byte.

Ini adalah versi yang lebih efisien untuk TIO. Cobalah online!

Penjelasan

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
mil
sumber
0

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

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

Cobalah online!

ngn
sumber