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

• 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:

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

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 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 of the y-axis. Next, adding the z-axis and shifting all axises 120 degrees means that each hex can be made up of three points instead of two. Again, I refer to Chris's post and this image that illustrates the concept wonderfully:

Credit Chris Schetter (Hexagon grids: coordinate systems and distance calculations)

Continue reading

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 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:

1 2 3 4 >>> max(d) 3 # This is the *maximum value of the dictionary's keys*. >>> max(d, key=d.get) 2 # This is the *key of the maximum value in the dictionary*.
Continue reading

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 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:

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

I taught myself Python a few years ago by following the wonderful Learn Python the Hard Way (LPTHW) series by Zed A. Shaw. Since then, I have spent a decent amount of time in Python largely in the Django framework. Django is a lot of fun to work with because it abstracts away much of the complexities of developing a full-featured web application in Python. In this way, however, it has also led me to forget some of the basic Python that I learned through LPTHW.

In order to recapture some of those early lessons (and maybe learn a few more Python 3 specific ones), I worked through (part of) the 2017 Advent of Code, a 25-day, language agnostic programming challenge series developed by Eric Watsl. I originally thought about using the series to learn a new language, but eventually realized that I still have a long way to go in Python.

This series explores my (often very basic) revelations and lessons learned while completing 20 of the 25 days of challenges (vacation travel cut the series short for me). The code I used for each day is available on GitHub. Also check out the advent-of-code and advent-of-code-2017 GitHub topics to see the many solutions people have developed in various languages.

• Day 1: zip()
• Day 2: itertools.combinations()
• Day 3: Manhattan Distance
• Day 4: set()
• Day 5: Profiling
• Day 6: max(x, key=y)
• Day 7: RuntimeError: dictionary changed size during iteration
• Day 8: Regular Expressions
• Day 9: Lookahead, Lookbehind
• Day 10: functools.reduce()
• Day 11: Navigating a Hexagon Grid
• Day 12: Recursion
• Day 13: Shallow vs. Deep Copy
• Day 14: Hexadecimal to Binary
• Day 15: progressbar2
• Day 16: One Billion Permutations in 0.535 Seconds
• Day 17: collections.deque()
• Day 18: Negative Numbers and str.isdigit()
• Day 19: The Internet is Not a Big Truck
• Day 20: Reading from a File

Continue reading