Solution for Advent of Code 2017 - Day 24: Electromagnetic Moat

Link to the puzzle text

Part 1

In this puzzle, we have a list of bridge parts described by two connectors. Bridge parts can be connected, if their connectors are the same. For this check, both configurations of a bridge part are possible and each part can only be used once. We should find the bridge with the largest strength, as defined by the sum of all connectors used.

The number of possible bridges is relatively small, so we just generate all of them. We start with the initial connector and check for all possible next connections. For each fitting part, we return the current configuration and continue recursively with the current part now removed.

def generate_bridges(bridge_head, last_connection, available_parts):
    for i, part in enumerate(available_parts):
        if part[0] == last_connection:
            next_connection = part[1]
        elif part[1] == last_connection:
            next_connection = part[0]
        else:
            continue
        yield bridge_head + [part]
        
        yield from generate_bridges(bridge_head + [part],
            next_connection,
            available_parts[:i] + available_parts[i + 1:])

Once we have all bridge, we can calculate the strength of all of them and take the largest.

Part 2

In part 2, we should search for the bridge with the most parts instead. We are asked to return the largest strength of all longsest bridges.

We also need to generate all possible bridges for this part. For finding the longest bridge, we introduce two new variable keeping track of the longest and their strength:

max_length_strength = 0
max_length = 0
for bridge in generate_bridges([], 0, parts):
    strength = sum([sum(part) for part in bridge])
    if len(bridge) >= max_length:
        max_length_strength = max(max_length_strength, strength)
        max_length = len(bridge)

Link to my solutions