As usual I’m doing these problems well after the festive season. My friend Screwtape is a lisp enthusiast and I’ve been curious in the past about lisp but never got around to picking it up, so I’m going to use it a bit this time.
Part 1 was pretty easy despite my very limited knowledge of lisp: just scan each line and populate each of two initially nil variables, etc.
When I first started doing Advent of Code puzzles I would copy my program from the first part of each day and modify it but at some point I decided to start extending each program to output both answers. Since then I’ve mostly been using rust for these and it doesn’t really lend itself to object-oriented approaches but I ended up using common lisp’s object system to manage the differences between each part.
The second part involves recognising English words for the numbers from one to nine. I did this by scanning each line character by character and maintaining a list of numbers that I might have seen part of. There are a finite number of states which that list can be in and presumably my program would have run faster if I’d numbered each state and made a transition graph but I didn’t think that optimisation would be worthwhile for a program that already runs to completion before I can percieve time passing.
The code for my solution is here
The puzzle input this time has a more complex grammar than I’m used to seeing in Advent of Code. Although iterating over all the individual characters in a string is no problem, it seems the Common Lisp Hyperspec doesn’t define a few things that would be very useful here; such as a function for splitting a string into words, or a function for checking whether or not a character is whitespace.
Since a tokenizer would need a function to test for whitespace that
seemed like an obvious place to start. In other projects I’ve used the
isSpace
function but that’s not available because I’m not using Haskell this
time. However, I did end up using it indirectly.
First I wrote my first non-trivial lisp macro, which generates an expression for checking whether or not a sortable object is within a given set of ranges.
(defmacro check-ranges (qe &rest bounds)
(let ((qry (gensym)) (last-bound nil) (in-range nil) (node-stack nil))
(dolist (bound bounds)
(if (and node-stack in-range (eq bound last-bound)
(not (eq nil last-bound)))
(progn
(setf in-range nil)
(setf (car node-stack) `(if (= ,qry ,bound) t nil)))
(let ((new-node
(if in-range
`(if (<= ,qry ,bound)
t
nil)
`(if (< ,qry ,bound)
nil
t))))
(setf last-bound bound)
(push new-node node-stack)
(setf in-range (not in-range)))))
(let ((node nil))
(loop for new-node = (pop node-stack)
while new-node
do (setf node
(if node
(append
(subseq new-node 0 3)
(list node)
(subseq new-node 4))
new-node)))
`(let ((,qry ,qe))
,node))))This took me a while because when building the nodes into a “tree”
for some reason it would create a cyclic data structure. I’m still not
sure what was going on: I’ve tried to get a minimal example of the
behaviour I was seeing but it just behaved as I would have expected in
the first place. The fix was to use append to build a new
top node at each iteration rather than setf to add a branch
to the node about to become the new top node. So the problem was
something to do with referential transparency or rather lisp’s
lack thereof.
The next part is where Haskell comes in: I use it to generate a call to the above macro.
import Data.Char (isSpace)
import Data.List (intercalate)
collectRanges :: (Enum a, Eq a) => [a] -> [(a, a)]
collectRanges [] = []
collectRanges (a':r') = go (a', a') r' where
go p [] = [p]
go p@(l, h) r'@(a:r)
| a == succ h = go (l, a) r
| otherwise = p : collectRanges r'
makeCall :: Show a => String -> [(a, a)] -> String
makeCall form ranges = "(check-ranges " ++ form ++ " " ++
intercalate " " (do
~(l, h) <- ranges
x <- [l, h]
return $ show x
) ++ ")"
main = putStrLn $
makeCall "(char-code the-char)" $
collectRanges $
map fromEnum $
filter isSpace [minBound .. maxBound]And the result is…
(check-ranges (char-code the-char) 9 13 32 32 160 160 5760 5760 8192 8202 8239 8239 8287 8287 12288 12288)Side note: Pandoc’s syntax highlighting (used here) is better than nothing but has definite room for improvement, especially compared to tree-sitter.
As it turns out while this was a great learning experience it wasn’t a great use of time in terms of solving the puzzle. The expression generated by the macro is still smaller than the macro itself, and I’d forgotten I’ll only actually need to use it once because common lisp actually does have the standard function alphanumericp.
With the tokenizer done the parser was pretty straightforward and the solution for part 1 was trivial.
When doing part 1 I’d noticed that it wasn’t necessary for the parser to distinguish between the ‘,’ and ‘;’ characters to solve the problem, and I could have just kept the highest number for each colour and discarded the rest. I just used the whole parse tree anyway because I thought there was a reasonable chance that part 2 would use the additional degree of structure but just storing the highest number for each colour would have still been sufficient. Actually; refactoring my program from part 1 to do that first makes part 2 a simpler problem.
The code for my solution is here