# Advent of Code

## Table of Contents

- 1 Links
- 2 Background
- 3 Current Progress
- 4 Advent 2019
- 5 Advent 2020
- 6 Advent 2021

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

- 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

Part 1: Check required fields

`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 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 `LOOP`

s.

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

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

- [function] AOC.2021.01:COUNT-DEPTHS SONAR-READINGS

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

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

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:

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.

COUNT-WINDOWED-DEPTHS which uses

`REDUCE`

and`LOOP`

to compute the result. ~2.5x-3 slower.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.

- [function] AOC.2021.01:COUNT-AVERAGE-DEPTHS SONAR-READINGS

- [function] AOC.2021.01:COUNT-WINDOWED-DEPTHS READINGS WINDOW-SIZE

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

- [function] AOC.2021.04:PLAY-BINGO ORDER BOARDS

#### 6.4.2 Let the Squid Win

- [function] AOC.2021.04:PLAY-BINGO-FINAL ORDER BOARDS

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

- [function] AOC.2021.06:TICK COUNTS

#### 6.6.2 Uh Oh

- [function] AOC.2021.06:ESTIMATE-POPULATION COUNTS DAYS

### 6.7 The Treachery of Whales

#### 6.7.1 Do the Crab Claw

- [function] AOC.2021.07:ALIGN-CRABS POSITIONS COST-FUNCTION TARGET

#### 6.7.2 Crabs Engineer Different

- [function] AOC.2021.07:MIN-DISTANCE-GAUSS POSITION I

### 6.8 Seven Segment Search

#### 6.8.1 Count the Easy Ones

- [function] AOC.2021.08:COUNT-UNIQUE-DIGITS ENTRIES &AUX (UNIQUE-LENGTHS (QUOTE (2 3 4 7)))

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