<< Anterior

Gracias a la comunidad PPCG, Santa ahora ha equilibrado sus carros de almacenamiento. Ahora, necesita moverlos a los muelles de transporte para que puedan enviarse a las bahías de carga. Desafortunadamente, las pistas para mover los carros son un desastre, ¡y él necesita descubrir cómo moverlas sin que se estrellen juntas!

Desafío

Se le darán las pistas para cada uno de los carros como listas de "etiquetas" (o estaciones). Los carros deben moverse de manera tal que en cualquier momento, no haya dos carros en la misma etiqueta / estación. Esencialmente, los carros se mueven entre posiciones que tienen una etiqueta única.

Tarea

Dadas las pistas para cada uno de los carros como una lista de listas de etiquetas (que son todos enteros positivos), determine cuándo se debe liberar cada carro para enviar todos los carros a sus destinos de manera segura en el menor tiempo posible.

Aquí hay una explicación de cómo funciona todo el sistema de seguimiento. Digamos que el carro ise lanza en el momento t_ien una pista con etiquetas T_i_1, T_i_2, ..., T_i_n. Luego, durante t_1a t_i-1, el carrito ino está en la cuadrícula y puede ignorarse.

En la trama de tiempo t_i, el carro está en la etiqueta T_i_1, y para cada marco de tiempo t_kde t_ia t_i+n(medio-inclusive), el carro está en la etiqueta T_i_k+1.

Para todos los plazos posteriores e inclusive t_i+n, el carrito está en su destino y ya no está en la cuadrícula.

La cantidad total de tiempo que se t_Ttarda es el último período de tiempo con un carro todavía en una pista en el sistema.

Especificaciones

Dado un sistema de seguimiento, devuelva una lista de plazos [t_1, t_2, ..., t_n]en los que el icarro se inicia en el momento t_i, de modo que ninguna otra disposición permita que los carros lleguen a sus destinos de manera segura con una cantidad de tiempo total menor.

En términos de "seguridad", si en cualquier marco de tiempo desde t_1que t_Texiste más de una compra en cualquier etiqueta, entonces chocan y la disposición no era "seguro". Tenga en cuenta que dos carros pueden moverse de un lugar a, ba otro b, ay seguir siendo "seguros" porque las vías son bidireccionales.

Especificaciones de formato

La entrada se dará como una matriz de enteros positivos en cualquier formato razonable. La salida debe darse como una lista de enteros positivos en cualquier formato razonable. Puede dar salida en marcos de tiempo indexados a cero, por lo que la salida sería una lista de enteros no negativos en cualquier formato razonable.

Reglas

• Se aplican lagunas estándar
• Este es un código de golf, por lo que gana la respuesta más corta en bytes
• No se aceptarán respuestas.

Casos de prueba

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]

^{Nota: Me inspiré para esta serie de desafíos de Advent Of Code . No estoy afiliado a este sitio}

Puede ver una lista de todos los desafíos de la serie mirando la sección 'Vinculados' del primer desafío aquí .

¡Feliz golf!

JavaScript (ES7), 172 bytes

Devuelve una matriz de marcos de tiempo indexados a 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 : Esto solo puede funcionar con etiquetas en [0-31]. Este es un límite JS, no un límite del algoritmo.

Casos de prueba

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]

Comentado

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