Advent of Code 2022 part 1

Advent of Code 2022 is here! This year I’m revisiting Common Lisp, which I’ve done a few problems in over the years, but for an extra twist, I’ll be doing most of the logic, when reasonable, in APL, using the April package. I’ve never used APL before, although I have toyed with other array languages, including doing a number of solutions for AoC 2019 in kdb+/q. My solutions are on GitHub, and I’ll document some of my thoughts here and in follow-up posts.

Resources

Here’s some of the resources I’ve been using to help learn CL and APL:

• On Lisp by Paul Graham
• Loving Common Lisp by Mark Watson
• TryAPL
• MicroAPL documentation
• gnu-apl-mode and its keyboard layout:
• The Array Cast (especially listen to Andrew Sengul, creator of April, in Episode 23)

Environment

I started preparing after Thanksgiving by setting up my development environment, which is just Emacs and SBCL, using quicklisp for package management. I’ve used emacs for years, but since I’ve used Vim even longer, I’ve always used evil mode, most recently as part of the doom emacs framework, but I’ve never been terribly happy with evil with any of the lisp modes (clojure, racket, emacs, common), so I’m making my life even more difficult by learning vanilla emacs key bindings, with a “lighter” configuration via prelude (I’ve tried rolling my own emacs config before, just not for me - I’d rather get to coding).

In order to set up my development environment on my NixOS machine, without installing anything in the global enviornment, I’m setting up a environment following Jason Miller’s nix-lisp-dev setup. This also lets me experiment with the emacs config withought affecting my main doom config, which I still need to keep being productive for my day job.

Library

I started by writing a helper package, which can directly download and do basic parsing of AoC input, based on the advent-of-code-data clojure library and some of my clojure helper functions. I just manually load it into my SBCL REPL for the time being.

Day 1

I solved this first with a straighforward pure common lisp solution (well, with a heavy use of the loop sub-language).

(defun calories-per-elf (stream)
  (loop with total = 0
        for line = (read-line stream nil)
        until (null line)
        when (= (length line) 0)
          collect total
          and do (setq total 0)
        else
          do (setq total (+ total (parse-integer line)))))

(defun max-calories (stream)
  (apply 'max (calories-per-elf stream)))

(defun part1 ()
  (with-input-stream (in 2022 1)
    (max-calories in)))

(defun top3 (ns)
  (let ((sorted (sort ns '>)))
    (list (car sorted) (cadr sorted) (caddr sorted))))

(defun part2 ()
  (with-input-stream (in 2022 1)
    (reduce '+ (top3 (calories-per-elf  in)))))

Note the use of the with-input-stream function from my aoc library, which fetches and caches my input for the given year and day (with a session key tucked in a config file or env var). It’s a huge timesaver when working on these. Next maybe it would be nice to be able to scrape example inputs, maybe just grab any <code> blocks on the problem page?

My place on my local leaderboards now secure, I could tackle the problem in APL. It’s a bit of a challenge since I didn’t do much learning beforehand, but I’m familiar enough with array concepts from my time with q that it’s mostly a matter of scanning through the references to find the function or operator I need (which I then need to find on the keyboard map…).

My own input and learning difficulties aside, my initial impression of working with April is a bit mixed: I really like being able to handle input and parsing in common lisp, but miss the interactive REPL experience when working on the APL code, instead needing to work on and then run the full APL block every time. I’ve been doing some interactive playing in TryAPL, but don’t have the data there so it’s more just testing concepts there.

You can see some of the iterative steps I took in the full source code, here’s the final solution that emits the answers to both parts (with the APL separated for code highlighting):

(defun apl ()
  (april-f (with (:state
                  :in ((in (input-as-ints 2022 1 :as 'vector :blanks-as 0)))
                  :out (ans1 ans2))) "

cals ← +/ ¨ (in≠0) ⊆ in
ans1 ← ⌈/ cals
ans2 ← +/ cals[3 ↑ (⍒ cals)]

"))

It’s really impressive how terse and yet expressive APL can be. I’ll try to walk through this (as much to help myself in five years when I look back and forgot everything about APL), using the example input from the problem descriptions.

For part 1 we’re given as input a list of all the food items the elves are carrying, grouped by elf, and asked to find the maximum total calories carried by any elf.

1. In the common lisp code, we get the problem input as a vector of integers, with the blank lines represented as zeroes; this goes into the APL code as the in variable. #(1000 2000 3000 0 4000 0 5000 6000 0 7000 8000 9000 0 10000)
2. (in≠0) ⊆ in: this partitions the input into sub-arrays . We do this by creating a filter array (in≠0) with 1s for all entries and 0s in between, and feed this to the partition function ⊆, which works a bit of magic with this and the input. #(#(1000 2000 3000) #(4000) #(5000 6000) #(7000 8000 9000) #(10000))
3. We then compute the sum for each elf via reduce +/ over each of ¨ the sub-arrays. #(6000 4000 11000 24000 10000)
4. For part 1 then we just need the max ⌈ of all / the elves. 24000

For part 2 we’re asked instead to find the sum of the top three total calories by the elves.

1. We start with the array of total calories per elf cals from step 3 above. We sort it descending (⍒ cals) (which actually gives the indices to the sorted values) and then take the first three 3 ↑. #(4 3 5)
2. We then grab the values for those indices from the cals array cals[...] and sum them +/. 45000

Easy, right? Let’s see how this looks in 24 days…