Advent of Code 2017: Days 6 - 10

Day 6: max(x, key=y)

• Challenge: Day 6: Memory Reallocation
• Solution: advent-of-code-2017/06

Another simple revelation on built-ins from this challenge: the key argument can be used to modify what is evaluated by the max function. This concept is explained in detail as part of the accepted answer to this Stack Overflow post: python max function using 'key' and lambda expression.

For Python dictionaries, this means that the get() method can be used to return the key of the maximum value in a dictionary. This works because the max function sends each of the dict keys to the dict.get() method and evaluates that result instead of the key itself. Without this argument, max will actually evaluate the dictionary's keys, which isn't terribly useful:

0
1
2
3
4

>>> d = {0: 1, 2: 5, 3: 4}
>>> max(d)
3  # This is the *maximum value of the dictionary's keys*.
>>> max(d, key=d.get)
2  # This is the *key of the maximum value in the dictionary*.

Day 7: RuntimeError: dictionary changed size during iteration

• Challenge: Day 7: Recursion
• Solution: advent-of-code-2017/07

My initial approach to this problem was to organize all "programs" in to a dictionary and whittle away at any program that wasn't a child of another program:

0
1
2
3
4
5

programs = {'<name>': {'weight': <int>, 'children': []}, ...}
for program, data in programs.items():
    for child in data.get('children'):
        if child in programs:
            del programs[child]
print(list(programs)[0])

The end result should be a single entry in programs that does not appear in the children list of any other program - aka the base of the recursion.

After running this successfully a few times and submitting my answer, I did some other things before coming back for part two. To my surprise, when I tried to run the same code again, it produced an error: RuntimeError: dictionary changed size during iteration

While trying to figure out why this was happening all of a sudden, I realized that I had, in the course of doing other things, changed to an environment with Python 3 as the default python, whereas my original environment used Python 2.

This error happens because dict.items() is a simple list in Python 2, but it is a view in Python 3. If my loop had not been modifying the contents of the dictionary, this would not have been a problem because either type can be iterated in the same way. However, since I was modifying the dictionary in place, Python 3 raises the RuntimError because the actual dictionary object (not the list copy of its items, as with Python 2) is being modified while the code is still in the loop.

The quick fix for this issue is to make a copy of the dictionary and iterate over that instead. E.g. by changing the for-loop like so:

1
2

for program, data in dict(programs).items():
    [...]

Day 8: Regular Expressions

• Challenge: Day 8: I Heard You Like Registers
• Solution: advent-of-code-2017/08

I have used regular expressions in the past two challenges. Every time I need a bit of regex I think to myself, "I should learn more about this in depth". I have yet to scratch that particular itch, but my general knowledge about them came in handy for this challenge.

The challenge provides line-by-line string instructions for modifying values, like this example (from the challenge):

0
1
2
3

b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10

Looking at this, there are four important pieces of information:

1. The "variable" to be modified (a, b, c, etc...).
2. How to modify that variable ("inc" for increase, "dec" for decrease).
3. The amount to modify the variable by.
4. An expression to decide whether or not to perform the actual modification.

Regular expressions to the rescue! The first thing I tend to do when trying to write a regular expression is pull up one of the many useful websites that will evaluate expressions in real time. In this case I used regex101.com, which will take the text to be searched, highlight the relevant parts, and provide explanations as you type the expression. I ended up with the following expression for the challenge:

([a-z]+) (inc|dec) (-?\d+) if ([a-z]+) (.+) (-?\d+)

This regex, the example input, and all of the useful context can be viewed at the following URL: https://regex101.com/r/O3xLTL/2.

Using Python's re module and some small modifications to the expression, the relevant capture groups can be organized in to more descriptive variables:

0
1
2
3
4
5
6
7

import re

with open('input.txt') as f:
    for line in f:
        result = re.search('(?P<register>[a-z]+) (?P<op>inc|dec) (?P<amt>-?\d+) '
                           'if (?P<cond_register>[a-z]+) (?P<cond>.+) '
                           '(?P<cond_amt>-?\d+)', line.strip())
        [...]

Python's re.search uses the syntax (?P=<name>[expression]) to enable this grouping. result.group('register') run on the first line produces "b", result.group('cond') run on the second line produces "<", and so on. This grouping further enhances the usefulness of regular expressions and makes building expressions (and evaluating functionality in general) a lot of fun.

Day 9: Lookahead, Lookbehind

• Challenge: Day 9: Stream Processing
• Solution: advent-of-code-2017/09

Regular expressions to the rescue again! Part one of this challenge was fairly straightforward and easy to complete with two passes of expressions to remove characters from a long string.

Part two was a bit more difficult because it was necessary to count the removed characters. I wanted to build on part one's character removal by comparing the string length before and after instead of trying to significantly modify the expression to use (and add up) grouping. The problem with this approach is that it requires matching strings that shouldn't be included in the count of removed characters because the task is to remove characters between brackets (< and >):

0
1
2
3

>>> import re
>>> string = '<characters>'
>>> print(re.sub(r"<[^>]+>", "", string))
   # (an empty string)

How can the expression <[^>]+> be changed to capture what is inside the brackets, but not the brackets themselves? With lookaround assertions! A lookahead assertion has the format (?=...) for positive assertions and (?!...) for negative assertions and a lookbehind uses (?<=...) and (?<!...) respectively.

Replacing the surrounding brackets with a single lookbehind solves the problem of capturing the brackets:

0
1
2
3

>>> import re
>>> string = '<characters>'
>>> print(re.sub(r"(?<=<)[^>]+", "", string))
<>  # only the brackets remain

Now the expression produces the desired effect - it removes all characters inside brackets, but not brackets themselves. This works because the positive lookbehind assertion ((?<=<)) ensures that the pattern matches, but does not actually match it. The remaining portion of the expression ([^>]+) does the actual matching of any character other than > (aka, everything inside the brackets!).

Day 10: functools.reduce()

• Challenge: Day 10: Knot Hash
• Solution: advent-of-code-2017/10

Part two of this challenge dealt in part with performing operations on each pair of two items cumulatively in a list of items. For example, multiplying all values in the list [1, 2, 3, 4, 5] should yield 120 because 1 * 2 = 2 * 3 = 6 * 4 = 24 * 5 = 120. An easy way to do this in Python is to iterate the list and deal with each element one-by-one:

0
1
2
3
4
5

>>> l = [1, 2, 3, 4, 5]
>>> result = l[0]
>>> for number in l:
>>>     result *= number
>>> print(result)
120

While this method certainly is not complicated, the code would have to be modified to work with other iterables and in many cases may not be so clean. As an alternative, functools.reduce() can perform the same action in a single line, on any iterable:

0
1
2
3
4

>>> from functools import reduce
>>> from operator import mul
>>> l = [1, 2, 3, 4, 5]
>>> print(reduce(mul, l))
120

This example uses operator.mul for a simple multiplication function. But reduce() will work with any function that accepts two arguments (including lambdas!):

0
1
2
3

>>> from functools import reduce
>>> l = [1, 2, 3, 4, 5]
>>> print(reduce(lambda i, j: i * j, l))
120