Erik Ramsgaard Wognsen

Thoughts & technology

AoC 2017 Day 8: Fell Into a Python Pitfall

I’ve been using and enjoying Python since 2009, but while doing Advent of Code again this year, I stumbled upon a Python feature that led to a subtle bug. Advent of Code spoiler ahead.

The Puzzle

In AoC 2017 you travel inside Santa’s computer, fixing and computing things so the Naughty or Nice List can be printed on time for Santa to deliver the presents on time.

The puzzle for Day 8 gives you a textual input such as

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

and asks you to find the largest value in any register after executing the given instructions (on some imagined CPU). The registers (which are a, b, and c in the above), are all initialized to zero. The largest value in the example is 1, which is in the a register at the end.

The real puzzle input is much larger and requires an automated solution. My approach was to build a register valuation dictionary, update it according to the instructions, and then find the largest value.

My Solution

I wrote this code (refactored):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from operator import lt, gt, le, ge, eq, ne

def day8(input):

    instructions = [line.split() for line in input.splitlines()]
    register_names = set(instruction[0] for instruction in instructions)
    registers = {register_name: 0 for register_name in register_names}

    for mod_reg, mod_op, mod_amt, _, cond_reg, cond_op, cond_const in instructions:
        if eval_cond(registers[cond_reg], cond_op, cond_const):
            registers[mod_reg] += (1 if mod_op == 'inc' else -1) * int(mod_amt)

    return max(registers.values())

def eval_cond(a, cond_op, b):
    return {'<': lt, '>': gt, '<=': le, '>=': ge, '==': eq, '!=': ne}[cond_op](a, b)

I ran it on the test input, and the test passed. Good! Then I ran it on the main puzzle input, got a nice looking number, and submitted my result.

Incorrect… Huh.

Can you spot the mistake?

I later fixed it in line 10, and it relates to types.

Strong and Weak Typing

One of the things I like about Python compared with other dynamically typed languages is that Python is also strongly typed.

JavaScript — which is dynamically and weakly typed — implicitly converts types, such as from number to string:

1
2
> 2 + '2'
'22'

Python doesn’t — it forces you to choose:

1
2
3
4
5
6
7
8
9
10
>>> 2 + '2'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'str'

>>> 2 + int('2')
4

>>> str(2) + '2'
'22'

But ok, let’s try mixed type comparison in JavaScript:

1
2
3
4
5
> 3 < '5'
true

> 30 < '5'
false

And Python:

1
2
3
4
5
>>> 3 < '5'
True

>>> 30 < '5'
True

(!)

In fact, any integer compares less than any string in CPython 2.

This was the reason for my bug — I kept comparing integer register values to unparsed text strings:

1
    if eval_cond(registers[cond_reg], cond_op, cond_const):

After adding the integer parsing, it worked as expected:

1
    if eval_cond(registers[cond_reg], cond_op, int(cond_const)):

Why Does It Work Like This?

It’s not that I had expected Python to suddenly do implicit type conversion for comparison — I had just forgot the call to int — even though I had remembered it while parsing the modification amount mod_amt.

What I would have hoped for was a loud error rather than a subtle bug. It turns out there is both a reason for the subtle behavior in Python 2 and the option to get a loud error — by using Python 3.

From the Python 2 docs:

Objects of different types […] are ordered consistently but arbitrarily (so that sorting a heterogeneous array yields a consistent result).

From the Python 3 docs:

The <, <=, > and >= operators will raise a TypeError exception […] when the objects are of different types that cannot be compared […].

Mixed-Type Operators Can Be Good

A little history lesson on stackoverflow.com explains why heterogeneous lists are not cool anymore, and I’m happy about the change in comparison from Python 2 to 3.

But that does not mean that different types should never be combined with operators.

Let’s take another look at JavaScript:

1
2
> '3' * 4
12

And Python:

1
2
>>> '3' * 4
'3333'

If you were expecting this to evaluate to 12 — either because you came from a weakly typed language, or because you simply forgot to parse the string as an integer — you might also be confused. But I really like this Python behavior.

“String multiplication”, or rather sequence replication, is much more useful than heterogeneous list sorting — so useful that it is acceptable for it to risk being confusing to newcomers.

And as opposed to string/integer comparison, it’s also less likely to lead to subtle bugs. While the string/integer comparison returned a boolean just like integer/integer comparison, string/integer multiplication returns a string, and not the integer a novice might be expecting.

Comments