advent-of-code

This is the code and documentation for my [[https://adventofcode.com/][Advent of Code]] adventures. Thanks for taking a look! I welcome your thoughts and feedback.

• Advent of Code 2020

• Advent of Code 2019

Santa is stranded at the edge of the Solar System and it's up to me to save Christmas using quick thinking and the power of the [[https://crystal-lang.org][Crystal programming language]]. I've been slowly learning Crystal for a while & am feeling ready to use it to tackle some actual challenges and build proficiency.

For each day, I plan to build or extend a well-behaved CLI tool that allows me to solve the puzzle using a Bash one-liner. I'm challenging myself to follow a set of priorities that align with how I want to write code:

*** Do:

• utilize a pure functional style
• use immutable, persistent data structures
• write readable, semantically meaningful code
• provide a well-behaved command line interface

*** Don't:

• rely on global or mutable state
• switch back arbitrarily to imperative style
• optimize prematurely
• obsess over minimal (or even DRY) code

** Day 1 I wrote the rocket-fuel utility to calculate fuel requirements.

• implementation: [[./2019/rocket-fuel/rocket-fuel.cr]]
• build: make bin/rocket-fuel
• solve part 1: bin/rocket-fuel data/day-1/puzzle-input.mod
• solve part 2: bin/rocket-fuel -x data/day-1/puzzle-input.mod

** Day 2 On the second day of Christmas begins the saga of the /intcode computer!/

• implementation: [[./2019/src/computer/computer.cr]]
• build: make bin/computer
• solve part 1: #+BEGIN_SRC bash bin/computer run -s 1,12 -s 2,2 data/day-2/puzzle-input.ic
  | head -n1
  | cut -d' ' -f1 #+END_SRC
• solve part 2: #+BEGIN_SRC bash bin/computer search --domain 0,99
  --target 19690720
  data/day-2/puzzle-input.ic #+END_SRC

** Day 3 This challenge required calculating the location of intersections and the lengths of paths. I wrote the trace-wires utility to assist.

• implementation: [[./2019/src/trace-wires/trace-wires.cr]]
• build: make bin/trace-wires
• solve part 1: bin/trace-wires nearest-intersection data/day-3/puzzle-input.wire
• solve part 2: bin/trace-wires nearest-intersection data/day-3/puzzle-input.wire

** Day 4 Elves vaguely remember an important password & it's time to crack it using the password utility.

• implementation: [[./2019/src/password/password.cr]]
• build: make bin/password
• solve part 1: bin/password [PUZZLE INPUT MIN] [MAX]
• solve part 2: bin/password --cap-run-length [PUZZLE INPUT MIN] [MAX]

** Day 5 Intcode Part 2: Thermoelectric Boogaloo. This challenge prompted me to refactor computer.cr, eliminating a number of previous simplifying assumptions. Then I added the new functions necessary to solve the puzzle.

• implementation: [[./2019/src/computer/computer.cr]]
• build: make bin/computer
• solve part 1: bin/computer run -q data/day-5/puzzle-input.ic <<<1
• solve part 2: bin/computer run -q data/day-5/puzzle-input.ic <<<5

** Day 6 In order to plot an orbital path to Santa, we stop by a mapping station to process some maps with the orbit utility.

• implementation: [[./2019/src/orbit/orbit.cr]]
• build: make bin/orbit
• solve part 1: bin/orbit sum data/day-6/puzzle-input.map
• solve part 2: bin/orbit path-distance data/day-6/puzzle-input.map

** Day 7 This challenge involves running an intcode program in many configurations, with chained inputs & outputs, in order to find the maximum possible output of a series. I believe I could have done this in bash without any changes to the computer utility, using standard UNIX pipes to handle I/O. Maybe I should have done that, because it would have reduced I/O complexity in the computer program itself.

However, after all this time using functional Crystal & persistent data structures, I've been itching for an opportunity to leverage parallelism, and I figured this optimization problem could be a nail for that hammer if you look at it funny.

To warm-up, since I've never used Crystal's parallel features before & they're in preview anyhow, I updated my day 2 "search" solution to use multiple threads. Et voila, it ran ~4 times as fast on my 4-core machine. Now we're living the dream!!

As a fortunate side-effect of refactoring the solution to run in parallel, implementing part 2 was a minor change: add a new --loop option to the CLI, loop the I/O structures, and wait for all the IC programs to terminate before reading the final output.

• implementation: mostly in [[./2019/src/computer/main.cr]], but with some added facilities for choosing whether to use stdin/stdout or internal data structures for I/O.
• build: make bin/computer
• solve part 1: bin/computer optimize --domain 0,4 data/day-7/puzzle-input.ic
• solve part 2: bin/computer optimize --domain 5,9 --loop data/day-7/puzzle-input.ic

** Day 8 This challenge lent itself to a satisfyingly compact representation in Crystal. I also found out that the "colorize" module is cute and easy to use.

• implementation: [[./2019/src/image/image.cr]]
• build: make bin/image
• solve part 1: bin/image check -d 25x6 data/day-8/puzzle-input.sif
• solve part 2: bin/image show -d 25x6 data/day-8/puzzle-input.sif

** Day 9 To solve this puzzle, we need a "complete" intcode computer. This requires satisfying a few new operational constraints & adding a new opcode and instruction mode.

To satisfy the requirement that intcode computers handle "big numbers," I switched from using Int32 for values throughout the codebase to using BigInts. This required a decent number of changes throughout the codebase, but that process highlighted for me how Crystal's compiler and type checker make refactoring less risky.

To satisfy the requirement that programs be allowed to write outside of the initial program memory, I segmented the program space into two parts: data, the initial program memory, and extra, a map of memory addresses to values. This allows us to set a value at some far-out address without having to allocate a ton of memory, which is nice.

It's interesting to note during part 2, where the performance of the intcode computer is stress-tested, that release builds are /much/ faster than dev builds. To test this yourself, time it with each build instruction below.

On my computer, this results in a 4x speedup, resulting in a speedy sub-second runtime. (=t_d / t_r * 100 where t_r is release runtime and t_d is dev runtime)

I haven't been profiling or optimizing much beyond gut-level instincts, so it's possible I may be missing something that would actually speed up execution again dramatically.

• implementation: [[./2019/src/computer/computer.cr]]
• dev build: make bin/computer
• release build: crystal build --release -o bin/computer computer/main.cr
• solve part 1: bin/computer run -q data/day-9/puzzle-input.ic <<<1
• solve part 2: bin/computer run -q data/day-9/puzzle-input.ic <<<2

** Day 10 In order to help distressed elves in an asteroid field I built the asteroid tool which can optimize for the best asteroid surveillance location and calculate the order in which asteroids will be vaporized by a laser beam. It does all this with vector math. I didn't look very hard for a vector library in Crystal's shards collection, but I didn't see anything obvious so I wrote my own with enough functionality to solve this puzzle.

• implementation: [[./2019/src/asteroid/asteroid.cr]]
• build: make bin/asteroid
• solve part 1: bin/asteroid optimize data/day-10/puzzle-input.map
• solve part 2: #+BEGIN_SRC shell bin/asteroid optimize -c $center
  --number 200
  data/day-10/puzzle-input.map #+END_SRC (where $center is the output from part 1, in my case "29,28")