codingquest

The route home

The ship has left the docks of Tycho station. Next stop: Earth. Home.

To ensure safe travel through the star systems, a series of beacons have been placed along key routes. Each beacon maintains a list of the other nearby beacons and their respective travel time.

Additionally, every time you pass a beacon, the ship must stop for 10 minutes (600 seconds) to reset systems with updated directions to the next beacon. This time must be added to your total journey calculations (the more beacons you pass, the more stops, the longer the trip will take).

Departing TYC, plot a course via the various beacons to reach home, EAR.

What is the shortest travel time (in seconds) via the beacons to get from TYC to EAR?

Example

Consider the following example data describing travel options and their respective times from each beacon.

AAA => BBB:38 CCC:45
BBB => AAA:38 DDD:60 ZZZ:70
CCC => AAA:45 DDD:35
DDD => BBB:60 CCC:35 ZZZ:15
ZZZ => BBB:70 DDD:15

This data indicates that from point AAA, it is possible to travel to BBB at a time of 38 seconds, or to CCC at a time of 45 seconds.

To travel from AAA to ZZZ using a per-beacon stop time of 10 seconds, the following routes are available

  • AAA->BBB->ZZZ has a travel time of 118 seconds comprising:

    • AAA->BBB 38 seconds
    • Stopping time 10 seconds
    • BBB->ZZZ 70 seconds

  • AAA->BBB->DDD->ZZZ has a travel time of 133 seconds comprising:

    • AAA->BBB 38 seconds
    • Stopping time 10 seconds
    • BBB->DDD 60 seconds
    • Stopping time 10 seconds
    • DDD->ZZZ 15 seconds

  • AAA->CCC->DDD->BBB->ZZZ has a travel time of 240 seconds comprising:

    • AAA->CCC 45 seconds
    • Stopping time 10 seconds
    • CCC->DDD 35 seconds
    • Stopping time 10 seconds
    • DDD->BBB 60 seconds
    • Stopping time 10 seconds
    • BBB->ZZZ 70 seconds

  • AAA->CCC->DDD->ZZZ has a travel time of 115 seconds comprising:

    • AAA->CCC 45 seconds
    • Stopping time 10 seconds
    • CCC->DDD 35 seconds
    • Stopping time 10 seconds
    • DDD->ZZZ 15 seconds

Therefore, the shortest travel time available in this example is 115 seconds. Notice that it is not necessarily the one with the least stops.

PS... be careful not to get caught in an infinite loop such as AAA->BBB->DDD->CCC->AAA->...

Your task

Process your input data and calculate the shortest time to travel from TYC to EAR (with a stopping time of 600 seconds per stop).

Closing remarks: An event like this would not be possible without the generous support of others. For Coding Quest 2023, I would like to thank those who beta-tested the problems and gave valuable feedback that helped improve them: Colin McAlpine, Matt Bolt, Patrick Kennedy, and Andrew Carle. The amazing promotional poster was designed by Clarice. Finally, a thank you to you, to the students who participate! I hope you found the experience enjoyable and valuable for your Computer Science learning.

See you in March 2024! (add a reminder to Google calendar)

Bye for now! Paul Baumgarten.

Input data

Get your puzzle input data

What is the solution?

 

Hint

A commonly used method for solving shortest path problems is Dijkstra's algorithm. This is a good explanation and example walk through on Youtube How Dijkstra's Algorithm Works.