Day 16: One Billion Permutations in 0.535 Seconds

• Challenge: Day 16: Permutation Promenade
• Solution: advent-of-code-2017/16

Ok, not really (: This challenge involved making specific modifications to a list 1,000,000,000 (one billion) times. Out of curiosity, the first thing I did was set up a progress bar loop to run the actual modifications all one billion times. The resulting progress bar estimated that the entire operation would take around 133 days. So... a different approach:

0
1
2
3
4
5
6
7

positions = [...]
movements = [...]
possibilities = [positions]
while True:
    positions = move(positions, movements)
    if positions in possibilities:
        break
    possibilities.append(positions)

Because the movements are always the same, eventually the positions list elements will return to their initial state. In this case, that happened on the 41st movement, making for a possibilities list of size 42. Armed with the answer to the ultimate …

Day 11: Navigating a Hexagon Grid

• Challenge: Day 11: Hex Ed
• Solution: advent-of-code-2017/11

I fought with how to create and navigate a hexagon grid for a bit before I stumbled on an extremely useful post by Chris Schetter: Hexagon grids: coordinate systems and distance calculations. Working in 2d grids (with four possible movement directions) in Python is fairly easy with some dictionaries, but a hexagon grid means there are six potential directions and simple calculations of x,y coordinates won't quite get the job done. What Chris explains so well is a simple concept: flip the grid and add a z-axis.

For my solution, I "flip" the grid by turning it to the right twice such that north and south become east and west:

  \ n  /
nw +--+ ne              sw +--+ nw
  /    \                \ /    \ /
-+      +-    ---->    s +      + n
  \    /                / \    / \
sw +--+ se              se +--+ ne
  / s  \

This puts north and south along the x-axis instead …

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 …

Day 1: zip()

• Challenge: Day 1: Inverse Captcha
• Solution: advent-of-code-2017/01

This challenge taught me about Python's built-in zip function. The basic goal is to compare values in a list with specific positional relationships to other values (e.g. next to, X steps from, etc.) in the same list. zip assists with this task by combining multiple lists in to tuples. My initial solution used a construct similar to:

0
1
2
3
4

digits = [1, 2, 3, 4, 5]
total = 0
for a, b in zip(digits[::1], digits[1::1]):
    if a == b:
        total += a

This code uses zip and Python's list indexing to evaluate each element in the digits list against the next element in the list by creating and combining two lists: one starting from the first digit in digits and one starting from the second digital in digits. Here are what …