Solution for Advent of Code 2015 - Day 19: Medicine for Rudolph

Link to the puzzle text

Part 1

In the first part, we are given a string and a number of production rules to turn substrings into other substrings. So a rule a -> b can turn ccaac into ccbac or ccabc. We are asked to find all possible results of a one time application of any rule.

For this, I iterated over all rules. If the left part of the rule was part of the starting string, I replaced the subpart according to the rule. The resulting new string was added to a set to remove duplicates. If a condition appears multiple times in the starting string, we iterate over all places.

def find_all_replacements(string, rules):
    results = set()
    for pattern, replacement in rules:
        num_patterns = string.count(pattern)
        for i in range(num_patterns):
            replaced = replace_n(string, pattern, replacement, i)
            results.add(replaced)
    return results

In the code above, the helper function replace_n replaces the ith occurance of pattern in string by replacement. To get the final answer, we print the amount of strings in the result set.

Part 2

Part 2 of this puzzle was more of a search problem. We are given the same production rules and are asked to find which applications of rules resulted in a transformation of e to our given string.

For that, we reversed the problem and tried turning our given string into e using the reversed rules. During parsing, the reversed rule mean the original a -> b became b -> a. Afterwards we used a search algorithm to find the number of rule applications needed to turn our starting string into e. We start with our given string and for each possible replacement using the reversed rules, we add this replacement to a queue. Previously seen string are skipped to remove duplicate work. Once we can replace the current string fully with a single e, we are done and return the number of rule applications we had to take.

queue = [(0, 0, starting_string)]
while len(queue) > 0:
    _, current_length, current_string = heapq.heappop(queue)
    if current_string == "e":
        print(current_length)
        break
    for replaced in find_all_replacements(current_string, rules_backward):
        heapq.heappush(queue, (len(replaced) + current_length, current_length + 1, replaced))

This search was quick enough and did find the correct solution.

I did find a short method in the reddit solution thread afterwards:

len(string) - #Rn - #Ar - 2*#Y - 1

Link to my solutions