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\$
4
  • 9
    \$\begingroup\$ This looks really interesting, but some worked examples and some test cases would help. \$\endgroup\$
    – Adám
    Aug 2, 2022 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, 2022 at 15:32
  • \$\begingroup\$ Are floating point inaccuracies allowed? (a mathematically correct solution, which might fail in practice for big values due to floating-point inaccuracies) \$\endgroup\$ Aug 17, 2022 at 8:24
  • \$\begingroup\$ @CommandMaster Yes, that should be fine. It's similar to integer overflow. \$\endgroup\$ Aug 17, 2022 at 21:39

4 Answers 4

3
\$\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\$
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, 2022 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, 2022 at 13:12
  • \$\begingroup\$ Ah ok, that makes sense. \$\endgroup\$ Aug 9, 2022 at 13:37
3
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ [1,0][D>c] => (D<c) \$\endgroup\$
    – naffetS
    Aug 9, 2022 at 4:04
  • \$\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, 2022 at 14:09
  • \$\begingroup\$ Errors for [[1, 0, -3, 4, 5], [0, 1, -1, 7, 9]] (expected 15) \$\endgroup\$
    – Jitse
    Aug 16, 2022 at 13:31
  • \$\begingroup\$ @Jitse The OP makes no mention of cycles. \$\endgroup\$
    – Ajax1234
    Aug 16, 2022 at 14:45
2
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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