KeiruaProd

I help my clients acquire new users and make more money with their web businesses. I have ten years of experience with the technical aspects of growing SaaS projects using data science for decision-making. If that’s something you need help with, we should get in touch!

Preparing Adventofcode in Python 2/3, standard library

This is the part 2 of the “Getting ready for Adventofcode in Python” series.

  1. Parsing the puzzles efficiently
  2. Cool tools from Python’s standard library
  3. Useful algorithms and data structures for competitive programming

Python’s standard library has A LOT of modules with useful only an import away.

The plan

My goal here is NOT to solve the problems with built-in things, but to get a better understanding of python’s toolbox.

For adventofcode, here is my list of few things worth knowing. We’ll have a look at:

And a bit more.

You should also know the basic data types:

Of course this is by no mean a comprehensive cheatsheet, but maybe a starting point to explore some ideas ?

built-in functions

There are 70 built-in functions in Python right now. That’s not a lot! Look them up

In the context of Adventofcode, and of your general understanding of Python, it can be useful to be familiar with only a handful:

The most important for AoC are those linked to iterable, we’ll dive a bit deeper later on with itertools.

re for regular expressions

I already talked about them in part 1, regular expressions or regexes are very useful in AoC. Once you know the syntax for describing a pattern, there are 4 interesting functions (5 if you use compile): search, split, findall, sub.

search searches if a string matches a pattern:

re.search(pattern, string)
re.search(r'\d+', "123")
<re.Match object; span=(0, 3), match='123'>
re.search(r'\d+', "abc") is None
True

split splits a string by the occurrences of pattern:

re.split(pattern, string)
re.split('[a-f]+', '0a3B9', flags=re.IGNORECASE)
['0', '3', '9']

findall returns all non-overlapping matches of pattern in string, as a list of strings or tuples

re.findall(pattern, string)
re.findall(r'(\w+)=(\d+)', 'set width=20 and height=10')
[('width', '20'), ('height', '10')]

sub performs replacements according to a pattern

re.sub(pattern, string, maxsplit=0)
re.sub(r'\sAND\s', ' & ', 'Baked Beans And Spam', flags=re.IGNORECASE)
'Baked Beans & Spam'

They may return a match object so it can be useful to know how to query it.

itertools

itertools is reaaaally powerful. It contains a lot of things for iterating through different kind of data and iterators. It is hard to grasp at first, because it involves a functional way of thinking you may not use every days.

For a comprehensive article on the matter, head to Realpython. Use the function to learn how they behave ! This is paramount.

For a quick cheatsheet, you may need:

product is the cartesian product, equivalent to a nested for-loop

import itertools as it
list(it.product([1, 2, 3], ['A', 'B', 'C']))
[(1, 'A'), (1, 'B'), (1, 'C'), (2, 'A'), (2, 'B'), (2, 'C'), (3, 'A'), (3, 'B'), (3, 'C')]

So you write something like this:

for (i, j) in product(p, q):
	

and it is the same as

for i in p:
  for j in q: 
    

More interesting, permutations and combinations are similar, except that permutations include all possible orderings (eg AB and BA). Both are very useful :

# generates all the existing arrangements of [1, 2, 3]
>>> list(it.permutations([1, 2, 3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
# generates all combinations of 2 elements with [1, 2 and 3]
>>> list(it.combinations([1, 2, 3], 2))
[(1, 2), (1, 3), (2, 3)]

collections

The collections module contains a few powerful data structures. You may want to know:

deque: double-ended queue

deque is the generalization of a stack and queue: you can add elements from the “right” (append(), pop()) or from the left(appendleft(), popleft()).

dq = deque(iterable) # Creates a deque with some elements
dq.append(object) # Adds object to the right of the deque
dq.appendleft(object) # Adds object to the left of the deque
dq.pop() -> object # Removes and returns the right most object, or raises an IndexError
dq.popleft() -> object # Removes and returns the left most object, or raises an IndexError   

One use-case is graph traversal problems. Breadth-first search is one option, there are others (depth-first search, dijkstra) but this is a popular starting point.

Counter

If you want to count how many times each value is in a list, Counter is here to help. You can initialize it with a list, update it, or ask for a value that is not there.

from collections import Counter
cnt = Counter(['a', 'b', 'a']) # cnt = Counter({'a': 2, 'b': 1}): there are 2 "a" and 1 "b"
cnt['a']+=1 # cnt = Counter({'a': 3, 'b': 1})
cnt['b'] # = 1
cnt['plop'] # = 0

There are a few others.

math

You may need it at some point, there are too many useful things in there: the math module has a lot of number-theory functions, trigonometry functions… that can be useful. Usually, AoC is not heavy on math and when that’s the case, to my knowledge it focuses on integer numbers and large numbers. Lean on its documentation.

bisect

You may need to search for a value in an ordered list. bisect does that in O(log(n)) time, which is very fast:

import bisect
values = [1, 2, 12, 42, 37, 59]
# search: 'If I were to insert 3, at what index would I do that?'
bisect.bisect(values, 31) # 3

# sorted insertion
bisect.insort(values, 31)
>>> values
[1, 2, 12, 31, 37, 42, 59]

dataclasses

For a data structure that will hold many attributes, dataclasses.dataclass can be handy instead of using a dict or writing the class yourself:

from dataclasses import dataclass

@dataclass
class InventoryItem:
    """Class for keeping track of an item in inventory."""
    name: str
    unit_price: float
    quantity_on_hand: int = 0

    def total_cost(self) -> float:
        return self.unit_price * self.quantity_on_hand

Going further

This is already quite a broad list, but I’ve found learning and using those to be useful.

In general, as part of my learning of Python, I’ve also found the following modules relevant, even though you may not need most ofe them as part of AoC:

And in order to go deeper in my understanding of the language, it was interesting to spend some time on some concepts, and their implementation in Python:

See a typo ? You can suggest a modification on Github.