Advent of Code 2017: Days 16 - 20

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 question of life, the universe, and everything, it was much easier to determine the value of positions at the one billionth permutation:

 8
 9
10

pos = 1000000000
answer_key = pos - int(pos/len(possibilities)) * len(possibilities)
print(possibilities[answer_key])  # 1,000,000,000!

This all takes a little over half a second, as opposed to the 133 days of processing that would be needed to run all one billion permutations. Phew!

Day 17: collections.deque()

• Challenge: Day 17: Spinlock
• Solution: advent-of-code-2017/17

Speed is the key once again with this challenge. After optimizing my initial solution as best I could, my program was still facing an 18 hour execution time to find the correct answer. Eventually I found my way to collections.deque to speed things up tremendously. Python's documentation sums up the difference between a deque and list like so:

Deques are a generalization of stacks and queues (the name is pronounced "deck" and is short for "double-ended queue"). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

Simply changing the list, which goes through 50,000,000 (50 million) insert operations, to a deque cut the execution time down a bit, but the big time saver ended up being deque.rotate. Using rotate allowed the insert operations to be replaced with much fast append operations. These two changes cut the execution time to about three minutes (from 18 hours).

Day 18: Negative Numbers and str.isdigit()

• Challenge: Day 18: Duet
• Solution: advent-of-code-2017/18

I was stuck with a bug while working on a piece of this challenge that had to identify the difference between an alpha and numeric string. Checking for alpha with str.isalpha() worked well enough but for some reason I wasn't having the same luck with str.isdigit():

0
1
2
3
4
5
6
7
8
9

>>> 'A'.isalpha()
True
>>> 'b'.isalpha()
True
>>> '1'.isdigit()
True
>>> '0'.isdigit()
True
>>> '-1'.isdigit()
False  # Oh no!

What these examples illustrate is that str.isdigit() does not return True for negative numbers. The Python documentation explains why (emphasis mine):

Return true if all characters in the string are digits [...]

The result for negative number is False because the negative sign itself (-) is not a digit.

Day 19: The Internet is Not a Big Truck

• Challenge: Day 19: A Series of Tubes
• Solution: advent-of-code-2017/19

This challenge didn't uncover any major new Python discoveries, but it was an amusing reminder of the infamous words of Ted Stevens:

I just the other day got, an internet was sent by my staff at 10 o'clock in the morning on Friday and I just got it yesterday. Why?

Because it got tangled up with all these things going on the internet commercially...

They want to deliver vast amounts of information over the internet. And again, the internet is not something you just dump something on. It's not a truck.

It's a series of tubes.

And if you don't understand those tubes can be filled and if they are filled, when you put your message in, it gets in line and its going to be delayed by anyone that puts into that tube enormous amounts of material, enormous amounts of material.

Ouch.

Day 20: Reading from a File

• Challenge: Day 20: Particle Swarm
• Solution: advent-of-code-2017/20

This solution makes use of earlier lessons about Manhattan Distance and the key argument for min() and max(), but beyond that nothing much new was introduced. One thing that has been important throughout this experience is reading content from a file, as most challenges include some long form of input data.

Compound statements such as if and for are as popular and well known in Python as probably any other language, but the other statement that has come in handy for almost every challenge so far is the with statement. When used with a context manager such as open(), the with statement makes it simple to do things like handle files without worrying about things like closing the file manually. The simplest example is to process each line of a file like so:

0
1
2

with open('file.txt') as f:
    for line in f:
        print(line)

This code opens a file.txt and assigns it to the variable f, uses a for loop to print each line of the file, and finally closes the file (automatically!). All kinds of things can be done with each line or the file itself here.

Jeff Knupp provides a very insightful read on context managers in general: Python with Context Managers.

If all lines (or other elements) of a file need to be evaluated together, the open function can be used to cram things in to a list, dictionary, or other structure easily:

0

lines = [line.rstrip() for line in open('input.txt').readlines()]

This simple statement will read each line of input.txt in to a list, applying rstrip each time to remove trailing data (i.e. the line breaks). Comprehensions like this can quickly accomplish basic data manipulation to turn file lines in to more easily manageable structures.