Solution for Advent of Code 2018 - Day 24: Immune System Simulator 20XX

Link to the puzzle text

Part 1

In this puzzle we have descriptions of two different armies for an immune system and an infection. Each army consists of multiple groups of units. Each unit has a number of units, an attack value, hit points, inititiave, attack type, weaknesses and immunities. Each round the units attack each other in an order based on their inititiave. During an attack, each unit selects an individual target of the opposing side with the largest potential damage. Each unit can only be chosen once as a target. Whenever a unit is hit by an attack it has a weakness to, it gets double damage. When hit by an attack which it is immune to, it gets no damage. After target select each group deals damage and only whole units of the groups are removed based on the damage received. We should simulate a fight until there is only one side left and count how many units the winning side has left.

The implementation of this was straight forward. We used a class for the units to keep data of a group close together. For the target selection we keep a dictionary of which group already targeted which other group. For ranking the targets of a new group, we only look at the groups not already targeted. The weaknesses, immunities and attack types are saved as list of strings and we just check if the attack type is in the list of weaknesses / immunities. Finally we check after each round if just one side is left and count the remaining units if so.

Part 2

In part 2, we introduce a boost the immune system. The boost increases the attack values of all units of the immune system side for the complete duration of the fight. We should find the lowest boost which results in the immune system winning and count the remaining units left after its win.

We reused the code for part 1 and also returned the winning side after the simulation. We start increasing the boost starting with 1 and simulate a new fight. As soon as the immune system side wins, we can count the remaining units for the answer.

Link to my solutions

Solution for Codyssi 2025 - Games in a Storm

Link to the puzzle text

Part 1

In this puzzle, we have a list of tuple of a string and a tuple. The string encodes an arbitrary base number with the exact base set by the second part of the tuple. The letters used for the digits above 9 are the lowercase letters followed by the uppercase letters. We should write every number in base 10 and find the largest number out of the list.

We need a function for parsing a string using an arbitrary base. This is simply:

total = 0
for c in s:
    total *= base
    total += char_value(c, total)

With the function char_value transforming a single character into a number.

def char_value(c):
    if "0" <= c <= "9":
        return int(c)
    elif "A" <= c <= "Z":
        return ord(c) - ord("A") + 10
    return ord(c) - ord("a") + 36

Once we call the function for parsing the string on all input lines, we can take the largest value out of them for the answer.

Part 2

In part 2, we should sum up all the parsed numbers and write the result back as a base-68 string. In base 68, the digits above 9 are the lowercase letters, then the uppercase letters followed by the characters !@#$%

Taking a number and writing it in base-68, this is basically the inverse of the previous function:

def num_to_string(num):
    s = ""
    digitschars = digits + ascii_uppercase + ascii_lowercase + "!@#$%^"
    while num > 0:
        last_digit = num % 68
        s = digitschars[last_digit] + s 
        num //= 68
    return s

This function is called with the sum of the parsed numbers from part 1 for the answer.

Part 3

In part 3, we should find the smallest base which can still represent the sum of all parsed numbers.

This can be done analitically. The largest number M with 4 characters in base N is M=N^4 -1. We can rewrite this so the base for a given number M must be N=M^(1/4) + 1. So we simply take the fourth-root of the sum, round it up and add one for the answer.

Link to my sol    utions

Solution for Advent of Code 2018 - Day 23: Experimental Emergency Teleportation

Link to the puzzle text

Part 1

In this puzzle, we have a series of 3D-coordinates and ranges. These describe each a nanobot at a certain coordinate and their signal range. We should find the nanobot with the largest signal range and count how many other nanobots are in their signal range. The distance between two nanobots is using the Manhattan distance, so the distance between points p and q is abs(p.x - q.x) + abs(p.y - q.y) + abs(p.z - p.z).

After reading in the input, we search for the nanobot with the largest radius. After getting its radius, we filtered the total list by their distance to this nanobot with the largest signal range. The length of this list was the answer.

Part 2

In part 2, we should find the coordinate which is in range of the most nanobots.

Finding how many nanobots are in range to a specific coordinate is straight forward and done similar to part 1. For finding the coordinate in a 3D-range with the most nanobots in range, we could use three simple loops and take the largest number until now. 
But searching the complete range is unfeasable due to how large the search space ist, so we had to reduce it first. We used a coarse search dividing the complete range into finer and finer grids until a complete search was feasable. Each coordinate (x,y,z) started with a range of the smallest coordinate minus radius to largest coordinate plus radius. At each step the range was divided into 2 halves. Going over each nanobot, we count if a nanobots signal reaches into any of the 8 subranges. We then halve the range of one of the coordinates to the half with more nanobot signals.
Once each coordinate range is at most 16 elements large, we could start the complete search for the coordinate with the most signals in range as the answer.

Link to my solutions