<< Poprz

Dzięki społeczności PPCG Święty Mikołaj zbalansował swoje wózki do przechowywania. Teraz musi przenieść je do doków transportowych, aby mogły zostać wysłane do ładowni. Niestety ślady do przemieszczania wózków to bałagan, a on musi wymyślić, jak je wszystkie omijać, nie rozbijając się razem!

Wyzwanie

Otrzymasz ścieżki dla każdego z wózków jako listy „etykiet” (lub stacji). Wózki muszą być przemieszczane w taki sposób, aby w żadnym czasie żadne dwa wózki nie znajdowały się na tej samej etykiecie / stacji. Zasadniczo wózki przemieszczają się między pozycjami, z których każda ma unikalną etykietę.

Zadanie

Biorąc pod uwagę ścieżki dla każdego z wózków jako listę list etykiet (które są dodatnimi liczbami całkowitymi), określ, kiedy każdy wózek powinien zostać zwolniony, aby bezpiecznie wysłać wszystkie wózki do ich miejsc docelowych w możliwie najkrótszym czasie.

Oto wyjaśnienie działania całego systemu gąsienic. Powiedzmy, że koszyk iwypuszczany jest t_ina tor z etykietami T_i_1, T_i_2, ..., T_i_n. Następnie, podczas t_1do t_i-1, wózek inie znajduje się na siatce i można go zignorować.

W ramce czasowej t_iwózek jest na etykiecie T_i_1, a dla każdej ramy czasowej t_kod t_ido t_i+n(w połowie włącznie) wózek jest na etykiecie T_i_k+1.

Dla wszystkich przedziałów czasowych po uwzględnieniu t_i+nkoszyk znajduje się w miejscu docelowym i nie znajduje się już na planszy.

Całkowity czas t_Tzajmuje ostatni przedział czasowy, w którym wózek nadal znajduje się na torze w systemie.

Dane techniczne

Biorąc pod uwagę system torów, zwróć listę przedziałów czasowych, w [t_1, t_2, ..., t_n]których iwózek rozpoczyna się w czasie t_i, tak aby żadne inne ustawienie nie pozwoliło wózkom bezpiecznie dotrzeć do miejsca docelowego przy mniejszym całkowitym czasie.

Jeśli chodzi o „bezpiecznie”, jeśli w dowolnym przedziale czasowym od t_1do t_Twięcej niż jednego wózka na dowolnej etykiecie, kolidują ze sobą, a układ nie był „bezpieczny”. Należy zauważyć, że dwa wózki mogą przejść od a, bcelu b, ai wciąż być „bezpieczne”, bo tory są 2-drożny.

Specyfikacja formatowania

Dane wejściowe będą podawane jako macierz dodatnich liczb całkowitych w dowolnym rozsądnym formacie. Dane wyjściowe należy podać jako listę liczb całkowitych dodatnich w dowolnym rozsądnym formacie. Możesz podać dane wyjściowe w przedziałach czasowych indeksowanych od zera, więc wynikiem będzie lista liczb całkowitych nieujemnych w dowolnym rozsądnym formacie.

Zasady

• Obowiązują standardowe luki
• To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach
• Żadna odpowiedź nie zostanie zaakceptowana

Przypadki testowe

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]

^{Uwaga: Inspirację do tej serii wyzwań czerpałem z Advent Of Code . Nie mam powiązań z tą stroną}

Możesz zobaczyć listę wszystkich wyzwań w serii, patrząc na sekcję „Połączone” pierwszego wyzwania tutaj .

Wesołego golfa!

JavaScript (ES7), 172 bajty

Zwraca tablicę przedziałów czasowych o indeksie 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 : Może to działać tylko z etykietami w [0-31]. Jest to limit JS, a nie limit algorytmu.

Przypadki testowe

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]

Skomentował

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