Train Route Planning

Question

We can model a rail network as a directed graph, where each node is a train station and each edge is a train connecting two train stations. We'll assume that each train travels between its corresponding stations at a regular schedule and takes a fixed amount of time

Your code should take a list of trains, where each train is a tuple (from, to, base, interval, duration), where

1. from is an integer denoting the station the train departs from.
2. to is an integer denoting the station the train arrives at.
3. base is the integer timestamp of an arbitrary departure of the given train.
4. interval is a positive integer denoting how often the train departs.
5. duration a positive integer denoting how long the train takes.

In other words, the departures are given by base + n * interval, and the corresponding arrivals by base + n * interval + duration, for integer n. For example, 0 2 -3 4 5 would describe a train going from station 0 to station 2, which is at station 0 at times ..., -11, -7, -3, 1, 5, 9, 13, ... and is at station 2 at times ..., -6, -2, 2, 6, 10, 14, 18, ....

If you are at some station x want to take a train from x to y, you must wait until the train from x to y is at station x. Then, after another duration units of time, you are at station y. For example, if at time 0 you're at station 0 and want to use the train described above, you'd need to wait until time 1, then at time 6 you would be at station 2.

Given these trains, your code should calculate the earliest arrival time at station 1, given that you start at station 0 at time 0. If no route is possible, you should return a distinguished value.

Worked Example

Suppose we are given input:

0 2 -3 4 5
2 1 9 3 2
0 1 -1 7 9

From this, we can see the pairs of arrival and departure times of each train are:

..., (1, 6), (5, 10), (9, 14), (13, 18), (17, 22), (21, 26), (25, 30), ... 
..., (0, 2), (3, 5), (6, 8), (9, 11), (12, 14), (15, 17), (18, 20), ...
..., (6, 15), (13, 22), (20, 29), (27, 36), (34, 43), (41, 50), (48, 57), ...

There are 2 routes from stations 0 to 1: 0 -> 1 and 0 -> 2 -> 1.

• For the route 0 -> 1, we can board the train at time 6 and get off at time 15.
• For the route 0 -> 2 -> 1, we can get on train 0 -> 2 at time 1, arrive at station 2 at time 6, then immediately board train 2 -> 1, arriving at station 1 at time 8.

Out of these, 0 -> 2 -> 1 is the fastest, so we output 8.

Answer 1

05AB1E, 44 bytes

æʒø2£ø˜Á2ôćRJs€ËP*}ε0svy¦¦`U©%∞<®*+Dr@ÏнX+]ß

Outputs an empty string if no valid route can be found.

What a mess.. Those arbitrary base-times are pretty annoying to deal with.
Ah well, it works.. Will try to golf it some more later on.

Try it online or verify all test cases.

Explanation:

Step 1: Get all valid routes:

æ                # Get the powerset of the (implicit) input-list of quintuplets
 ʒ               # Filter it by:
  ø              #  Zip/transpose; swapping rows/columns
   2£            #  Keep the first two inner lists
     ø           #  Zip/transpose back
                 #  (we now have a list of all [from,to]-pairs for the current potential
                 #  route)
      ˜          #  Flatten it
       Á         #  Rotate it once towards the left
        2ô       #  Split it back into pairs
  ć              #  Extract the head
   R             #  Reverse it
    J            #  Join it together to a string
                 #  (note: only 1 is truthy in 05AB1E, including "01")
  s              #  Swap so the remainder-list is at the top
   €Ë            #  Check for each pair whether they're equal
     P           #  Check if this is truthy for all of them
  *              #  Check if both are truthy
 }               # Close the filter

Try just the first step online.

Step 2: Calculate the time each route takes, and leave the smallest as result:

ε                # Map over each valid route:
 0               #  Start at time 0 (let's call this the `current_time`)
  s              #  Swap so the route-list is at the top of the stack
   vy            #  For-each over its quintuplets:
     ¦¦          #   Remove the `from` and `to` from the quintuplet
     `           #   Pop and push the remaining three values to the stack
      U          #   Pop the top one (`duration`), and store it in variable `X`
      ©          #   Store the next top (`interval`) in variable `®` (without popping)
       %         #   Pop both values, and calculate base modulo interval
     ∞<          #   Push an infinite non-negative list: [0,1,2,...]
       ®*        #   Multiply each by interval `®`: [0,interval,2*interval,...]
         +       #   Add the (base modulo interval) to each
          D      #   Duplicate the infinite list
           r     #   Reverse the values on the stack
            @    #   Check for each value in the infinite list if it's >= `current_time`
             Ï   #   Only keep the values in the infinite list at the truthy indices
              н  #   Pop and push the first/lowest
     X+          #   Add duration `X` to it,
                 #   which is the next iteration's `current_time`
]                # Close both the loop and map
 ß               # Pop and push the minimum
                 # (which is output implicitly as result)

Answer 2

JavaScript (ES6), 102 bytes

Expects an array of tuples [ from, to, base, interval, duration ]. Returns \$+\infty\$ if there's no solution.

f=(a,p,t=0,m)=>p^1?Math.min(...a.map(([A,B,b,i,d])=>p^A|m>>B&1?1/0:f(a,B,t+((b-t)%i+i)%i+d,m|1<<B))):t

Try it online!

Or 86 bytes if the graph is guaranteed to be acyclic.

Commented

f = (                       // f is a recursive function taking:
  a,                        //   a[] = list of routes
  p,                        //   p = current position
  t = 0,                    //   t = current time
  m                         //   m = mask of visited stations
) =>                        //
p ^ 1 ?                     // if the current position is not 1:
  Math.min(...              //   take the minimum of ...
    a.map(                  //     for each route in a[] going from
    ([A, B, b, i, d]) =>    //     A to B with parameters (b, i, d):
      p ^ A |               //       if the current position is not A
      m >> B & 1 ?          //       or B was already visited:
        1 / 0               //         return +Infinity
      :                     //       else:
        f(                  //         do a recursive call:
          a,                //           pass a[] unchanged
          B,                //           set p = B
          t +               //           compute the updated time
          ((b - t) % i + i) //           by adding the delay before
          % i               //           departure
          + d,              //           and the duration
          m | 1 << B        //           mark B as visited
        )                   //         end of recursive call
    )                       //     end of map()
  )                         //   end of Math.min()
:                           // else:
  t                         //   destination reached: return t

Answer 3

Python3, 111 bytes:

f=lambda t,s=0,D=0:min(m)if(m:=[D]*(s==1)+[K for a,b,c,d,e in t if a==s and(K:=f(t,b,max(c%d-D,0)+D+e))])else[]

Try it online!

Answer 4

Python 3, 119 bytes

f=lambda a,n=0,t=0:t*(n==1)or min([f(a-{(x,y,s,i,d)},y,s-(s-t)//i*i+d)for x,y,s,i,d in a if x==n]or[max(sum(a,()))**2])

Try it online!