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

Solution for Codyssi 2024 - Unformatted Readings

Link to the puzzle text

Part 1

We are given a file with several lines of input. Each line consists of a number in a certain base and the base. We should extract only the bases and return the sum. 

We start by parsing the input file into a list of tuples. For the first part, we sum over the bases and are done. 

Part 2

In part 2, we should use the bases to convert each number into base 10 and sum the result.

We use the int function of python to convert strings into numbers. The second, optional argument of int can specify a base, so we supply the base. Summing up the results gets us the answer. 

Part 3

In part 3, we should convert the previous sum into a base 65 string. In base 65, the first 10 digits are normal, followed by upper case and lower case letters. The last 3 digits are special chars !, # and @.

The easiest way to convert into a base is by building the string in reverse. We start by calculating the number modulo 65 and convert the result into a digit. We then divide the number by 65 and repeat to get the rest of the base-65 string. While building the string, we just have to remember to append the current digit to the left.

Link to my solutions

Solution for Codyssi 2024 - Sensors and Circuits

Link to the puzzle text

Part 1

We are given a file with 512 boolean values in a file. Each value corresponds to one sensor with an id equal to the line in the file. We should find the sum of all sensor outputting true.

We used a list expression to get all sensor ids with true values and used sum to get the sum.

Part 2

In part 2, we should simulate a simple circuit. The sensors are grouped into pairs and alternative used as input for an AND and an OR gate. So sensors 1 and 2 are input for an AND, sensor 3 and 4 for an OR gate and so on. We should find the number of gates outputting true.

We wrote a function to simulate this circuit. The inputs are paired and depending on the gate index we use a different gate function. Finally the all gate outputs are returned and we count the number of true values.

Part 3

In part 3, we should repeat the previous circuit until only one value remains. During this computation, we should count the number of gates outputting true.

We reused the previously written function and always summed the number of true gates while there is still enough input left. The total sum was return as the final answer.

Link to my solutions