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.

• Czeslaw Milosz, Ars Poetica

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:

• the shape and volume of runtime data as well as the course it takes through the program

• the performance characteristics of the application as it executes on physical hardware

• the domain knowledge and engineering constraints that influenced design decisions

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
• Part 1: Fuel for Modules

Time:   0.001ms  Memory:       0kb  Answer:  3282935

• Part 2: Fuel for Fuel

Time:   0.005ms  Memory:       0kb  Answer:  4921542

##### 2020 Day 01: Report Repair
• Part 1: Fix the Expense Report

Time:   0.030ms  Memory:       0kb  Answer:  910539

• Part 2: Now in triplicate

Time:   0.333ms  Memory:       0kb  Answer:  116724144

##### 2020 Day 02: Password Philosophy
• Part 1: Count valid passwords

Time:   0.561ms  Memory:     383kb  Answer:  456

• Part 2: Count using XOR

Time:   0.070ms  Memory:       0kb  Answer:  308

##### 2020 Day 03: Toboggan Trajectory
• Part 1: Count tree collisions

Time:   0.014ms  Memory:       0kb  Answer:  274

• Part 2: Count multiple slopes

Time:   0.059ms  Memory:       0kb  Answer:  6050183040

##### 2020 Day 04: Passport Processing

Time:   0.301ms  Memory:      32kb  Answer:  256

• Part 2: Validate fields

Time:   0.477ms  Memory:      32kb  Answer:  199

##### 2020 Day 05: Binary Boarding
• Part 1: Binary Seat Encoding

Time:   0.218ms  Memory:      63kb  Answer:  880

• Part 2: Find the unoccupied seat

Time:   0.284ms  Memory:     156kb  Answer:  731

##### 2020 Day 06: Custom Customs
• Part 1: Count any yes answers

Time:   0.434ms  Memory:      96kb  Answer:  6726

• Part 2: Count all yes answers

Time:   0.312ms  Memory:     128kb  Answer:  3316

##### 2020 Day 07: Handy Haversacks
• Part 1: How many bags can contain a shiny gold bag?

Time:   4.151ms  Memory:   1,332kb  Answer:  151

• Part 2: How many bags does a shiny gold bag hold?

Time:   0.965ms  Memory:     571kb  Answer:  41559

##### 2020 Day 08: Handheld Halt
• Part 1: Find the bootloader error

Time:   0.222ms  Memory:       0kb  Answer:  1801

• Part 2: Fix the bootloader error

Time:   8.780ms  Memory:   7,055kb  Answer:  2060

##### 2020 Day 09: Encoding Error
• Part 1: Find vulnerable number

Time: 272.417ms  Memory: 156,419kb  Answer:  3199139634

• Part 2: Break the encryption

Time: 1010.555ms  Memory: 372,596kb  Answer:  438559930

##### 2021 Day 01: Sonar Sweep
• Part 1: Into the Depths

Time:   0.012ms  Memory:       0kb  Answer:  1266

• Part 2: De-noising the Depths

Time:   0.008ms  Memory:       0kb  Answer:  1217

##### 2021 Day 02: Dive!
• Part 1: Plotting the Course

Time:   0.010ms  Memory:       0kb  Answer:  2117664

• Part 2: One Does Not Simply Dive

Time:   0.011ms  Memory:       0kb  Answer:  2073416724

##### 2021 Day 03: Binary Diagnostic
• Part 1: Check the Power Consumption

Time:   0.163ms  Memory:       0kb  Answer:  3923414

• Part 2: Verify Life Support

Time:   0.167ms  Memory:      32kb  Answer:  5852595

##### 2021 Day 04: Giant Squid
• Part 1: Bingo Subsystem

Time:   2.664ms  Memory:   2,944kb  Answer:  50008

• Part 2: Let the Squid Win

Time:  15.285ms  Memory:   8,000kb  Answer:  9280

##### 2021 Day 05: Hydrothermal Venture
• Part 1: Overlapping Vents

Time:  17.414ms  Memory:  19,428kb  Answer:  4655

• Part 2: Diagonal Overlap

Time:  64.128ms  Memory:  37,894kb  Answer:  20500

##### 2021 Day 06: Lanternfish
• Part 1: That's a big school

Time:   0.015ms  Memory:       0kb  Answer:  360761

• Part 2: Uh Oh

Time:   0.034ms  Memory:       0kb  Answer:  1632779838045

##### 2021 Day 07: The Treachery of Whales
• Part 1: Do the Crab Claw

Time:   0.012ms  Memory:       0kb  Answer:  356922

• Part 2: Crabs Engineer Different

Time:   0.032ms  Memory:       0kb  Answer:  100347031

##### 2021 Day 08: Seven Segment Search
• Part 1: Count the Easy Ones

Time:   0.025ms  Memory:       0kb  Answer:  493

• Part 2: Decode the Outputs

Time:   2.003ms  Memory:     223kb  Answer:  1010460

##### 2021 Day 09: Smoke Basin
• Part 1: Follow the Smoke

Time:   2.625ms  Memory:   1,759kb  Answer:  436

• Part 2: Dodge the Basins

Time:  42.374ms  Memory:  17,718kb  Answer:  1317792

##### 2021 Day 10: Syntax Scoring
• Part 1:

Time:   0.542ms  Memory:      96kb  Answer:  392421

• Part 2:

Time:   0.544ms  Memory:     160kb  Answer:  2769449099

##### 2021 Day 11: Dumbo Octopuses
• Part 1:

Time:   4.085ms  Memory:     863kb  Answer:  1673

• Part 2:

Time:   8.759ms  Memory:   2,240kb  Answer:  279


### 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:

• SBCL seems to generate tighter assembly for truncate than floor in many cases.

• Factoring out fuel-for as a separate helper and adding type and optimize declarations there keeps the rest of the code clean and gets us the speed benefits of typing in LOOP, etc.

(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

### 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.

• ORDER BOARDS

• ORDER BOARDS

• COUNTS

• COUNTS DAYS

### 6.7 The Treachery of Whales

#### 6.7.1 Do the Crab Claw

• POSITIONS COST-FUNCTION TARGET

• POSITION I

### 6.8 Seven Segment Search

#### 6.8.1 Count the Easy Ones

• ENTRIES &AUX (UNIQUE-LENGTHS (QUOTE (2 3 4 7)))