The Right Lang for the Job

Exploring the abbyss of non-mainstream programming languages

Advent of Code 2023 - Day 2

Just Part 1, since I'm late to the party again today...


1. Part 1

Here's the link to the exercise - as usual, we get some input data, and need to read it and check some of the properties. In this case, the question is as follows:

Determine which games would have been possible if the bag had been loaded with only 12 red cubes, 13 green cubes, and 14 blue cubes.

Okay - before we start, let's import the libraries we'll need. Strictly speaking, none if these are actually needed - you can see other implementations that don't use anything outside of subr and simple - but I want to showcase the tools modern Elisper has at their disposal.

1: (require 'b)
2: (require 'cl-lib)
3: (require 'map)
4: (require 'dash)  

With that out of the way, we can take a stab at the task. First, let's assume we have the input in a buffer already, in input.txt. You could implement the task by imperatively traversing the buffer, which would be very Emacs-y way of doing this, but since there's an implementation like that already, I'll go for a more Python-like approach and split the input into a list of lines:

5: (defconst aoc-games-played-input
6:   (-> "input.txt" get-buffer b-string-no-properties s-trim s-lines))

We now have 100 lines of text, ready to be further processed:

(length aoc-games-played-input)

Here's how the lines look like:

(-take 2 aoc-games-played-input)
("Game 1: 12 blue, 15 red, 2 green; 17 red, 8 green, 5 blue; 8 red, 17 blue; 9 green, 1 blue, 4 red"
 "Game 2: 6 red, 6 blue, 2 green; 1 blue, 1 red; 6 green, 1 red, 10 blue")

We need to verify that on each line all the "subsets" - separated by semicolons - have color values that do not exceed the limits quoted at the beginning. First, let's further split the lines into chunks, separating game ID from subsets, and then further separating subsets from each other:

(let ((line (car aoc-games-played-input)))
      ((`(,game ,subsets) (s-split (rx ": ") line))
       (subset-list (s-split (rx "; ") subsets))
       (subsets (--map (s-split (rx ", ") it) subset-list)))
     (cl-second (s-match (rx "Game " (group (1+ num))) game))
("1" ("12 blue" "15 red" "2 green") ("17 red" "8 green" "5 blue")
 ("8 red" "17 blue") ("9 green" "1 blue" "4 red"))

It works, so let's refactor it a bit before moving on. As we're doing the refactor, we can also convert strings to numbers and symbols as appropriate, and subsets into alists:

 7: (cl-defun get-game-id (game-name)
 8:   (let ((re (rx "Game " (group (1+ num)))))
 9:     (->> game-name (s-match re) cl-second string-to-number)))
11: (cl-defun subset->alist (colors)
12:   (cl-loop for color in colors
13:            for (num color) = (s-split (rx " ") color)
14:            collect (cons (intern-soft color) (string-to-number num))))
16: (cl-defun line->game (line)
17:   (pcase-let* ((`(,game ,subsets) (s-split (rx ": ") line))
18:                (subset-list (s-split (rx "; ") subsets))
19:                (subsets (--map (s-split (rx ", ") it) subset-list)))
20:     (cons
21:      (get-game-id game)
22:      (-map #'subset->alist subsets)))  )
24: (let ((line (car aoc-games-played-input)))
25:   (line->game line))
(1 ((blue . 12) (red . 15) (green . 2)) ((red . 17) (green . 8) (blue . 5))
   ((red . 8) (blue . 17)) ((green . 9) (blue . 1) (red . 4)))

So we have the data in a form that's convenient to work with. Now, what does it mean for a game to be possible? All subsets must have color values within a limit. Let's define a function for checking this:

26: (defconst limits '((red . 12) (green . 13) (blue . 14)))
28: (cl-defun game-possible-p (game)
29:   (cl-loop for subset in (cdr game)
30:            unless (cl-loop for (color . limit) in limits
31:                            always (<= (map-elt subset color 0) limit))
32:            return nil
33:            finally return t))
35: (defconst line-impossible
36:   "Game 1: 12 blue, 15 red, 2 green; 17 red, 8 green, 5 blue; 8 red, 17 blue; 9 green, 1 blue, 4 red")
37: (defconst line-possible
38:   "Game 2: 6 red, 6 blue, 2 green; 1 blue, 1 red; 6 green, 1 red, 10 blue")
40: (list (game-possible-p (line->game line-possible))
41:       (game-possible-p (line->game line-impossible)))
(t nil)

The predicate seems to be working. The two things left to do are to filter out the games for which the predicate returns t and then sum the game IDs of those games:

42: (cl-loop for line in aoc-games-played-input
43:          for game = (line->game line)
44:          if (game-possible-p game)
45:          sum (car game))

And that's, according to the AoC page, the correct answer for my dataset, for part 1!

2. Part 2

For completeness sake, here's the answer to the second part of the puzzle. Here, we need to find the maximum values for each color across all subsets of a given game:

46: (defconst maxes '((red . 0) (green . 0) (blue . 0)))
48: (cl-macrolet
49:     ((alist-maximize (key acc alist)
50:        `(setf (alist-get ,key ,acc)
51:               (max (alist-get ,key ,acc) (alist-get ,key ,alist 0)))))
52:   (cl-loop for line in aoc-games-played-input
53:            for game = (line->game line)
54:            sum (cl-loop with maxs = (copy-tree maxes)
55:                         for x in (cdr game)
56:                         do (progn
57:                              (alist-maximize 'red maxs x)  
58:                              (alist-maximize 'green maxs x)
59:                              (alist-maximize 'blue maxs x) )
60:                         finally return (apply #'* (map-values maxs)))))

The result happens to be correct for my dataset, here too.

The main highlight here is the cl-macrolet form, which defines local macros, valid only in the lexical scope of the form. It's great for getting syntactic clutter out of the way without polluting the global namespace.

A honorary mention goes to setf - a versatile tool for updating contents of things. There are many "things" that you can set/update, and you can your own "places" and have setf work with them, too. The selling point of setf is the symmetry: most often, the "place" has the same syntactic form as the getter for a given thing. Here, alist-get is used with setf to update a value in an alist - it's way cleaner than assoc and setcdr to which it expands to.

Notice also the copy-tree - it's important because of the mutability of Elisp's lists. It's obvious now when the alist is defined outside of the function, but the call to copy-tree would be needed even if the variable was inlined! That is, this:

(cl-loop with maxs = '((red . 0) (green . 0) (blue . 0)) ...)

Would still produce wrong output. An alternative to copy-tree would be constructing the list at runtime by calling list and cons functions. I'll leave the detail as to why this happens for a future post.