Solution for Codyssi 2024 - Traversing the Country

Link to the puzzle text

Part 1

We are given a file containing a network of cities. The input is in the form of a list of tuples for each connection between two cities. We should find the number of distinct cities in this network.

We store the network in a dictionary containing the connections per city. When we parse each line, we add a connection for both origin and destination city in this dictionary. Once we parse the whole file, the number of distinct cities is the number of elements in this dictionary.

Part 2

In part 2, we should find the number of cities reachable in 3 steps starting with a certain city. 

Instead of restricting us to 3 steps, we calculate the minimal distance to all cities and restrict to 3 steps later on. Since the step costs are always 1 and we are not interested in the exact path, we can use a simple flood fill algorithm with a queue to find the path length. Once we have the path lengths, we filter the cities with a path length of less than 3 and count them.

Part 3

In part 3, we should sum up all the minimal paths from the start city.

We already have the minimal paths lengths for all cities, so we can just sum them all up. 

Link to my solutions