<< Préc

Grâce à la communauté PPCG, le Père Noël a maintenant équilibré ses chariots de stockage. Maintenant, il doit les déplacer dans les quais de transport afin qu'ils puissent être envoyés aux quais de chargement. Malheureusement, les pistes pour déplacer les chariots sont un gâchis, et il doit trouver comment les faire circuler sans les écraser ensemble!

Défi

Vous recevrez les pistes pour chacun des chariots sous forme de listes de "labels" (ou stations). Les chariots doivent être déplacés de telle sorte qu'à tout moment, deux chariots ne soient pas sur la même étiquette / station. Essentiellement, les chariots se déplacent entre des positions qui ont chacune une étiquette unique.

Tâche

Étant donné les pistes pour chacun des chariots sous forme de liste de listes d'étiquettes (qui sont toutes des entiers positifs), déterminez quand chaque chariot doit être libéré afin d'envoyer tous les chariots vers leurs destinations en toute sécurité dans les plus brefs délais.

Voici une explication du fonctionnement de l'ensemble du système de chenilles. Disons que le panier iest libéré à temps t_isur une piste avec des étiquettes T_i_1, T_i_2, ..., T_i_n. Ensuite, pendant t_1le t_i-1, le chariot in'est pas sur la grille et peut être ignoré.

À la période t_i, le chariot est sur l'étiquette T_i_1et pour chaque période t_kde t_ià t_i+n(demi-inclus), le panier est sur l'étiquette T_i_k+1.

Pour tous les délais après et y compris t_i+n, le chariot est à sa destination et n'est plus sur la grille.

Le temps total t_Tpris est le dernier laps de temps avec un chariot toujours sur une piste dans le système.

Caractéristiques

Étant donné un système de suivi, renvoyez une liste de délais [t_1, t_2, ..., t_n]où le ichariot commence à l'heure t_i, de sorte qu'aucun autre arrangement ne permettrait aux chariots de se rendre en toute sécurité à leurs destinations avec un temps total moindre.

En termes de "sécurité", si à tout moment de t_1à t_Til y a plus d'un chariot sur une étiquette, ils entrent en collision et l'arrangement n'est pas "sûr". Notez que deux chariots peuvent se déplacer d' a, bà b, aet être encore « sûr » parce que les pistes sont à 2 voies.

Spécifications de formatage

L'entrée sera donnée sous la forme d'une matrice d'entiers positifs dans n'importe quel format raisonnable. La sortie doit être donnée sous la forme d'une liste d'entiers positifs dans n'importe quel format raisonnable. Vous pouvez donner une sortie dans des intervalles de temps indexés zéro, donc la sortie serait une liste d'entiers non négatifs dans n'importe quel format raisonnable.

Règles

• Les échappatoires standard s'appliquent
• Ceci est un code-golf donc la réponse la plus courte en octets gagne
• Aucune réponse ne sera acceptée

Cas de test

Input -> Output
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> [1, 1, 1]
[[1, 2, 3], [1, 2, 3]] -> [1, 2]
[[1, 2, 3], [3, 2, 1]] -> [1, 2]
[[1, 2, 3, 4], [4, 3, 2, 1]] -> [1, 1]
[[1, 1, 1], [1, 1, 1]] -> [1, 4]
[[1, 2, 3, 4], [2, 4, 3, 1]] -> [2, 1]
[[1, 2, 3, 4, 5, 6, 7], [2, 3, 3, 4], [5, 4, 3]] -> [1, 3, 4]
[[1, 2, 3, 4, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5]] -> [2, 3, 1]

^{Remarque: je me suis inspiré de cette série de défis d' Advent Of Code . Je n'ai aucune affiliation avec ce site}

Vous pouvez voir une liste de tous les défis de la série en consultant la section 'Linked' du premier défi ici .

Bon golf!

JavaScript (ES7), 172 octets

Renvoie un tableau de périodes de temps indexées sur 0.

a=>(g=k=>a.map((a,i)=>[l=a.length+1,i,a,L=L<l?l:L]).sort(([a],[b])=>a-b).every(([,n,b],i)=>b.every((c,t)=>o[t+=A[n]=k/L**i%L|0]&1<<c?0:o[t]|=1<<c),o=[],A=[])?A:g(k+1))(L=0)

NB : Cela ne peut fonctionner qu'avec des étiquettes en [0-31]. Il s'agit d'une limite JS, pas d'une limite de l'algorithme.

Cas de test

let f =

a=>(g=k=>a.map((a,i)=>[l=a.length+1,i,a,L=L<l?l:L]).sort(([a],[b])=>a-b).every(([,n,b],i)=>b.every((c,t)=>o[t+=A[n]=k/L**i%L|0]&1<<c?0:o[t]|=1<<c),o=[],A=[])?A:g(k+1))(L=0)

console.log(JSON.stringify(f([[1, 2, 3], [4, 5, 6], [7, 8, 9]])))                   // -> [0, 0, 0]
console.log(JSON.stringify(f([[1, 2, 3], [1, 2, 3]])))                              // -> [0, 1] or [1, 0]
console.log(JSON.stringify(f([[1, 2, 3], [3, 2, 1]])))                              // -> [0, 1] or [1, 0]
console.log(JSON.stringify(f([[1, 2, 3, 4], [4, 3, 2, 1]])))                        // -> [0, 0]
console.log(JSON.stringify(f([[1, 1, 1], [1, 1, 1]])))                              // -> [0, 3] or [3, 0]
console.log(JSON.stringify(f([[1, 2, 3, 4], [2, 4, 3, 1]])))                        // -> [1, 0]
console.log(JSON.stringify(f([[1, 2, 3, 4, 5, 6, 7], [2, 3, 3, 4], [5, 4, 3]])))    // -> [0, 2, 3]
console.log(JSON.stringify(f([[1, 2, 3, 4, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5]]))) // -> [1, 2, 0]

Commenté

a => (                         // given a = array of tracks
  g = k =>                     // g = recursive function taking k = counter
    a.map((t, i) => [          // map each track t in a to a new entry made of:
      l = t.length + 1,        //   - its length + 1 (l)
      i,                       //   - its original index in the input array
      t,                       //   - the original track data
      L = L < l ? l : L        //   and update the maximum track length L
    ])                         // end of map()
    .sort(([a], [b]) =>        // let's sort the tracks from shortest to longest
      a - b                    // so that solutions that attempt to delay short
    )                          // tracks are tried first
    .every(([, n, b],          // for each track b with an original position n,
                      i) =>    // now appearing at position i:
      b.every((c, t) =>        //   for each label c at position t in b:
        o[t += A[n] =          //     add to t the time frame A[n] corresponding
          k / L**i % L | 0     //     to this position (i) and this combination (k)
        ] & 1 << c ?           //     if the station c is already occupied at time t:
          0                    //       make every() fail
        :                      //     else:
          o[t] |= 1 << c       //       mark the station c as occupied at time t
      ),                       //   end of inner every()
      o = [],                  //   start with: o = empty array (station bitmasks)
      A = []                   //               A = empty array (time frames)
    ) ?                        // end of outer every(); if successful:
      A                        //   return A
    :                          // else:
      g(k + 1)                 //   try the next combination
)(L = 0)                       // initial call to g() + initialization of L