<< Пред.

Благодаря сообществу PPCG Санта теперь сбалансировал свои тележки для хранения. Теперь ему нужно переместить их в транспортные доки, чтобы их можно было отправлять на погрузочные площадки. К сожалению, дорожки для перемещения тележек - беспорядок, и он должен выяснить, как обойти их без крушения вместе!

Вызов

Вам дадут дорожки для каждой из тележек в виде списков «меток» (или станций). Тележки должны быть перемещены так, чтобы в любой момент времени на одной этикетке / станции не было двух тележек. По сути, тележки перемещаются между позициями, каждая из которых имеет уникальный ярлык.

задача

С учетом дорожек для каждой тележки в виде списка списков меток (все они являются положительными целыми числами), определите, когда каждая корзина должна быть выпущена, чтобы безопасно отправлять все тележки в места назначения в кратчайшие сроки.

Вот объяснение того, как работает вся система треков. Допустим, корзина iвыпущена вовремя t_iна дорожку с ярлыками T_i_1, T_i_2, ..., T_i_n. Затем, во время t_1To t_i-1, телега iне на сетке и может быть проигнорирована.

В определенные периоды времени t_iкорзина находится на этикетке T_i_1, а для каждого периода времени t_kот ( t_iдо t_i+nполовины включительно) корзина находится на этикетке T_i_k+1.

Для всех периодов времени после и после t_i+n, корзина находится в пункте назначения и больше не находится в сетке.

Общее количество времени, которое t_Tпотребовалось, является последним периодом времени, когда корзина все еще находится на дорожке в системе.

Характеристики

При наличии системы отслеживания верните список временных интервалов, в которые [t_1, t_2, ..., t_n]эта iкорзина начинается в определенное время t_i, так что никакое другое устройство не позволило бы тележкам безопасно добраться до пунктов назначения с меньшим общим количеством времени.

С точки зрения «безопасно», если в любой момент времени кадр из t_1к t_Tесть более чем одна тележка на любой ярлык, то они сталкиваются и расположение не было «безопасным». Обратите внимание , что две тележки могут перейти от a, bк b, aи все еще быть «безопасным» , потому что дорожки 2-полосная.

Спецификации форматирования

Ввод будет дан как матрица положительных целых чисел в любом разумном формате. Выходные данные должны быть представлены в виде списка натуральных чисел в любом приемлемом формате. Вы можете выдавать выходные данные с нулевыми индексами, поэтому выходные данные будут представлять собой список неотрицательных целых чисел в любом приемлемом формате.

правила

• Применяются стандартные лазейки
• Это код-гольф, поэтому выигрывает самый короткий ответ в байтах
• Ответ не будет принят

Тестовые случаи

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]

^{Примечание: я черпал вдохновение для этой серии испытаний из Advent Of Code . У меня нет связи с этим сайтом}

Вы можете увидеть список всех испытаний в серии, посмотрев раздел «Связанные» первого испытания здесь .

Счастливого гольфа!

JavaScript (ES7), 172 байта

Возвращает массив 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 : Это может работать только с метками в [0-31]. Это предел JS, а не предел алгоритма.

Контрольные примеры

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]

комментарии

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