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

- Parsing the puzzles efficiently
- Cool tools from Python’s standard library
- 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:

- the
**built-in functions**
- some interesting modules:
**re** for regexes
**collections** for some useful data-structures
**itertools**, your go-to module for seemingly complex things
**math**
**bisect**
**dataclasses**

And a bit more.

You should also know the basic data types:

- lists and their common operations
- set are very useful, some operations like union or intersection can
- dict. Yes, you know that, but have a look at the complete API anyway.

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
**basics**
- the
**iterator-related builtins**:
- all()
- any()
- enumerate()
- map()
- filter()
- reversed()
- min()/max()/sum()
- next()
- zip()
- …

- the
**conversion-related** builtins:
- int(), str(), bytearray(), bytes(), list(), bool(), float(), …
- ord()/chr() can be useful to convert to/from ASCII
- bin()/hex()/oct()/format()/repr() for formatting

- the
**math things**:
- abs(), pow(), round()
- complex() (yes, python has a Complex type for complex numbers out of the box!)

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** 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**
**combinations**
**permutations**

`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.