Intro

aoc-utils is a collection of various helper functions I usually use for solving Advent of Code (AoC) tasks.

Highlights

• Read the contents of an input file with read-input. This is usually just (aoc/read-input 1), and if you need to read the file containing test input, e.g. 01_test.txt then use (aoc/read-input "01_test")
• The input file usually contains multiple lines of data, which are parsed with the parse-lines function. For the details on how to parse different datatypes, see below. To parse a single-line input, parse-input can be used.
• A frequent task type is the one where we have a 2D-grid. For converting the input to a datatype that can be easily used as a grid, see the create-grid function. There are also some helpers to manipulate 2D points, pt+, pt-, pt*, and their 3D equivalents (pt-3d+, etc.).
• Early tasks often need to apply a function on each row and then take a sum of the results. We can use sum-map for that.
• Some tasks are graph traversal problems, and for those there are four options: dfs, bfs, a-star, dijkstra. These try to be as general as possible to fit different tasks, but they are not as performant as a specialized function for a given task.

In short, one of the early tasks might look like this:

(->> (aoc/parse-lines (aoc/read-input 1) row-parsing-function)
     (aoc/sum-map row-function)

 

Reading input files

The read-input function has the folowing assumptions:

• inputs are in the sibling ../inputs directory
• inputs have .txt extension
• if passing a single digit as a parameter, it zero-pads it

E.g. (read-input 1) slurps ../inputs/01.txt file.

Input parsing

The aoc/parse-input function is doing some heavy lifting.
The parse-fn parameter there is the key to the versatility: it makes possible to parse all AoC inputs, either by the typical functions (see the list below) or by passing it a custom function, specially crafted for the task at hand.

Possible “built-ins” to pass to the parse-fn parameter:

• :int - parse a single integer
• :ints- get all integers
• :digits - extract all single digits
• :chars - make a list of chars
• :words - make a list of words

This function is usually used on single-line inputs.

---

Parsing a whole multi-line input file is just a matter of applying that function to each line of the input, and there is aoc/parse-lines that does exactly that.

On some rare occasions, the input is split into paragraphs by having an empty line between different parts of input. We have a function for that too: aoc/parse-paragraphs.

Grids

AoC wouldn’t be AoC if there aren’t many tasks where you’re given a 2D grid (sometimes even 3D).
It is important to have a usable representation of a grid.

If a grid is dense, e.g. we want to keep all points in a grid, it is the best to keep it as a 2D vector of characters. We can use the grid-get function to get a character at y-row, x-col.

If a grid is sparse, e.g. we only need to know positions of walls and/or several other characters, we can create a hashmap representation of a grid with the create-grid function.

Sometimes we need to inspect a grid. With the show-grid function, we create a printable string of all points in the grid.

---

2D grids

Here are some functions that help us with points in 2D grids:

• manhattan
• pt+
• pt-
• pt*
• left-turn
• right-turn
• inside?
• neighbours-4
• neighbours-8

3D grids

For 3D grids, we have variants of the functions above:

• manhattan-3d
• pt-3d+
• pt-3d-
• pt-3d*
• inside-3d?
• neighbours-3d

Graph traversal

Graph traversal problems are relatively frequent in AoC.

I’ve written a huge general function for traversing grids, but it remains to be seen how useful it’ll be for specific tasks with their specific needs: I feel like in the recent years the graph traversal tasks always had some gotcha which made it harder to use a general algorithm, rather than a specific one written for the task at hand.

If this gets used, the implementation details will probably change, depending on the specific tasks. As if the traverse function is not already way too long and complicated.

All four algorithms (DFS, BFS, Dijkstra, A*) share the same logic, the difference is in a queue type. They can be passed as a first argument to the traverse function, and they are also available as separate functions:

• dfs
• bfs
• dijkstra
• a-star

The list of possible keys passed in the options map is quite large:

[start end walls size size-x size-y
 nb-func nb-num nb-cond end-cond
 cost-fn heuristic steps-limit
 allow-revisits? side-effect]

It’s best to read the function’s source code to understand what each does.

Utilities

Functions for some common AoC stuff.

• transpose: We often need to iterate through columns, instead of rows. This transposes the matrix.
• count-if: In many tasks we need to apply some condition and then count the number of elements which satisfy it. This should be slightly faster (to type, at least) than (count (filter ...)).
• sum-map: Similarly, in some tasks we need to map a function to each element, and then take a sum of the results. There are also sum-map-indexed, sum-pmap, prod-map, max-map and max-pmap variants.
• find-first: Returns the first element which satisfies a predicate. It should be slightly faster than using (some ...).
• gcd: Greatest common divisor.
• lcm: Least common multiple.
• sign: Sign of a number.
• none?: A faster version of not-any?.