Advent of Code: Day 24

For Day 24, the challenge is to calculate the optimal combination of pieces to build a bridge of sufficient distance and strength.

My brute force solution in Python is:

paths = {}

with open("input.txt", "r") as o:
    for line in o:
        parts = line.strip().split("/")
        f = int(parts[0])
        t = int(parts[1])
        if f not in paths:
            paths[f] = []
        if t not in paths:
            paths[t] = []
        paths[f].append(t)
        paths[t].append(f)

def max_score(paths, used_parts, current_pos):
    scores = [0]
    for next_path in paths.get(current_pos, []):
        if (current_pos, next_path) in used_parts or (next_path, current_pos) in used_parts:
            continue
        scores.append(max_score(paths, used_parts.union({(current_pos, next_path)}), next_path) + current_pos + next_path)
    return max(scores)

def max_length(paths, used_parts, current_pos):
    lengths = [(0, 0)]
    for next_path in paths.get(current_pos, []):
        if (current_pos, next_path) in used_parts or (next_path, current_pos) in used_parts:
            continue
        m = max_length(paths, used_parts.union({(current_pos, next_path)}), next_path)
        lengths.append((m[0] + 1, m[1] + current_pos + next_path))
    return sorted(lengths, key = lambda x: x, reverse=True)[0]

print "Part 1", max_score(paths, set(), 0)
print "Part 2", max_length(paths, set(), 0)[1]

Advent of Code runs every day up to Christmas, you should join in!.

Show Comments

Get the latest posts delivered right to your inbox.