Advent Challenge 8: Storage Cart Transport Planning!

Question

<< Prev

Thanks to the PPCG community, Santa now has balanced his storage carts. Now, he needs to move them into the transport docks so that they can be sent to the loading bays. Unfortunately, the tracks to move the carts around are a mess, and he needs to figure out how to get them all around without them crashing together!

Challenge

You will be given the tracks for each of the carts as lists of "labels" (or stations). The carts must be moved such that at any time frame, no two carts are on the same label/station. Essentially, the carts move between positions that each have a unique label.

Task

Given the tracks for each of the carts as a list of lists of labels (which are all positive integers), determine when each cart should be released in order to send all the carts to their destinations safely in the shortest time possible.

Here's an explanation of how the entire track system works. Let's say cart i is released at time t_i onto a track with labels T_i_1, T_i_2, ..., T_i_n. Then, during t_1 to t_i-1, cart i is not on the grid and can be ignored.

At time frame t_i, the cart is on label T_i_1, and for each time frame t_k from t_i to t_i+n (half-inclusive), the cart is on label T_i_k+1.

For all time frames after and including t_i+n, the cart is at its destination and is no longer on the grid.

The total amount of time t_T taken is the last time frame with a cart still on a track in the system.

Specifications

Given a track system, return a list of time frames [t_1, t_2, ..., t_n] where the ith cart starts at time t_i, such that no other arrangement would allow the carts to safely get to their destinations with a lesser total amount of time.

In terms of "safely", if at any time frame from t_1 to t_T there is more than one cart on any label, then they collide and the arrangement was not "safe". Note that two carts can move from a, b to b, a and still be "safe" because the tracks are 2-way.

Formatting Specifications

Input will be given as a matrix of positive integers in any reasonable format. Output should be given as a list of positive integers in any reasonable format. You may give output in zero-indexed time frames, so then the output would be a list of non-negative integers in any reasonable format.

Rules

• Standard Loopholes Apply
• This is a code-golf so the shortest answer in bytes wins
• No answer will be accepted

Test Cases

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]

^{Note: I drew inspiration for this challenge series from Advent Of Code. I have no affiliation with this site}

You can see a list of all challenges in the series by looking at the 'Linked' section of the first challenge here.

Happy Golfing!

Answer 1

JavaScript (ES7), 172 bytes

Returns an array of 0-indexed time frames.

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: This can only work with labels in [0-31]. This is a JS limit, not a limit of the algorithm.

Test cases

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]

Commented

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