Sièges dans un cinéma finlandais

51

On vous donne la carte d'un cinéma comme une matrice booléenne: 0 représente un siège libre, 1 - occupé. Chaque Finlandais qui entre choisit le siège le plus éloigné ( distance euclidienne ) du siège occupé le plus proche ou, s’il en existe plusieurs, le premier par ordre de rangée . Produisez une matrice indiquant l'ordre dans lequel les sièges seront éventuellement occupés; c'est-à-dire remplacer les 0 par 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

Le format I / O est flexible dans les normes de golf établies par code pour votre langue. Vous pouvez supposer que l'entrée est correcte, qu'elle a une taille d'au moins 3x3 et qu'elle n'est pas entièrement composée de la même valeur booléenne. Ecrivez une fonction ou un programme complet. La solution la plus courte par langue est considérée comme la gagnante. aucune réponse ne sera acceptée. Les échappatoires standard sont interdites.

code-golf matrix ngn
la source
6
@ Mego En tant que personne antisociale, je peux confirmer que je préférerais m'asseoir à deux places ou deux derrière une personne plutôt qu'en diagonale une place derrière et à côté.
Pavel
17
L'espace personnel @Mego est calculé en fonction de la distance euclidienne :)
Angs
2
@Pavel Asocial, pas antisocial?
Chromatix
2
@ Chromatix Nope. Je veux que la société brûle. : P
Pavel
12
@Pavel infernosocial :)
ngn le

Réponses:

11

MATL , 37 octets

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

Essayez-le en ligne! Ou vérifiez tous les cas de test . Vous voudrez peut-être aussi voir le cinéma se remplir d' art ASCII.

Explication

!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
la source
11

JavaScript (ES6), 156 137 octets

Enregistrement de 18 octets grâce à @ l4m2

C'est beaucoup de 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

Essayez-le en ligne!

Commenté

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
la source
Essayez-le en ligne!
l4m2
b=b<(d=X*X--+Y*Y)|!v?b:d
l4m2
v|b<=B v|est inutile parce que valorsb=0
l4m2
3

Haskell , 216 213 185 184 octets

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

Prend l'entrée sous forme de tableau. L'entrée et la sortie sont dans l'ordre inverse. Crédit pour magie de points fixes à Laikoni .

Essayez-le en ligne!

Angs
la source
1
180 octets avecuntil((==)=<<f)f
ovs le
3

Python 2 , 200 187 octets

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

Essayez-le en ligne!

-13 octets thx à un conseil de Not that Charles en supprimant la vérification inutile pour les cellules étant 0.

Chas Brown
la source
J'ai presque la même solution, mais Python3, une fonction et 194 octets
Pas comme ça Charles
Au lieu d’afficher le mien, les principales économies réalisées sont celles que j’ajoute ,v,uà la fin du générateur à l’intérieur max, et vous n’aurez pas à le faire, if a[v][u]<1car elles seront 0et ne seront donc pas maximales. Donc, ma ligne est fondamentalement*_,y,x=max((min(...),-v,-u,v,u)for v,u in P)
pas que Charles
code étonnamment similaire, cependant. sensationnel.
Pas que Charles
Honnêtement, je ne suis pas sûr que l'ajout des *,v,upersonnages ne soit pas une sauvegarde contre ce que --vous avez. :)
Pas que Charles
@Not that Charles: Nice, totalement raté que le if a[v][u]<1est redondant (puisque les cellules non nulles auront un min()de 0).
Chas Brown
3

APL (Dyalog) , 39 octets

Merci Cocks quack pour la sauvegarde d'un octet, et ngn pour la sauvegarde d'un autre

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

Essayez-le en ligne!

H.PWiz
la source
2

APL (Dyalog Unicode) , 44 octets

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

Essayez-le en ligne!

Solution alternative à 44 octets

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

Clojure, 247 octets

#(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)))

L'entrée est une vec-of-vecs M, qui est modifiée dans un looppar assoc-in. Lorsqu'aucune place disponible n'est trouvée ( if-let), le résultat est renvoyé.

NikoNyrh
la source
1

Jelly , 35 33 30 29 octets

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

Essayez-le en ligne!

Remplacé le ×ı+avec æị(complexe combiner), une nouvelle dyade sur la base j.de J, l' enregistrement d' un octet.

Voici une version plus efficace pour TIO. Essayez-le en ligne!

Explication

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
milles
la source