Advent Of Code 2025 starts in a few hours. Time to practice your Lisp-fu to solve it with the greatest language of all times this year!
Most of the times, puzzles start with a string input we have to parse to a meaningful data structure, after which we can start working on the algorithm. For example, parse this:
(defparameter *input* "3 4
4 3
2 5
1 3
3 9
3 3")
into a list of list of integers, or this:
(defparameter *input* "....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...")
into a grid, a map. But how do you represent it, how to do it efficiently, what are the traps to avoid, are there some nice tricks to know? We’ll try together.
You’ll find those 3 exercises of increasing order also in the GitHub repository of my course (see my previous post on the new data structures chapter).
I give you fully-annotated puzzles and code layout. You’ll have to carefully read the instructions, think about how you would solve it yourself, read my proposals, and fill-in the blanks -or do it all by yourself. Then, you’ll have to check your solution with your own puzzle input you have to grab from AOC’s website!
Table of Contents
- Prerequisites
- Exercise 1 - lists of lists
- Exercise 2 - prepare to parse a grid as a hash-table
- Harder puzzle - hash-tables, grid, coordinates
- Closing words
Prerequisites
You must know the basics, but not so much. And if you are an
experienced Lisp developer, you can still find new constraints for
this year: solve it with loop, without loop, with a
purely-functional data structure library such as FSet, use Coalton, create
animations, use the object system, etc.
If you are starting out, you must know at least:
- the basic data structures (lists and their limitations, arrays and vectors, hash-tables, sets…)
- iteration (iterating over a list, arrays and hash-table keys)
- functions
no need of macros, CLOS or thorough error handling (it’s not about production-grade puzzles :p ).
Exercise 1 - lists of lists
This exercise comes from Advent Of Code 2024, day 01: https://adventofcode.com/2024/day/1
Read the puzzle there! Try with your own input data!
Here are the shortened instructions.
;;;
;;; ********************************************************************
;;; WARN: this exercise migth be hard if you don't know about functions.
;;; ********************************************************************
;;;
;;; you can come back to it later.
;;; But, you can have a look, explore and get something out of it.
In this exercise, we use:
;;; SORT
;;; ABS
;;; FIRST, SECOND
;;; EQUAL
;;; LOOP, MAPCAR, REDUCE to iterate and act on lists.
;;; REMOVE-IF
;;; PARSE-INTEGER
;;; UIOP (built-in) and a couple string-related functions
;;;
;;; and also:
;;; feature flags
;;; ERROR
;;;
;;; we don't rely on https://github.com/vindarel/cl-str/
;;; (nor on cl-ppcre https://common-lisp-libraries.readthedocs.io/cl-ppcre/)
;;; but it would make our life easier.
;;;
OK, so this is your puzzle input, a string representing two colums of integers.
(defparameter *input* "3 4
4 3
2 5
1 3
3 9
3 3")
We’ll need to parse this string into two lists of integers.
If you want to do it yourself, take the time you need! If you’re new to Lisp iteration and data structures, I give you a possible solution.
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;; [hiding in case you want to do it…]
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
(defun split-lines (s)
"Split the string S by newlines.
Return: a list of strings."
;; If you already quickloaded the STR library, see:
;; (str:lines s)
;;
;; UIOP comes with ASDF which comes with your implementation.
;; https://asdf.common-lisp.dev/uiop.html
;;
;; #\ is a built-in reader-macro to write a character by name.
(uiop:split-string s :separator '(#\Newline)))
Compile the function and try it on the REPL, or with a quick test expression below a “feature flag”.
We get a result like '("3 4" "4 3" "2 5" "1 3" "3 9" "3 3"), that is a list of strings with numbers inside.
#+lets-try-it-out
;; This is a feature-flag that looks into this keyword in the top-level *features* list.
;; The expression below should be highlihgted in grey
;; because :lets-try-it-out doesn't exist in your *features* list.
;;
;; You can compile this with C-c C-c
;; Nothing should happen.
(assert (equal '("3 4" "4 3" "2 5" "1 3" "3 9" "3 3")
(split-lines *input*)))
;; ^^ you can put the cursor here and eval the expression with C-x C-e, or send it to the REPL with C-c C-j.
We now have to extract the integers inside each string.
To do this I’ll use a utility function.
;; We could inline it.
;; But, measure before trying any speed improvement.
(defun blank-string-p (s)
"S is a blank string (no content)."
;; the -p is for "predicate" (returns nil or t (or a truthy value)), it's a convention.
;;
;; We already have str:blankp in STR,
;; and we wouldn't need this function if we used str:words.
(equal "" s)) ;; better: pair with string-trim.
#+(or)
(blank-string-p nil)
#++
(blank-string-p 42)
#+(or)
(blank-string-p "")
And another one, to split by spaces:
(defun split-words (s)
"Split the string S by spaces and only return non-blank results.
Example:
(split-words \"3 4\")
=> (\"3\" \"4\")
"
;; If you quickloaded the STR library, see:
;; (str:words s)
;; which actually uses cl-ppcre under the hood to split by the \\s+ regexp,
;; and ignore consecutive whitespaces like this.
;;
(let ((strings (uiop:split-string s :separator '(#\Space))))
(remove-if #'blank-string-p strings)))
#+lets-try-it-out
;; test this however you like.
(split-words "3 4")
I said we wouldn’t use a third-party library for this first puzzle. But using cl-ppcre would be so much easier:
(ppcre:all-matches-as-strings "\\d+" "3 6")
;; => ("3" "6")
With our building blocks, this is how I would parse our input string into a list of list of integers.
We loop on input lines and use the built-in function parse-integer.
(defun parse-input (input)
"Parse the multi-line INPUT into a list of two lists of integers."
;; loop! I like loop.
;; We see everything about loop in the iteration chapter.
;;
;; Here, we see one way to iterate over lists:
;; loop for … in …
;;
;; Oh, you can rewrite it in a more functional style if you want.
(loop :for line :in (split-lines input)
:for words := (split-words line)
:collect (parse-integer (first words)) :into col1
:collect (parse-integer (second words)) :into col2
:finally (return (list col1 col2))))
#+lets-try-it-out
(parse-input *input*)
;; ((3 4 2 1 3 3) (4 3 5 3 9 3))
The puzzle continues.
“Maybe the lists are only off by a small amount! To find out, pair up the numbers and measure how far apart they are. Pair up the smallest number in the left list with the smallest number in the right list, then the second-smallest left number with the second-smallest right number, and so on.”
=> we need to SORT the columns by ascending order.;;;
“Within each pair, figure out how far apart the two numbers are;”
=> we need to compute their relative, absolute distance.
“you’ll need to add up all of those distances.”
=> we need to sum each relative distance.
“For example, if you pair up a 3 from the left list with a 7 from the right list, the distance apart is 4; if you pair up a 9 with a 3, the distance apart is 6.”
Our input data’s sum of the distances is 11.
We must sort our lists of numbers. Here’s a placeholder function:
(defun sort-columns (list-of-lists)
"Accept a list of two lists.
Sort each list in ascending order.
Return a list of two lists, each sorted."
;; no mystery, use the SORT function.
(error "not implemented"))
;; Use this to check your SORT-COLUMNS function.
;; You can write this in a proper test function if you want.
#+lets-try-it-out
(assert (equal (sort-columns (parse-input *input*))
'((1 2 3 3 3 4) (3 3 3 4 5 9))))
Compute the absolute distance.
;; utility function.
(defun distance (a b)
"The distance between a and b.
Doesn't matter if a < b or b < a."
;;
;; hint: (abs -1) is 1
;;
(error "not implemented")
)
(defun distances (list-of-lists)
"From a list of two lists, compute the absolute distance between each point.
Return a list of integers."
(error "not implemented")
;; hint:
;; (mapcar #'TODO (first list-of-lists) (second list-of-lists))
;;
;; mapcar is a functional-y way to iterate over lists.
)
(defun sum-distances (list-of-integers)
"Add the numbers in this list together."
(error "not implemented")
;; Hint:
;; try apply, funcall, mapcar, reduce.
;; (TODO #'+ list-of-integers)
;; or loop … sum !
)
Verify.
(defun solve (&optional (input *input*))
;; let it flow:
(sum-distances (distances (sort-columns (parse-input input)))))
#+lets-try-it-out
(assert (equal 11 (solve)))
All good? There’s more if you want.
;;;
;;; Next:
;;; - do it with your own input data!
;;; - do the same with the STR library and/or CL-PPCRE.
;;; - write a top-level instructions that calls our "main" function so that you can call this file as a script from the command line, with sbcl --load AOC-2024-day01.lisp
;;;
Exercise 2 - prepare to parse a grid as a hash-table
This exercise is a short and easy, to prepare you for a harder puzzle. This is not an AOC puzzle itself.
Follow the instructions. We are only warming up.
;; Do this with only CL built-ins,
;; or with the dict notation from Serapeum,
;; or with something else,
;; or all three one after the other.
We will build up a grid stored in a hash-table to represent a map like this:
"....#...##....#"
where the # character represents an obstacle.
In our case the grid is in 1D, it is often rather 2D.
This grid/map is the base of many AOC puzzles.
Take a second: shall we represent a 2D grid as a list of lists, or something else, (it depends on the input size) and how would you do in both cases?
Your turn:
;;
;; 1. Define a function MAKE-GRID that returns an empty grid (hash-table).
;;
(defun make-grid ()
;; todo
)
;;
;; Define a top-level parameter to represent a grid that defaults to an empty grid.
;;
;; def… *grid* …
;;
;; 2. Create a function named CELL that returns a hash-table with those keys:
;; :char -> holds the character of the grid at this coordinate.
;; :visited or :visited-p or even :visited? -> stores a boolean,
;; to tell us if this cell was already visited (by a person walking in the map). It defaults
;; to NIL, we don't use this yet.
;;
(defun cell (char &key visited)
;; todo
)
;;
;; 3. Write a function to tell us if a cell is an obstacle,
;; denoted by the #\# character
;;
(defun is-block (cell)
"This cell is a block, an obstacle. Return: boolean."
;; todo
;; get the :char key,
;; check it equals the #\# char.
;; Accept a cell as NIL.
)
We built utility functions we’ll likely re-use on a more complex puzzle.
Let’s continue with parsing the input to represent a grid.
If you are a Lisp beginner or only saw the data structures chapter in
my course, I give you the layout of the parse-input function with a
loop and you only have to fill-in one blank.
In any case, try yourself. Refer to the Cookbook for loop
examples.
;;
;; 4. Fill the grid (with devel data).
;;
;; Iterate on a given string (the puzzle input),
;; create the grid,
;; keep track of the X coordinate,
;; for each character in the input create a cell,
;; associate the coordinate to this cell in the grid.
;;
(defparameter *input* ".....#..#.##...#........##...")
(defun parse-grid (input)
"Parse a string of input, fill a new grid with a coordinate number -> a cell (hash-table).
Return: our new grid."
(loop :for char :across input
:with grid := (make-grid)
:for x :from 0
:for cell := (cell char)
:do
;; associate our grid at the X coordinate
;; with our new cell.
;; (setf … )
:finally (return grid)))
;; try it:
#++
(parse-grid *input*)
That’s only a simple example of the map mechanism that comes regurlarly in AOC.
Here’s the 3rd exercise that uses all of this.
Harder puzzle - hash-tables, grid, coordinates
This exercise comes from Advent Of Code 2024, day 06. https://adventofcode.com/2024/day/6 It’s an opportunity to use hash-tables.
Read the puzzle there! Try with your own input data!
Here are the shortened instructions.
The solutions are in another file, on my GitHub repository.
;;;
;;; ********************************************************************
;;; WARN: this exercise migth be hard if you don't know about functions.
;;; ********************************************************************
;;;
;;; you can come back to it later.
;;; But, you can have a look, explore and get something out of it.
In this exercise, we use:
;;;
;;; parameters
;;; functions
;;; recursivity
;;; &aux in a lambda list
;;; CASE
;;; return-from
;;; &key arguments
;;; complex numbers
;;; hash-tables
;;; the DICT notation (though optional)
;;; LOOPing on a list and on strings
;;; equality for characters
For this puzzle, we make our life easier and we’ use the DICT notation.
(import 'serapeum:dict)
If you know how to create a package, go for it.
Please, quickload the STR library for this puzzle.
#++
(ql:quickload "str")
;; Otherwise, see this as another exercise to rewrite the functions we use.
This is your puzzle input:
;;; a string representing a grid, a map.
(defparameter *input* "....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...")
;; the # represents an obstacle,
;; the ^ represents a guard that walks to the top of the grid.
When the guard encounters an obstacle, it turns 90 degrees right, and keeps walking.
Our task is to count the number of distinct positions the guard will visit on the grid before eventually leaving the area.
We will have to: - parse the grid into a data structure - preferably, an efficient data structures to hold coordinates. Indeed, AOC real inputs are large. - for each cell, note if it’s an obstacle, if that’s where the guard is, if the cell was already visited, - count the number of visited cells.
;; We'll represent a cell "object" by a hash-table.
;; With Serapeum's dict:
(defun cell (char &key guard visited)
(dict :char char
:guard guard
:visited visited))
;; Our grid is a dict too.
;; We create a top-level variable, mainly for devel purposes.
(defvar *grid* (dict)
"A hash-table to represent our grid. Associates a coordinate (complex number which represents the X and Y axis in the same number) to a cell (another hash-table).")
;; You could use a DEFPARAMETER, like I did initially. But then, a C-c C-k (recompile current file) will erase its current value, and you might want or not want this.
For each coordinate, we associate a cell.
What is a coordinate? We use a trick we saw in other people’s AOC solution, to use a complex number. Indeed, with its real and imaginary parts, it can represent both the X axis and the Y axis at the same time in the same number.
#|
;; Practice complex numbers:
(complex 1)
;; => 1
(complex 1 1)
;; => represented #C(1 1)
;; Get the imaginary part (let's say, the Y axis):
(imagpart #C(1 1))
;; the real part (X axis):
(realpart #C(1 1))
|#
Look, we are tempted to go full object-oriented and represent a “coordinate” object, a “cell” object and whatnot, but it’s OK we can solve the puzzle with usual data structures.
;; Let's remember where our guard is.
(defvar *guard* nil
"The guard coordinate. Mainly for devel purposes (IIRC).")
Task 1: parse the grid string.
We must parse the string to a hash-table of coordinates -> cells.
I’ll write the main loop for you. If you feel ready, take a go at it.
(defun parse-grid (input)
"Parse INPUT (string) to a hash-table of coordinates -> cells."
;; We start by iterating on each line.
(loop :for line :in (str:lines input)
;; start another variable that tracks our loop iteration.
;; It it incremented by 1 at each loop by default.
:for y :from 0 ;; up and down on the map, imagpart of our coordinate number.
;; The loop syntax with … = … creates a variable at the first iteration,
;; not at every iteration.
:with grid = (dict)
;; Now iterate on each line's character.
;; A string is an array of characters,
;; so we use ACROSS to iterate on it. We use IN to iterate on lists.
;;
;; The Iterate library has the generic :in-sequence clause if that's your thing (with a speed penalty).
:do (loop :for char :across line
:for x :from 0 ;; left to right on the map, realpart of our coordinate.
:for key := (complex x y)
;; Create a new cell at each character.
:for cell := (cell char)
;; Is this cell the guard at the start position?
:when (equal char #\^)
:do (progn
;; Here, use SETF on GETHASH
;; to set the :guard keyword of the cell to True.
(print "we saw the guard")
;; (setf (gethash … …) …)
;; For devel purposes, we will also keep track of
;; where our guard is with a top-level parameter.
(setf *guard* key)
)
:do
;; Normal case:
;; use SETF on GETHAH
;; to associate this KEY to this CELL in our GRID.
(format t "todo: save the cell ~S in the grid" cell)
)
:finally (return grid))
)
;; devel: test and bind a top-level param for ease of debugging/instropection/poking around.
#++
(setf *grid* (parse-grid *input*))
Task 2: walk our guard, record visited cells.
We have to move our guard on the grid, until it exits it.
I’ll give you a couple utility functions.
(defun is-block (cell)
"Is this cell an obstacle?"
;; accept a NIL, we'll stop the walk in the next iteration.
(when cell
(equal TODO #\#)))
;; We choose the write the 4 possible directions as :up :down :right :left.
;; See also:
;; exhaustiveness checking at compile-time:
;; https://dev.to/vindarel/compile-time-exhaustiveness-checking-in-common-lisp-with-serapeum-5c5i
(defun next-x (position direction)
"From a position (complex number) and a direction, compute the next X."
(case direction
(:up (realpart position))
(:down (realpart position))
(:right (1+ (realpart position)))
(:left (1- (realpart position)))))
(defun next-y (position direction)
"From a position (complex number) and a direction, compute the next Y."
(case direction
(:up (1- (imagpart position)))
(:down (1+ (imagpart position)))
(:right (imagpart position))
(:left (imagpart position))))
This is the “big” function that moves the guard, records were it went, makes it rotate if it is against a block, and iterates, until the guard goes out of the map.
Read the puzzle instructions carefuly and write the “TODO” placeholders.
(defun walk (&key (grid *grid*) (input *input*)
(position *guard*)
(cell (gethash *guard* *grid*)) ;; todo: *grid* is used here. Fix it so we don't use a top-level variable, but only the grid given as a key argument.
(direction :up)
(count 0)
;; &aux notation: it saves a nested of LET bindings.
;; It's old style.
;; Those are not arguments to the function we pass around,
;; they are bindings inside the function body.
&aux next-cell
next-position
obstacle-coming)
"Recursively move the guard and annotate cells of our grid,
count the number of visited cells."
;; At each iteration, we study a new cell we take on our grid.
;; If we move the guard to a coordinate that doesn't exist in our grid,
;; we stop here.
(unless cell
(return-from walk count))
;; Look in the same direction first and see what we have.
(setf next-position
(complex (next-x position direction) (next-y position direction)))
(setf next-cell (gethash next-position grid))
;; obstacle?
(setf obstacle-coming (is-block next-cell))
;; then change direction.
(when obstacle-coming
(setf direction
(case direction
(:up :right)
(:down :left)
(:right :down)
(:left :up))))
;; Count unique visited cells.
;; TODO
(unless (print "if this CELL is visited...")
(incf count)
;; TODO set this cell as visited.
(print "set this CELL to visited")
)
;; get our next position now.
(setf next-position
(complex (next-x position direction) (next-y position direction)))
;; This next cell may or may not be in our grid (NIL).
(setf next-cell (gethash next-position grid))
(walk :grid grid :input input
:cell next-cell
:position next-position
:direction direction
:count count))
and that’s how we solve the puzzle:
(defun part-1 (input)
(walk :grid (parse-grid input)))
#++
(part-1 *input*)
;; 41
;; The right answer for this input.
;; In AOC, you have a bigger, custom puzzle input. This can lead to surprises.
Closing words
Look at other people’s solutions too. For example, ak-coram’s for our last exercise (using FSet). See how Screamer is used for day 06 by bo-tato (reddit). atgreen (ocicl, cl-tuition, cffi…) solution with a grid as a hash-table with complex numbers. lispm’s day 04 solution. Can you read all solutions?
On other days, I used:
- alexandria’s
map-permutationsfor day 08 when you want… permutations. It doesn’t “cons” (what does that mean you ask? You didn’t follow my course ;) ). Read here: https://dev.to/vindarel/advent-of-code-alexandrias-map-permutations-was-perfect-for-day-08-common-lisp-tip-16il. - the library fare-memoization, to help in a recursive solution.
- to write math, use cmu-infix. When you spot 2 equations with 2 unknows, think “Cramer system”. This came up last year, so maybe not this year.
- with very large numbers: use double floats, as in
1.24d0 - least common multiple?
lcmis a built-in. - str:match can be a thing to parse strings.
- if you got CIEL (CIEL Is an Extended Lisp), you have Alexandria, cl-str, Serapeum:dict and more libraries baked-in. It’s also an easy way to run Lisp scripts (with these dependencies) from the shell.
See you and happy lisping!
Your best resources:
