Advent of Code is a coding competition, with one new challenge per day during December. I started writing the core of my own solutions, then I realized this wouldn’t be very interesting because (1) my own code is often very naive compared to the best ones, (2) the article was starting to get very long.

Instead, I will focus only on things I learned or already knew but experienced doing the challenges. I’ve been doing my implementations in Python and in C, but also read other solutions (mostly posted on Reddit) and have often been amazed by one-liners or very performant implementations.

Python

Logging

Logging is important, especially when you need some form of debugging

1
2
3
4
5

import logging

log_format = "%(asctime)s - %(name)s - %(levelname)s - %(message)s" 
logging.basicConfig(format = log_format, level = logging.INFO)
logger = logging.getLogger()

Along with logging, I appreciate the f-strings notations where the variable to output is directly shown in the format string.

• f-strings doc

Comparison

It’s actually possible to write several comparisons like:

1
2

if 1 < len < max_value:
	...

Type hints

Type hints are very probably over-kill for Advent of Code challenges, but coming from C, I like to use type hints as much as possible.

1

def get_calibration_value(s: str) -> int:

• Type hint for an array of ints: list[int]
• Type hint for an array of arrays: list[list[int]]

Enumerates

I wasn’t using very much enumerates in Python. They are very useful to simplify loops that need counters.

For example, in the following code, we automatically “map” the words to an incremented index:

1
2

for i, num in enumerate('one two three four five six seven eight nine'.split()):
	print(i, num)

Lists

When you pass a list to a function in Python, it’s the object that you provide. So, if the function modifies the list, the list will remain modified outside the function.

Example:

1
2
3
4
5
6
7

>>> a = [1,2,3,4]
>>> def modify(tab):
...     tab[0] = 'modified'
... 
>>> modify(a)
>>> a
['modified', 2, 3, 4]

If you don’t want that to happen, you can copy the list with mylist.copy().

List comprehensions

Reminder: it is possible to use conditions in list comprehensions. For example, the following get the positions of Os:

1
2
3

>>> column = '....O...O'
>>> [i for i in range(len(column)) if column[i] == 'O']
[4, 8]

• More on List comprehensions on Real Python

Tuples

The difference with a list is that tuples are immutable. You cannot assign to a tuple.

Sets

To initialize a set: a = set()

A set does not have redundancies.

So, to test that all elements of a table are zeroes, you can actually transform the list in a set and test: set(tab) == {0}

• Reminder: a set is defined with {}. A dict is a named set: { 'green' : True, 'blue' : False }.

Extended Slices

I had never used extended slices with a third argument. The syntax is exactly: mylist[first:last:step] which will produce mylist[first], mylist[first+step] … until mylist[last] not included.

Example:

• Extracting elements with even indexes: mylist[::2]
• Reversing order: mylist[::-1]

This works with lists, tupples and strings.

Ref: Understanding slice notation

Strings

• Important: keep in mind strings are immutable in Python. If you want to modify letters in a string, a common way is to transform them in a list, edit the list and join back.
• a[5:] works even if there are less than 6 characters in the string! It will return ''

Map

Map applies a function to elements of an iterable object. If we have a line of numbers, the following works:

1

nums = [int(i) for i in line.split(',') ]

But it also works with map:

1

nums = list(map(int, l.split(',')))

If you need to rule out some values, consider using filter: filter(function, iterable).

1

groups_tab = list(filter(None, groups.split('.'))) # remove empty groups

Priority queue

1

from heapq import heappush, heappop

A heap queue, also known as priority queue, will also keep the lowest value first:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

>>> from heapq import heappop, heappush
>>> pq = [(10, 'start')]
>>> heappush(pq, (2, 'test'))
>>> pq
[(2, 'test'), (10, 'start')]
>>> heappush(pq, (4, 'ajdkajdal'))
>>> pq
[(2, 'test'), (10, 'start'), (4, 'ajdkajdal')]
>>> heappop(pq)
(2, 'test')
>>> pq
[(4, 'ajdkajdal'), (10, 'start')]

Regex

I often need to match a given syntax and return only the part that matches. For example: Game 123 and I want to retrieve 123.

The way to do that is with a search and then use group on the match.

1
2
3

def get_id(line: str) -> int:
    match = re.search(r'Game ([0-9]+)', line)
    return int(match.group(1))

Remember that search only returns the first occurence. If you need them all, consider using findall.

• Find 3 letters: [A-Z]{3}. This will match ABC, or HSM but not H8T.

Reading a file

It’s not difficult to read a file line by line in Python. Pay attention that the following includes the trailing \n at the end of each line.

1
2
3

f = open('filename','r')
lines = f.readlines()
f.close()

If you don’t want those \n, you can remove them or simpler:

1

lines = open('filename','r').read().splitlines()

Pointers

Pointers are essential to any C developper. There are no pointers in Python, but there are mutable objects and we can more or less simulate the mechanism.

In the following, seed_to_soil and soil_to_fertilizer are lists. I use tags as a pointer to the right list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def get_maps(lines: list[str]):
    array = []
    tags = { 'seed-to-soil' : seed_to_soil,
             'soil-to-fertilizer' : soil_to_fertilizer,
             'fertilizer-to-water' : fertilizer_to_water,
             'water-to-light' : water_to_light,
             'light-to-temperature' : light_to_temperature,
             'temperature-to-humidity' : temperature_to_humidity,
             'humidity-to-location' : humidity_to_location }

	...
    array = tags[k]

Unpacking operators

Functions such as math.lcm use a variable number of arguments:

1
2

def lcm(*integers):
	...

If we have a list of integers to provide, we can use the unpacking operator *: math.lcm(*tab). Actually, * works over any iterable object (even for example on strings themselves).

If you want a variable number of named arguments, use the unpacking operator **. This create a dict that the function iterates over.

More on Real Python

Zip

Good article from RealPython

zip takes one or multiple iterables as input. It returns a sequence of tuples with one element of each iterable.

This is quite useful in Day 14 to convert a matrix organized by lines, into a matrix of columns.

1
2
3
4
5

>>> matrix = [ 'ABCDE', 'FGHIJ', 'KLMNO' ]
>>> list(zip(*matrix))
[('A', 'F', 'K'), ('B', 'G', 'L'), ('C', 'H', 'M'), ('D', 'I', 'N'), ('E', 'J', 'O')]
>>> list(map(''.join, list(zip(*matrix))))
['AFK', 'BGL', 'CHM', 'DIN', 'EJO']

Note that zip works without issue on iterables of different lengths. It will operate till the smallest iterable.

As mentioned in Real Python, zip is also particularly interesting when you want to loop over several iterables:

1
2
3
4
5

>>> letters = ['a', 'b', 'c']
>>> numbers = [0, 1, 2]
>>> for l, n in zip(letters, numbers):
...     print(f'Letter: {l}')
...     print(f'Number: {n}')

Other good example in Real Python, using zip to unzip with the unpacking operator:

1
2
3
4
5
6

>>> pairs = [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]
>>> numbers, letters = zip(*pairs)
>>> numbers
(1, 2, 3, 4)
>>> letters
('a', 'b', 'c', 'd')

Note that it’s possible to zip iterables of different lengths.

Underscore

There are more uses of underscore that I had ever imagined.

Basically, in [dict() for _ in range(256)] the underscore acts as an “unnamed” variable.

It can also used to ignore values:

1
2

a, _, b = (1,2,3)
a, *_,b = (1,2,3,4)

Misc

• Read a string right to left: reversed(s)
• Is a digit: isdigit()
• Sum all elements of a list: sum(thelist)
• Lambda functions
• To compute combinations, use from itertools import combinations
• Python 3.8 introduced := which “assigns values as part of a larger expression”. In the following, n gets the value of len(a).

1
2

if (n := len(a)) > 10:
    print(f"List is too long ({n} elements, expected <= 10)")

Elegant solutions (SPOILER ALERT)

Those are solutions I found on Internet. Not mine

C

I solved a few challenges using plain C (day 5, day 6, day 7 for instance). If you’re not going to use some Python specificities, C does the work very well… and fast.

Performance

Python is way slower than C. That’s a fact. For example, this is the performance for similar implementations of Day 5 Task 2. The same with Python simply would not finish in a reasonable time.

However… it depends very much on the algorithm you choose and your implementation skills…

In Python, if a given function is called many times with the same arguments, it’s a good idea to memoize it to speed up the result. This can be done with from functools import cache and the @cache decorator.

For example, this Day 12 solution caches the recurse function. Beware, caching works with simple types, it won’t work with lists.

1
2
3
4
5

from functools import cache

@cache
def recurse(lava, springs, result=0):
...

Also, if you’re using recursivity intensively, you might need the optimization of sys.setrecursionlimit(number) - but that might not solve all your performance issues ;)