→ ↺ λ

Advent of Code

Table of Contents

← ↑ → ↺ λ

1 Links

Here is the github repo and here is the website.

← ↑ → ↺ λ

2 Background

I have always aspired to a more spacious form
that would be free from the claims of poetry or prose
and would let us understand each other without exposing
the author or reader to sublime agonies.

What do we want from a program? For a long time, I have wondered what it would mean to have truly readable programs. I agree with Peter Seibel that code is not literature and yet, I cannot help but imagine a world where software supports our understanding.

Source code, like language, is a weak medium for humans. Many of the things we care about cannot be captured in source code:

Automated testing can capture some small fragments of these details but too much is left to us to reconstruct using our imagination and experience. This is a large part of why gaining comfort with a new codebase doesn't come from passive reading but active rewriting.

I continue to believe that the best way to combat these limitations comes from live environments that allow runtime inspection of in-memory structures and support for inspecting, redefining, and migrating both code and data in a live environment. I also recognize that, unlike the fantasies of my youth, most people have no interest in looking under the hood at how a program functions or how the machine carries out its tasks. And industry will continue moving away from systems that are entirely comprehensible by a single individual.

This program won't overcome these limitations in understanding. It will not reveal all its contextual mysteries and the baggage of its creation to those who read it or run it. But I enjoy programming most when it is a creative writing exercise. So I will try to make this program open to exploration, document a little of what I understand, and show some compassion for myself and you, dear reader.

← ↑ → ↺ λ

3 Current Progress

I do not hold myself to completing every exercise and oscillate between striving for a concise or clever implementation versus an optimized one. Still, it's useful to have an overview of what code has been written and how it performs so I will add that here.

← ↑ → ↺ λ

3.1 Overview

2019 Day 01: The Tyranny of the Rocket Equation
2020 Day 01: Report Repair
2020 Day 02: Password Philosophy
2020 Day 03: Toboggan Trajectory
2020 Day 04: Passport Processing
2020 Day 05: Binary Boarding
2020 Day 06: Custom Customs
2020 Day 07: Handy Haversacks
2020 Day 08: Handheld Halt
2020 Day 09: Encoding Error
2021 Day 01: Sonar Sweep
2021 Day 02: Dive!
2021 Day 03: Binary Diagnostic
2021 Day 04: Giant Squid
2021 Day 05: Hydrothermal Venture
2021 Day 06: Lanternfish
2021 Day 07: The Treachery of Whales
2021 Day 08: Seven Segment Search
2021 Day 09: Smoke Basin
2021 Day 10: Syntax Scoring
2021 Day 11: Dumbo Octopuses

← ↑ → ↺ λ

4 Advent 2019

← ↑ → ↺ λ

4.1 The Tyranny of the Rocket Equation

← ↑ → ↺ λ

4.1.1 Fuel for Modules

Part 1 is just a simple summation problem. We need to compute the total fuel requirements based on a list of masses provided. To make things a little interesting I wrote three variations, one with REDUCE, one with DOLIST, and one with LOOP. The different versions were almost equivalent, taking ~10k CPU cycles and executing in a handful of microseconds. I added a type declaration to the LOOP version for giggles and saw a ~50% speedup which is reflected in the disassembly being a tighter 124 bytes compared to 276 bytes for the DOLIST version and 371 bytes for the functional version.

(let ((data (read-day-input #'parse-integer)))
  (time (fuel-requirements-3 data)))

;; Evaluation took:
;;   0.000 seconds of real time
;;   0.000002 seconds of total run time (0.000002 user, 0.000000 system)
;;   100.00% CPU
;;   4,426 processor cycles
;;   0 bytes consed

← ↑ → ↺ λ

4.1.2 Fuel for Fuel

To extend the problem, we'll compute a fixed point for the fuel. Similar to the first part, I wrote a few different variations on this problem. The first was a classic tail recursive approach and the second used nested LOOPs.

Two interesting notes:

(let ((data (read-day-input #'parse-integer)))
  (time (total-fuel-needed-2 data)))

;; Evaluation took:
;;   0.000 seconds of real time
;;   0.000018 seconds of total run time (0.000017 user, 0.000001 system)
;;   100.00% CPU
;;   42,426 processor cycles
;;   0 bytes consed

← ↑ → ↺ λ

5 Advent 2020

← ↑ → ↺ λ

6 Advent 2021

← ↑ → ↺ λ

6.1 Sonar Sweep

← ↑ → ↺ λ

6.1.1 Into the Depths

For part 1, we'll just be checking how often a depth reading is increasing from the previous measurement. Pretty straightforward.

← ↑ → ↺ λ

6.1.2 De-noising the Depths

Part 2 extends our initial solution by averaging the depth readings in a sliding window three at a time. I'm still using a straightforward loop but the partitioning of the list is ugly. Two options for improvement are:

  1. Solve the problem in two passes, first generating sums then counting increases.

  2. Factor out the size of the window, either via callback or some other means.

Interesting notes after more experiments. I've tried a number of different approaches to this problem, some that are flexible enough to accommodate both parts of the puzzle and some that are specialized to the 3-element window of the second part.

Looking at the generic versions that can account for any input size we have 3 speed tiers:

  1. COUNT-DISPLACED-DEPTHS which is depressingly slow due to use of displaced arrays. Neat feature that they are, it seems displaced arrays are just plain slow. ~5x slower.

  2. COUNT-WINDOWED-DEPTHS which uses REDUCE and LOOP to compute the result. ~2.5x-3 slower.

  3. COUNT-INCREASING-SUMS-LOOP which is a direct translation of death's solution using DO. I often enjoy reviewing death's solutions as he tends to have different ideas than I do and I think he has good taste and knowledge of the language. I don't much like DO though.

It's worth pointing out that my COUNT-WINDOWED-DEPTHS is flexible enough to accept a list or array as an input. ...Though the performance degrades substantially from ~2.5x slower to 170x slower lol. This is due to repeated traversals of the input list by reduce.

Notably, it was much easier to write a version using lists instead of arrays that conses and uses 2 passes but because it is specialized on a 3-element version, it is just as fast as the fastest generic version. Granted, I haven't tried it on larger inputs. COUNT-AVERAGE-DEPTHS is clean and simple but I was curious if I could eliminate the consing and go faster. After some experimentation, I wound up with COUNT-SHIFTING-DEPTHS which is 4-5x faster than COUNT-INCREASING-SUMS-LOOP! Very interesting to see how much of a difference specializing makes in this case.

← ↑ → ↺ λ

6.2 Dive!

← ↑ → ↺ λ

6.2.1 Plotting the Course

← ↑ → ↺ λ

6.2.2 One Does Not Simply Dive

← ↑ → ↺ λ

6.3 Binary Diagnostic

← ↑ → ↺ λ

6.3.1 Check the Power Consumption

← ↑ → ↺ λ

6.3.2 Verify Life Support

← ↑ → ↺ λ

6.4 Giant Squid

← ↑ → ↺ λ

6.4.1 Bingo Subsystem

← ↑ → ↺ λ

6.4.2 Let the Squid Win

← ↑ → ↺ λ

6.5 Hydrothermal Venture

← ↑ → ↺ λ

6.5.1 Overlapping Vents

← ↑ → ↺ λ

6.5.2 Diagonal Overlap

← ↑ → ↺ λ

6.6 Lanternfish

← ↑ → ↺ λ

6.6.1 That's a big school

← ↑ → ↺ λ

6.6.2 Uh Oh

← ↑ → ↺ λ

6.7 The Treachery of Whales

← ↑ → ↺ λ

6.7.1 Do the Crab Claw

← ↑ → ↺ λ

6.7.2 Crabs Engineer Different

← ↑ → ↺ λ

6.8 Seven Segment Search

← ↑ → ↺ λ

6.8.1 Count the Easy Ones

← ↑ → ↺ λ

6.8.2 Decode the Outputs

← ↑ → ↺ λ

6.9 Smoke Basin

← ↑ → ↺ λ

6.9.1 Follow the Smoke

← ↑ → ↺ λ

6.9.2 Dodge the Basins

← ↑ → ↺ λ

6.10 Syntax Scoring

← ↑ → ↺ λ

6.10.1

← ↑ → ↺ λ

6.10.2

← ↑ → ↺ λ

6.11 Dumbo Octopuses

← ↑ → ↺ λ

6.11.1

← ↑ ↺ λ

6.11.2