Advent of code 2020, Day 19

Okay, after a bit of a delay...

I got very stuck on Day 19, but couldn't let it go. I kept having great ideas for improving the solution to part 2, but couldn't get it to run fast enough to find the solution. After talking to a friend I finally solved it on Christmas, but then had family time and needed a break from AOC -- and then my country was falling apart.... The good news is that my grandmother recovered from COVID... and promptly broke her hip. But she's recovering from that. It's been an eventful few weeks.

So I'm finally back to completely the advent of code, but at a more relaxed rate. My goal is to complete one AOC day per week. I may well do more than that, but I'm balancing other responsibilities, so I'm keeping my goal attainable. I do want to complete all the puzzles, so this gives me the push to do it.

Okay, Day 19 Monster Messages.
Part 1 is pretty straightforward. We read in a list of rules, followed by a list of messages. We need to find out how many messages match Rule 0. Rule 0, of course, relies on Rules 1, 4, and 5, Rule 1 relies on Rules 2 and 3.. etc.

So, here's my main routine:

def part1(filename):
    (rules, messages) = read_data(filename)

    rule_dict = make_rulesdict(rules)
    combos = create_combinations(rule_dict)

    count = 0
    for mess in messages:
        if mess in combos: 
            count+=1
    return(count)

First, we read in the data, then make a dictionary for all the rules, then create all possible combinations and compare with the messages to see which match.

Making the rules dictionary just requires a bit of parsing.

def make_rulesdict(rules):
    rule_dict={}

    for rule in rules:
        num, definition = rule.split(': ')
        if '"' in definition:
            rule_dict[num] = definition.replace('"', '')
        else:
            rule_dict[num] = definition.split(' ')
    return(rule_dict)

Creating all the combinations is a little clunky but works. I set up a queue and add Rule 0. As Rule 0 relies on Rules 1 and 5, those get added to the queue as Rule 0 is processed, then the same process is carried out for Rule 1, then Rule 5, etc:

def create_combinations(rule_dict, first_rule = '0'):

    from collections import deque

    rules = deque()
    if '|' in rule_dict[first_rule]:
        rules.append([rule_dict[first_rule]])
    else:
        rules.append(rule_dict[first_rule])

    done = [] #will hold all combinations that have been played out
    while len(rules)>0:
        rule = rules.pop()

        new_rules = process_rule(rule, rule_dict)
        for new_rule in new_rules:
            if isdone(new_rule):
                done.append(''.join(new_rule))
            else:
                rules.insert(0, new_rule)

    return done

For more details on how the rules are processed and how ors are dealt with, see my Github.

Part 2 becomes significantly more difficult.

As you look over the list of messages, you realize your matching rules aren't quite right. To fix them, completely replace rules 8: 42 and 11: 42 31 with the following:

8: 42 | 42 8

11: 42 31 | 42 11 31

This small change has a big impact: now, the rules do contain loops, and the list of messages they could hypothetically match is infinite. You'll need to determine how these changes affect which messages are valid.

So now the rules depend on themselves, creating an infinite solution space. This is the part that I banged my head against for days.

Me, Attempt 1: I’m going to try building all messages, but cut the process short if the length of the message is longer than the length of the longest message. If it bogs down, I’ll try something else.

Narrator: It did bog down.

Me: This is going to require recursion, isn’t it? Ugh.

Narrator: Actually it did not.

I originally used a list to keep track of the rules, lists are slow, so I switched to a python queue instead to speed things up.

from collections import deque

This helped, but not enough. More optimisation followed.

After 3 days I went back and read the instructions again. The part where it said 'don’t make a general solution'. I started a working through the rules on a sheet of paper (I can't find that sheet or I would include a photo of it here).

So what we have is that 8 is one or more 42s and 11 is one or more 42s followed by one or more 31s. How can we represent this? It does remind me of a regex solution, but I’m not quite sure how to implement that. I’ve been trying to make a general solution, but the puzzle states pretty clearly that we will need to hardwire our solution.

This lead me closer and closer to a solution, but it was still too slow to converge.

Then a friend said: "Oh that! That was a brain twister. I transformed each 5 digit seq into 0 or 1 for it if matches a 31 or 42 .. discarding all other messages.. then the new list needed only 1s bef 0s, more 1s than 0s."

Ah-ha! I had all the pieces, but hadn't quite put it together. Here's how I did it:

def check_message(mess, combos_42, combos_31):

    seg_length = len(combos_42[0])
    num_segs = int(len(mess)/seg_length)
    count_42 = 0
    count_31 = 0

    #check that first and second segment is in combos_42
    for i in range(2):
        segment = mess[i*seg_length:(i+1)*seg_length]
        if segment not in combos_42:
            return False
    count_42 = 2
    i=2
    #allow for more in 42, keep count
    while mess[i*seg_length:(i+1)*seg_length] in combos_42:
        count_42+=1
        i+=1

    #now check 31s
    while mess[i*seg_length:(i+1)*seg_length] in combos_31:
        count_31+=1
        i+=1

    if i < num_segs:
        return False

    if (count_31 > 0) and (count_31 < count_42):

        return True

    return False

Then Part 2 is solved by:

def part2(filename):

    (rules, messages) = read_data(filename)

    rule_dict = make_rulesdict(rules)
    #all rules lead to 42 and 31
    combos_42 = create_combinations(rule_dict, first_rule = '42')
    combos_31 = create_combinations(rule_dict, first_rule = '31')

    matches = []

    for mess in messages:
        if check_message(mess, combos_42, combos_31):
            matches.append(mess)

    return(matches)

In other words, we create combinations based on Rule 42 and Rule 31 -- everything downstream from that does not create a loop, so this is easily done. Then we use that result to check the messages, requiring that the message start with at least two iterations of Rule 42, followed but at least one iterations of Rule 31 and that the number of iterations of Rule 31 is less than that of Rule 42. Hard to say, harder to implement. But it worked and I got part 2. Then took 3+ weeks off. :-).

Stay tuned day 20.

Full solution for Day 19, including a few of my missteps, is on Github.