I have officially spent too much time solving the Advent of code 2023 day 5 problem. I've solved it in 10 languages in a bunch of different ways. Functionally, with GPUs and CPU multiprocessing, being "smart" and just brute forcing the problem.

Here is what I've learned.

This challenge has been an ongoing thing for me for a few years. It's been a bit of a test-bed for me as it's a simple problem, but it complex enough that you can get your teeth into it and do things "properly". It's possible to solve in a single file (and yes I've been nasty and done that) but you can be nice and do it modularly with good unit tests and coverage. If you're into programming I'd encourage you to find a problem like this, or a set of problems that you can go back to. Low Level uses an HTTP server to act as his litmus test. So I'd recommend having 3, a very easy one (but harder than hello-world), a medium one to get used to package management / structure, and then a harder one if you really want to get your teeth into the language.

So, what is the problem....

The offical site page is here (official) or here.

The simple explanation is that you have an input value and a set of maps to transform it through to get an output.

|-------| | Input | |-------| | |---------| | Layer 1 | |---------| | ..... | |---------| | Layer 7 | |---------| | |---------| | Output | |---------|

Each layer consists of a set of maps which have a source a target and a size. If the value is between source and source + size, it translates to the corresponding place in target to target + size. If the value isn't in any of the maps then it passes through unchanged.

It's a pretty simple problem, nothing particularly complex but you do have to think about things.

Part A

In Part A of the problem you have a set of inputs 20 for the full data and 7 layers with about 250 maps in tota for the full dataset. The sample data has a much reduced set (4 inputs and about 30 maps).

There are 3 ways to look at the solutions to this: depth first, bredth first

Depth First

This is probably the simplest method. You have a minimum value, you run each value through the layers and check it against the minimum, if it's smaller, update and continue.

Bredth First

This is still pretty easy, you translate each value from the input set through the layers and at the end find the minimum.

This problem actually parallelises well, if you have a number of processors then each one can deal with a single value and then the array at the end picks the minimum.

Optimisations

One obvious optimisation is to flatten the layers into a single layer and translate the value through the single layer, this might be marginal but we'll talk about this in a minute.

Part B

Part B throws a spanner in the works. The simple input turns the simple set of values into a set of ranges with a start and a size.

E.g.

seeds: 28965817 302170009 1752849261 48290258 804904201 243492043 2150339939 385349830 1267802202 350474859 2566296746 17565716 3543571814 291402104 447111316 279196488 3227221259 47952959 1828835733 9607836

First range is: 28,965,817 to 331,135,826. This ends up with 1,975,502,102 values in total, that's a lot of values.

What took 0.035s for part A in python takes hours. So we start having problems. How do we solve it?

Profile your code to identify the bottleneck

Pretty much every language has tools to profile usage, if we're starting with Python we have cProfile. If we start with the day5_classes.py script.

``` python3 -m cProfile day5_classes.py ../../input_reduced_1M.txt part_b_forward

...

ncalls tottime percall cumtime percall filename:lineno(function) 7/1 0.000 0.000 62.958 62.958 {built-in method builtins.exec} 1 0.000 0.000 62.958 62.958 day5_classes.py:1() 1 0.442 0.442 62.951 62.951 day5_classes.py:474(part_b_forwards) 1000000 1.016 0.000 62.018 0.000 day5_classes.py:436(map_seed) 7000000 14.710 0.000 61.002 0.000 day5_classes.py:341(map_seed) 183000000 34.014 0.000 46.292 0.000 day5_classes.py:156(map_seed) 345000001 11.983 0.000 11.983 0.000 day5_classes.py:26(value) 1000001 0.304 0.000 0.352 0.000 day5_classes.py:128(next) 8000000 0.343 0.000 0.343 0.000 day5_classes.py:12(init) 1000000 0.137 0.000 0.137 0.000 day5_classes.py:46(lt) ```

Three calls stand out: day5_classes.py:341(map_seed), day5_classes.py:156(map_seed) and day5_classes.py:26(value)

For day5_classes.py:341(map_seed) def map_seed(self, seed: Seed): for mapping in self.__mappings: if result := mapping.map_seed(seed): return result return None

At a quick glance there isn't much we can do here.

For day5_classes.py:156(map_seed) def map_seed(self, seed: Seed): if (seed.value >= self.__src) and (seed.value <= self.__src + self.__size - 1): return Seed(self.__dest + (seed.value - self.__src)) return None

For day5_classes.py:26(value) it's a little more complex @property def value(self): return self.__value

This is a getter method for the Seed class which was an experiment in being overly object oriented. By removing this class and using just an integer we could speed up the code by about 20%.