This is the part 2 of the “Getting ready for Adventofcode in Python” series.
Python’s standard library has A LOT of modules with useful only an import away.
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 ?
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.
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 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)]
The collections module contains a few powerful data structures. You may want to know:
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.
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.
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.
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]
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
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:
exceptionsfunctoolsoperatorpprintenumtypingpicklesqlite3zlibcsvhashlibiotimeargparsejsonunittestabcAnd 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: