<< Sebelumnya

Berkat komunitas PPCG, Santa sekarang telah menyeimbangkan gerobak penyimpanannya. Sekarang, dia perlu memindahkan mereka ke dermaga transportasi sehingga mereka dapat dikirim ke teluk pemuatan. Sayangnya, trek untuk menggerakkan gerobak berantakan, dan dia perlu mencari cara untuk mendapatkan semuanya tanpa menabrak bersama!

Tantangan

Anda akan diberi trek untuk masing-masing kereta sebagai daftar "label" (atau stasiun). Gerobak harus dipindahkan sedemikian rupa sehingga pada jangka waktu berapa pun, tidak ada dua gerobak yang berada pada label / stasiun yang sama. Pada dasarnya, gerobak bergerak di antara posisi yang masing-masing memiliki label unik.

Tugas

Diberi jejak untuk masing-masing gerobak sebagai daftar daftar label (yang semuanya bilangan bulat positif), tentukan kapan setiap gerobak harus dilepaskan untuk mengirim semua gerobak ke tujuan mereka dengan aman dalam waktu sesingkat mungkin.

Berikut ini penjelasan tentang cara kerja seluruh sistem trek. Katakanlah kereta idilepas tepat waktu t_ike trek dengan label T_i_1, T_i_2, ..., T_i_n. Kemudian, selama t_1ke t_i-1, gerobak itidak di grid dan dapat diabaikan.

Pada kerangka waktu t_i, gerobak ada pada label T_i_1, dan untuk setiap kerangka waktu t_kdari t_ihingga t_i+n(setengah inklusif), gerobak ada pada label T_i_k+1.

Untuk semua kerangka waktu setelah dan termasuk t_i+n, keranjang berada di tujuannya dan tidak lagi berada di grid.

Jumlah waktu total t_T diambil adalah kerangka waktu terakhir dengan kereta masih di jalur dalam sistem.

Spesifikasi

Dengan sistem lacak, kembalikan daftar kerangka waktu [t_1, t_2, ..., t_n]tempat ikereta mulai saat itu t_i, sehingga tidak ada pengaturan lain yang memungkinkan kereta dengan aman mencapai tujuan mereka dengan jumlah waktu yang lebih sedikit.

Dalam hal "aman", jika sewaktu-waktu kerangka dari t_1ke t_Tsana ada lebih dari satu kereta pada label apa pun, maka mereka bertabrakan dan pengaturannya tidak "aman". Perhatikan bahwa dua kereta dapat bergerak dari a, bke b, adan masih "aman" karena jalurnya 2 arah.

Spesifikasi Format

Input akan diberikan sebagai matriks bilangan bulat positif dalam format apa pun yang masuk akal. Keluaran harus diberikan sebagai daftar bilangan bulat positif dalam format apa pun yang masuk akal. Anda dapat memberikan output dalam kerangka waktu tanpa indeks, sehingga outputnya adalah daftar bilangan bulat non-negatif dalam format apa pun yang masuk akal.

Aturan

• Celah Standar Berlaku
• Ini adalah kode-golf sehingga jawaban tersingkat dalam byte menang
• Tidak ada jawaban yang akan diterima

Uji Kasus

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]

^{Catatan: Saya mendapat inspirasi untuk seri tantangan ini dari Advent Of Code . Saya tidak memiliki afiliasi dengan situs ini}

Anda dapat melihat daftar semua tantangan dalam seri ini dengan melihat bagian 'Tertaut' dari tantangan pertama di sini .

Selamat Golf!

JavaScript (ES7), 172 byte

Mengembalikan array kerangka waktu 0-diindeks.

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 : Ini hanya dapat bekerja dengan label pada [0-31]. Ini adalah batas JS, bukan batas algoritma.

Uji kasus

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]

Berkomentar

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