Advent of Code: Day 3


Part 1: Given a string of <>^v characters which mean move west, east, north, or south respectively and starting at the origin, how many unique positions do you pass through?

presents = collections.defaultdict(lambda : 0)
location = 0+0j

directions = {'<': -1+0j, '>':  1+0j, '^':  0+1j, 'v':  0-1j}

for c in
    location += directions.get(c, 0+0j)
    presents[location] += 1


There are two tricks here, both of which I’ve used before. First, we have use collections.defaultdict to implement a basic counter. That way, we can safely do += 1 to any element without worrying if it exists first and without initializing the (potentially infinite) grid.

Second, we represent points using complex numbers. That has the advantage of meaning that movement is just adding two (complex) numbers together and we can directly index the presents dictionary with the locations.

At the end, the len of a dictionary is the number of keys, thus exactly equal to the number of locations visited (which thankfully works correctly even with a defaultdict). Neat.

Part 2: Start with two actors, each at the origin. Apply alternating characters to first one then the other, such that ^v^v would result in one moving north twice, the other two south.

presents = collections.defaultdict(lambda : 0)
presents[0+0j] = 2

locations = [0+0j, 0+0j]
directions = {'<': -1+0j, '>':  1+0j, '^':  0+1j, 'v':  0-1j}

for i, c in enumerate(
    which = i % len(location)
    locations[which] += directions.get(c, 0+0j)
    presents[locations[which]] += 1


The basic code is the same here, the only difference is that we determine which actor is moving using modular arithmatic (%). One neat thing about this is that it scales without any other changes to any number of actors merely by putting more elements in the initial locations array.

comments powered by Disqus