This post is part of the series, Advent of Code 2017,
where I work my way through (part of) the 2017 Advent of Code
challenges in order to re-learn some of the basics of Python and
reflect on some simple concepts and functionality. All my challenge
code is available in cdubz/advent-of-code-2017
on GitHub.
Day 16: One Billion Permutations in 0.535 Seconds
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:
1
2
3
4
5
6
7
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:
9
10
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!
Continue reading