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!
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.
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
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_i+n (half-inclusive), the cart is on label
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.
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_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.
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.
- Standard Loopholes Apply
- This is a code-golf so the shortest answer in bytes wins
- No answer will be accepted
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.