Advent of Code 2023 (50/50 ✨)
Languages: 6 (21 × Python, 1 × fish, 1 × Clojure, 1 × DDP, 1 × Zig, 4 × Vim)
- ⭐⭐ Python
- throwing unit tests against functions until stuff works out…
- efficient, but complicated range based solution for part 2 📏
- ⭐⭐ Zig
- took a long time to fix a memory leak
- Zig is not for the faint of heart 🫨
- ⭐⭐ Python
- half smart, half brute force is the real Joker 🃏
- ⭐⭐ Python
- haunted solution, LCM works for some reason
- ⭐⭐ Python
- easy and straightforward
- ⭐⭐ Python
- pretty lengthy, but it prints some nice Unicode visualization
- ⭐⭐ Python
- space math
- ⭐⭐ Python
- part 1: initially brute force generating valid patterns (with some optimizations)
- part 2: complete rewrite: recursive count of valid patterns with memoization (took some inspiration for this…) 🤯
- ⭐⭐ Python
- part 1: just iterating over 2D arrays and comparing strings
- part 2: brute forcing over the patterns with one entry swapped at each position until a new row or column is found
- notable Python tricks:
list(zip(*arr))transposes an array, so that columns can be treated as rows- a
forloop can have anelseblock – this can be used tobreakan outer loop
- ⭐⭐ Python
- part 1: moving stuff around in arrays (rotating a 2D array helps so that only one direction has to be implemented - shifting east is easiest, as we can go line by line and within a line from left to right)
- part 2: finding cycles and not messing up modulo calculations
- ⭐⭐ Python
- straightforward coding, one of the easiest days so far
- ⭐⭐ Python
- part 1: BFS (queue work list + visited set)
- part 2: brute-force of part 1 with all starting positions (not that many, run-time is around 1.5 sec)
- ⭐⭐ terminal visualization using curses
char.translate(char.maketrans("RLUD", "→←↑↓")is a neat trick
- ⭐⭐ Python
- part 1: Dijkstra with priority queue (
heapq); the tricky part is to include both direction and steps already taken in that direction into the queue and seen set - part 2: making max steps configurable and adding a min steps in same
direction was easy, but everything broke because I started with a single
entry in the queue with a fake direction of
(0, 0), which messed up the minimum step count; solved by adding the start twice, with right and down directions ((0, 1)and(1, 0))
- ⭐⭐ Python
- part 1: initially solved with a flood fill, but…
- part 2: … is way to big for a flood fill, so I had to look up some math:
- the shoelace formula is a simple and fast way to calculate the area of a polygon (Mathologer has a very nice video about this)
- with the area and the number of border points (from part 1), we can derive the number of inner points via Pick's theorem
- ⭐⭐ Python
- part 1 went pretty well; putting the input into some proper data structures and then iterating over the parts and traversing the workflow graph with each of them
- part 2 was brutal - hardest day for me so far; since it took me a while, I added a write-up of my final algorithm
- ⭐⭐ Python
- part 1: implementing the modules and their behavior/states, then simulating the whole thing
- part 2: the solution is based on an observation about the structure of
the machine; with this known, cycle lengths of sub-machines can be found,
and the final result is the LCM of all cycle lengths; see the lengthy
comments of
find_circle_outputs()andpart2()for details
- ⭐⭐ Python
- part 1: BFS on grid
- part 2: crazy calculations based on a diamond shape, took a very long time to get right; source has some lengthy comments including a lot of ASCII art drawings of the shapes
- ⭐⭐ Python
- initially I tried a clever way to determine if a brick can be
disintegrated, but there is some bug that I cannot find - the function
can_be_disintegrated()(still commented out in the code) detects more bricks as disintegratable than it should - after a lot of debugging, I gave up and re-used the
drop()function; calling that on sets of bricks with one brick removed and checking the bricks that fell takes a good amount of time, but gives the data that is needed for both part 1 and part 2 - the excessive debugging at least produced some nice 3D plots created with Matplotlib (see day 22 README)
- ⭐⭐ Python
- part 1: DFS; to get the different paths, the partial paths are stored
the work queue, and used to re-initialize the visited set after a complete
path has been found
- built some nice terminal visualization
- part 2: complete rewrite, as brute forcing all paths was no longer possible; took some inspiration on how to solve this; the idea is to build a graph that connects start, end, and all crossing points; edges of the graphs are calculated by traveling the actual maze; an edge may not travel through another node; eventually we have a graph where the edges are annotated with the path distances between the nodes; to find the longest total distance, there is no better way than to try all possible paths (done via recursive DFS); my input had 36 nodes and 120 edges for part 2; calculation takes about 8 seconds
- ⭐⭐ Python
- part 1: implementing some geometry, perfectly test-driven by the elaborate examples; learned about homogeneous coordinates
- part 2: solved with Z3
- ⭐⭐ Python
- part 1: did a lot of reading on graph theory, and my conclusion was that
we can find a solution based on max flows, which eventually turned out to
be right; no further spoilers here, those are in the
day 25 README
- used NetworkX for the graph stuff, which felt a bit like cheating, but understanding the problem and picking the right algorithms was a challenge in itself; also, using NetworkX for the first time was interesting, it's a cool library to have in the toolbox
- part 2: n/a (auto-win with all other stars)