7
\$\begingroup\$

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.

\$\endgroup\$
2
  • 9
    \$\begingroup\$ This looks really interesting, but some worked examples and some test cases would help. \$\endgroup\$
    – Adám
    Aug 2 at 9:31
  • 4
    \$\begingroup\$ Maybe you should clarify whether the routes can include cycles (at least one train going from A to B and another train going from B to A). Apart from that, the task seems pretty clear to me. But test cases would be greatly appreciated. \$\endgroup\$
    – Arnauld
    Aug 2 at 15:32

4 Answers 4

3
\$\begingroup\$

Python3, 99 bytes:

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

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ [1,0][D>c] => (D<c) \$\endgroup\$
    – Steffan
    Aug 9 at 4:04
  • \$\begingroup\$ This also seems to result 8 with [[0, 1, -1, 7, 9]] as input (expected 15). \$\endgroup\$
    – Jitse
    Aug 9 at 12:50
  • \$\begingroup\$ [[0, 2, 0, 5, 3], [2, 1, 4, 10, 4]] results in 11 instead of 8 (expected route: 0->2 in 3 minutes; wait 1 minute; 2->1 in 4 minutes). \$\endgroup\$ Aug 9 at 14:09
3
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Out of curiosity: even if the graph can be cyclic, in what scenario would it ever be shorter to cycle over non-cycle? If there is a cycle, you can just wait at that station, preventing the cycle. Or am I missing something? (e.g. if cycle 0 -> 2 -> 3 -> 0 -> 2 -> 3 -> 1 is shorter than 0 -> 1, that first one can also just be 0 -> 2 -> 3 -> wait -> 1) \$\endgroup\$ Aug 9 at 12:26
  • 1
    \$\begingroup\$ @KevinCruijssen Cycles are never worth considering for the best path. But if there are cycles, we need some extra code to prevent infinite recursion. (There may be a shorter way than my current solution, though.) \$\endgroup\$
    – Arnauld
    Aug 9 at 13:12
  • \$\begingroup\$ Ah ok, that makes sense. \$\endgroup\$ Aug 9 at 13:37
2
\$\begingroup\$

Python 3, 123 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)or[sum(map(abs,sum(a,())))]for x,y,s,i,d in a if x==n)

Try it online!

Compatibility with dead ends and cyclic routes made it significantly longer.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.