18 Feb 2025
Planet Lisp
Joe Marshall: Advent of Code 2024: Day 7
You don't have to use named-lets for tail recursive loops. You can use them for any recursive function. Here is an example of a named let that computes the factorial of 5:
(let fact ((n 5)) (if (= n 0) 1 (* n (fact (- n 1)))))
Day 7 is an unremarkable puzzle. On each line of input we are given a target number and some terms. We work on the terms from left to right and we can add the next term or multiply by it. We are to sum the target numbers which can be identified as a result of some combination of adding and multiplying.
;;; -*- Lisp -*- (in-package "ADVENT2024/DAY7") (defun can-satisfy? (target ops terms) (let recur ((accum (first terms)) (terms (rest terms))) (cond ((and (> accum target) (not (find-if #'zerop terms))) nil) ((consp terms) (find-if (lambda (op) (recur (funcall op accum (first terms)) (rest terms))) ops)) ((null terms) (= target accum)) (t (error "Dotted list."))))) (defun parse-integer-list (str) (map 'list #'parse-integer (str:split #\Space str :omit-nulls t))) (defun parse-line (str) (let ((key+value (str:split #\: str))) (cons (parse-integer (first key+value)) (parse-integer-list (second key+value))))) (defun puzzle (ops) (collect-sum (let* ((equations (#Mparse-line (scan-file (input-pathname) #'read-line))) (satisfied (#M(lambda (equation) (can-satisfy? (car equation) ops (cdr equation))) equations))) (#Mcar (choose satisfied equations))))) (defun part-1 () (puzzle (list #'+ #'*)))
Part two allows us to concatenate the digits in addition to muliplying or adding.
(defun concatenate-digits (left right) (+ (* left (expt 10 (1+ (integer-log right 10)))) right)) (defun part-2 () (puzzle (list #'+ #'* #'concatenate-digits)))
18 Feb 2025 8:51am GMT
17 Feb 2025
Planet Lisp
vindarel: These years in Common Lisp: 2023-2024 in review
This is a personal pick of the most interesting projects, tools, libraries and articles that popped-up in Common Lisp land in the last two years.
Newcomers might not realize how the Common Lisp ecosystem, though stable in many ways, actually evolves, sharpens, tries new solutions, proposes new tools, ships new libraries, revives projects. And everyone might enjoy a refresher.
Here's my previous overview for 2022.
The same warnings hold: I picked the most important links, in my view, but this list is by no means a compilation of all new CL projects or articles published on the topic. Look for yourself on Reddit, Quicklisp releases, GitHub, and use your favourite search engine.
There are too many great news and achievements to pick 3. I love what's happening around SBCL (and ECL, and Clozure's revival), I love everything that got included into Lem and the work on all other editors, I love the webviews and I love the scripting tools that are emerging. What are your top picks?
OK, there's a news I want to put at the forefront: HackerNews now runs on top of SBCL ;)
If you are discovering the ecosystem, my recommendaton is to not miss these two resources:
- Awesome-cl - a curated list of libraries (there might be more than you think)
- if you are looking for a list of recommended libraries on each topic, look here.
- the CL Cookbook
Now let's dive in and thanks to everyone involved.
Table of Contents
- Community
- Documentation
- Implementations
- Companies and jobs
- Projects
- More libraries
- Other articles
- Videos
Community
We could start with some reddit stats: 2025 - a New Year for an old programming language! (numbers are up).
The ELS team kept organizing the conference. We have a date and place for 2025: European Lisp Symposium 2025 in Zürich, May 19⁄20
We saw new and regular Lisp Ireland meetups.
Here's one of their videos: Lisp Ireland, February 2024 Meetup - Lisp & Hardware Verification with ACL2
@djha-skin ran a survey, which is not an established practice in the community, and analysed the results: Common Lisp Community Survey 2024 Results .
@shinmera (Yukari), the author of many useful libraries and an active member of the ELS, and even the host of the next one, opened a Patreon. "If you'd like to help me continue my full-time open source Lisp work, please consider supporting me.". Sponsoring Yukari is money well spent. She is on GH sponsors and ko-fi too.
The community is on reddit, Discord, Mastodon, LinkedIn... and also on XMPP.
Documentation
The CL Cookbook is a collaborative resource with new contributors each year: new Cookbook EPUB and PDF release: 2025-01.
We got a great contribution: Cookbook: Building Dynamic Libraries with SBCL-Librarian · by em7
PAIP is a classic, now available on the web: Peter Norvig: Paradigms of Artificial Intelligence Programming, Case Studies in Common Lisp (web version).
New resource: Web Apps in Lisp: Know-how: I wanted a resource specialized for web development in Common Lisp. I mean to continuously extend it from now on.
I'll include a couple general videos in this section. More videos and more documentation improvements are to be found in their respective sections.
FreeCodeCamp released an extensive Common Lisp course on Youtube: Lisp Programming Language - Full Course for Beginners - freeCodeCamp.org - Youtube.
David Botton of CLOG fame released more beginner material, among which Common Lisp - The Tutorial - Fast, Fun and Practical (with CLOG).
I carry on the work on my Common Lisp course in videos, on the Udemy platform. Lately, I worked on a CLOS tutorial: I published 9 videos (1h 22min) on my course. You'll know enough to read the sources of Hunchentoot or the Kandria game 🎥 comments. The course is comprised of more than 7 hours of short videos, with a code first approach, divided in 9 chapters. We see some basics but we quickly dive into more advanced Common Lisp topics. You can learn more about it here on GitHub. Students can send me an email for a free link.
Here's the feedback of redditors:
I can vouch for the Udemy course. From the very first lesson, just firing up the REPL and Emacs/SLIME I was taught something new. It's a great course.
fuzzmonkey35, January 2025 (reddit)
It is an amazing tutorial. What is really strange is I thought CLOS was complicated. I guess it can be but Vincent is amazing at explaining everything and demystifying it.
intergallactic_llama, January 2025 (reddit)
;)
Implementations
Great times for Common Lisp implementations.
SBCL
SBCL ships monthly releases. You really should look at and appreciate all the activity and the continous improvements.
One noticeable addition: its new garbage collector. SBCL: merge of the mark-region GC.
More improvements include:
- "the mark-region parallel garbage collector can be enabled on arm64. (Thanks to Hayley Patton)",
- new contrib module sb-perf, "a performance-analysing tool for Linux. (thanks to Luke Gorrie and Philipp Marek)"
- support for cross-compiling the system to Android has been added (thanks to Gleefre)
- "support for memory allocation arenas is now available on the arm64 platform."
- haiku support
- sb-simd improvements
More good stuff with SBCL:
- Porting SBCL to the Nintendo Switch
- SBCL as part of an Android application!
- Simple REPL App. (SBCL, Android - WIP)
- 40ants/tree-shaker: experimental tree shaker for SBCL
- SBCL can now be installed on Windows via Chocolatey (unofficial)
- sbcl-builds: Nightly builds of SBCL for Windows using MSYS2 UCRT64.
- sbcl-goodies: distributing binaries with Common Lisp and foreign libraries. libssl, libcrypto and libfixposix are statically baked in.
There are open bounties to improve SBCL:
- $2000 USD bounty to see by-value struct passing implemented in SBCL's native FFI.
- it may be more than $2000 USD now.
- You wouldn't start from zero, there is existing work. See the thread.
- another $700+ bounty to add coroutines in SBCL
- same link. No official bounty page yet, I may work on it.
ABCL
New release ABCL 1.9.2.
New tool: Announcing the First Release of abcl-memory-compiler - Now Available!
CCL
Clozure was a bit active, but rather dormant.
Great news: Clozure is back
Allegro
Allegro Common Lisp 11.0 from Franz Inc.
LispWorks
I didn't spot a patch release (they had a major release in 2022), so let's link to a discussion: is LispWorks worth it? you might learn some things about LW's feature set.
ECL
Embeddable, targetting WASM... is it the future?
CLASP
CLASP targets C++ on LLVM.
They realeased Clasp v2.7.0 in January, 2025.
For context:
- Christian Schafmeister talk - brief update about his "molecular lego" supported by his Lisp compiler
- there's less funding than in the 80s for Common Lisp, but still funding: "CLASP was supported by The Defense Threat Reduction Agency, The National Institutes of Health, The National Science Foundation".
New implementations
- A Common Lisp implementation in development in C89 (no compiler so far)
- called ALisp, "breakpoints and stepping work quite well"
- gsou/LCL: Lua Common Lisp. An implementation of Common Lisp targeting Lua.
Historical: Medley Interlisp
We can run the Medley Interlisp Lisp machine in a browser O_o The work achieved by this group is phenomenal, look:
I suggest to follow @interlisp@fosstodon.org
on Mastodon.
Companies and jobs
Yes, some companies still choose Common Lisp today, and some hire with a public job posting.
It's of course the visible top of the iceberg. If you dream of a Lisp job, I suggest to be active and make yourself visible, you might be contacted by someone without a proper job announce. This could be for an open-source project with funding (happened to me), for a university, etc.
- a new product: Oracle Aconex Accelerator · "Over 5 years of development and scaling, the entire Conceptual AI linked data platform is built on Common Lisp (SBCL)."
- experience report: the World's Loudest Lisp Program to the Rescue, by Eugene Zaikonnikov
- job: Common Lisp Developer Job | Backend | Keepit | Kraków
- job: (same company, later) Common Lisp Developer job offer at Keepit
- job: Freelance job posting at Upwork for a Common Lisp Developer/Engineer.
- job: Lisp job: Cognitive Software Engineer - Chelmsford, MA, at Triton Systems
- job: implement the "Convex Hull Covering of Polygonal Scenes" paper.
- job: Senior Lisp Developer (m/f/d), Software & Applications at DXC Technology, work on SARA (SuperAgent Robotic Application), an automation tool designed to streamline complex and repetitive business processes for major airlines.
- job: senior Common Lisp Developer | 3E, Brussels
We knew these companies since awesome-lisp-companies -it's only a list of companies we know about, nothing offical. Additions welcome.
Discussions on the topic:
- Anyone using Common Lisp for freelance work? where we learn about cool websites made in CL and cool experience reports.
- Running my 4th Common Lisp script in production© - you can do it too aka "you don't need crazily difficult needs to make yourself a favour and use CL instead of Python in your projects"
Projects
Editors
Please check out the Cookbook: editors for a list of good editors for Common Lisp. You migth be surprised.
Let's highlight a new editor in town: Neomacs: Structural Lisp IDE/computing environment . Mariano integrated it in his moldable web desktop: Integrating Neomacs into my CLOG-powered desktop.
About Emacs
- slime 2.30 · Better I/O performance, macroexpand for macrolet (and more)- Better Common Lisp highlighting in Emacs
- Learning Lisp - making sense of xrefs in SLIME
About VSCode
About Lem and Rooms pair programming environment
- Lem 2.0.0 released
- released in May 2023, this version added the SDL2 frontend, adding mouse support, graphic capabilities, and Windows support.
- it brought the possibility to draw images and shapes at any location on a buffer or window.
- addition of many base16 color themes (180), by @lukpank.
- Lem 2.1.0 released, with many new contributors. Lem 2.0 definitely caught the eyes of many developers IMO.
- this is when Lem got its website: https://lem-project.github.io/
- @sasanidas worked on supporting other implementations: "ECL and CCL should work fairly well", "ABCL and Clasp are still work in progress, working but with minor bugs.".
- I added project-aware commands, find-file-recursively
- @cxxxr added (among everything else) great Lisp mode additions (just look at the release notes and the screenshots)
- added a sidebar / filer
- and much more. Just look at the release.
- then came out Lem 2.2.0
- the release notes are less organized ;)
- added libvterm integration
- this is when I added the interactive git mode.
Unfortunately these latest releases do not ship a readily usable executable. But the installation recipes have been greatly simplified and use Qlot instead of Roswell. There's a one-liner shell command to install Lem on Unixes.
Lem's creator cxxxr is now on GitHub sponsors.
He is also working on Rooms, aka Lem on the cloud: it's a Lem-based "pair programming environment where you can share your coding sessions". Only the client is open-source, so far at least.
Demo: https://www.youtube.com/watch?v=IMN7feOQOak
Those are the Lem related articles that popped up:
- Oh no, I started a Magit-like plugin for the Lem editor
- Lem customizable dashboard
- Lem has a subreddit
- Lem in CLIM "1.0" · now with mouse events and smoother performance. (August 2024)
- Lem on the cloud: Powerful web-based Editor with Collaborative Editing
About LispWorks
About the Jetbrains plugin
About Jupyter
Other tools
- CL-REPL now supports multiline editing
- it also comes as a ready-to-use binary
Coalton
I found Coalton-related projects:
- https://github.com/garlic0x1/coalton-threads
- https://github.com/garlic0x1/coalton-rope
- https://github.com/jbouwman/coalton-lsp
E. Fukamachi added Coalton support for Lem: https://lem-project.github.io/modes/coalton-lang/. This adds completion, syntax highlighting, interactive compilation and more inside "coalton-toplevel" forms.
Package managers
Quicklisp had a one year hiatus, because it relies on one man. It finally got an update after 1 year: Quicklisp libraries were updated 2024-10-12. Despite a call for collaboration, we don't really know how we can help.
But Quicklisp isn't the only library manager anymore.
- introducing ocicl: an experimental modern quicklisp alternative built on tools from the world of containers may 2023
- Ultralisp now supports any git repositories as project sources
- Qlot 1.4.1 - added script for manual installation without Roswell, "qlot install" runs in parallel
- Qlot 1.5.0 - added a REPL interface
- introducing vend: just vendor your dependencies
Also:
Gamedev
The Kandria game was released: https://kandria.com/
- Trial game engine documentation website and examples
- My Lisp physics engine for Trial is finally working!
If you are into game dev, this is a paper you cannot miss: Kandria: experience report, presented at the ELS 2023.
Great articles:
- Gamedev in Lisp. Part 1: ECS and Metalinguistic Abstraction
- Gamedev in Lisp. Part 2: Dungeons and Interfaces · Wiki · Andrew Kravchuk / cl-fast-ecs · GitLab
and more:
I almost forgot the Lisp Game Jams and the new cool little games. For example: Nano Towers
a simple tower defense game written in Common Lisp with the EON framework based on Raylib, submitted for the Spring Lisp Game Jam 2024.
Links to the jams:
GUI
Many solutions exist. Disclaimer: the perfect GUI library doesn't exist. Please see the Cookbook/gui and awesome-cl. Also don't miss the web views available today.
releases:
- McCLIM 0.9.8 Yule
- Shirakumo/glfw: An up-to-date Common Lisp bindings library to the most recent GLFW OpenGL context management library
- nodgui 0.4 released - multithread main loop, auto-completion entry, extended text widget, better image support
- nodgui v0.6.0 - Added an SDL frame as an alternative for TK canvas when fast rendering is needed. Both 2D (pixel based) and a 3D rendering (the latter using openGL) are available.
- Pretty GUIs now: nodgui comes with a pre-installed nice looking theme
As always, we might not highlight the work achieved on existing libraries that didn't get a proper announce. There are more GUI libraries for CL.
demos:
Web
CLOG appeared in 2022 and is kicking. Its API has been stable for 4 years.
You know Hacker News, the website, right? Hacker News now runs on top of SBCL
HN runs on top of Arc, the language. Arc was implemented on top of Racket (-> MzScheme). A new, faster / more efficient, implementation of Arc in SBCL was in the works by a Hacker News site maintainer for some time: called Clarc. Its source code has not been published. Since [late september, 2024], the official Hacker News site runs using Clarc and SBCL.
Here's (again) my new resource for web development in Common Lisp: Web Apps in Lisp: Know-how.
Now the links:
- CLOG CLOG 2.0 - Now with a complete Common Lisp IDE and GUI Builder (with or w/o emacs)
- CLOG OS shell
- CLOG CLOG Builder Video Manual Video 5 - Using Projects & Plugins
- CLOG debug tools https://github.com/rabbibotton/clog/discussions/361
- CLOG got emacs-like tabs
Projects built with CLOG:
- mold desktop - A programmable desktop.
- CLOG moldable inspector, "A moldable Common Lisp object inspector based on CLOG"
Weblocks (continued in the Reblocks project):
- Height Weblocks (Reblocks) Extensions - now with documentation
- video: Weblocks demo: a staff onboarding web app written in Common Lisp (EN Subs)
More:
Articles:
- Ningle Tutorial 3: Static Files Middleware
- Towards a Django-like database admin dashboard for Common Lisp
- Add Stripe billing to your Common Lisp app
- Building a highly-available web service without a database
- Building with Parenscript and Preact
- i18n in my Lisp web app with Djula templates and gettext
videos:
libraries:
- JZON hits 1.0 and is at last on the latest QL release: a correct and safe JSON parser, packed with features, and also FASTER than the latest JSON library advertised here.
- OpenAPI client generator
- Pulling portableaserve (Portable AllegroServe) into sharplispers
- ScrapyCL - The web scraping framework for writing crawlers in Common Lisp
- Nobody Knows Shoes But Ryo Shoes (A Simple GUI DSL upon CLOG)
The web views I mentioned: Electron is a thing, but today we have bindings to webview.h and webUI:
More libraries
Data structures:
Language extensions, core libraries:
- Dynamic Let (Common Lisp, MOP)
- Equality and Comparison in FSet, CDR8, generic-cl
- generic-cl 1.0
- cl-ppcre 2.1.2 - New function: count-matches
Iteration:
- cl-transducers 1.0 - operating over and into plists, hash-tables, CSV
- cl-transducers 1.2.0 - FSet support
- Štar: an iteration construct for Common Lisp
Developer tools:
Threads, actors:
- Bordeaux-Threads API v2
- Sento actor framework 3.0 released - no new features, many API changes: cleanups, obstacles removed, and hopefully a more consistent way of doing things.
- Sento 3.2 · allows a throughput of almost 2M messages per second
Documentation builders:
Databases:
- AllegroGraph 8
- Postmodern v1.33.10 and 1.33.11 released
- endatabas/endb v0.2.0-beta.1 · SQL document database with full history (Lisp, Rust)
- Mito-validate
relational database and first order logic:
Numerical and scientific:
- cl-waffe2: (Experimental) Graph and Tensor Abstraction for Deep Learning all in Common Lisp
- numericals` has a slightly better documentation now!
- Common Lisp: Numerical and Scientific Computing - Call for Needs
- Lisp Stats 2023 end of year summary
- More notes on using Maxima in a Lisp runtime
- maxima-interface - Simple interface between Common Lisp and Maxima
Plotting:
- GURAFU: a simple (just usable) plot program for Common Lisp
- plotly-user: Use plotly in your browser to explore data from a Common Lisp REPL
- "a week-end hack and an excuse to learn CLOG"
Bindings and interfaces:
- marcoheisig/lang: A library for seamless multi-language programming. The currently supported languages are Python and Lisp.
- bike (.NET interface for CL) version 0.14.0. Documentation! .NET-callable classes. ECL support. And more.
- CL-CXX-JIT: Write C++ functions within Common Lisp
- Common Lisp implementation of the Forth 2012 Standard
Serialization:
Date and time:
- Precise Time - hooking into the operating system to give sub-seconds precise timing information
- calendar-times - a calendar time library implemented on top of LOCAL-TIME
Utilities:
- cl-ansi-term: print tables with style, and other script utilities
- command-line-args - Turn your Common Lisp function into a command which you can use from the command line. (similar to defmain)
- file-finder: Rapid file search and inspection
- Consfigurator 1.4.1 released, including new support for FreeBSD
Bindings and interfaces to other software:
- cl-git 2.0 - an interface to the C library libgit2. The API is an almost complete exposure of the underlying library
- cl-telegram-bot - Telegram Bot API (now with documentation)
- claw-raylib - Fully auto-generated Common Lisp bindings to Raylib and Raygui using claw and cffi-object
Networking:
Scripting
(I love what's being done here)
- ruricolist/kiln: Infrastructure for scripting in Common Lisp to make Lisp scripting efficient and ergonomic.
- CIEL Is an Extended Lisp, Hacker News
- unix-in-lisp - Mount Unix system into Common Lisp image.
Software releases
- OpusModus 3.0, first Windows version released
- tamurashingo/reddit1.0: Refactored old reddit source code (with recent commits and a Docker setup)
- Release 1.0.0 · calm - Canvas and Lisp magic
- Lisa: A production-ready expert-system shell, written in thoroughly modern Common Lisp.
- todolist-cl 3.0 - a todolist web UI, written in Common Lisp, with Hunchentoot, Spinneret templates, Mito ORM. (by a CL newcomer)
- iescrypt: a tool to encrypt and/or sign files. Lisp and C versions.
Other articles
- A Tour of the Lisps
- Why I chose Common Lisp
- practicing statistics with Common Lisp (Jupyter notebook)
- Full Common Lisp (sbcl) and a CLOG dev environment on/from an Android device
Videos
Demos:
- AudioVisual in CommonLisp (cl-collider, cl-visual) (screencast)
- Cheesy trailer for recent kons-9 3D graphics features.
- Drum N Bass in CommonLisp
- Drum and Bass with a Counterpoint - How to Tutorial - Opusmodus
- How Lisp is designing Nanotechnology (Developer Voices, with Prof. Christian Schafmeister) (Youtube)
- How to Package Common Lisp Software for Linux? EN Subs (alien-works-delivery, linux-packaging)
- Melodic Techno - How to Tutorial - Opusmodus
- The Opusmodus Studio - Everything I didn't know I needed - Subject Sound (YouTube)
- Welcome to Opusmodus (Youtube)
- Identicons and Clozure Common Lisp, by R. Matthew Emerson
Web:
- Dynamic Page With HTMX and Common Lisp
- Common Lisp web development tutorial: how to build a web app in Lisp · part 2 part 1
- Missing Clack Guide! Build a Web Application in Common Lisp Like a Pro!
- URL shortener using Hunchentoot and BKNR
- web page graphics with lisp-stat, data-frame and vega plot
More from the ELS (see their Youtube channel):
- An Introduction to Array Programming in Petalisp, by Marco Heisig, ELS 2024
- Lightning Talk: Julia Functions, Now in Lisp
- Lightning Talk: Valtan: Write Webapp Everything in Common Lisp: European Lisp Symposium
- ELS2023: Common Lisp Foundation
Learning:
- I published 17 videos about Common Lisp macros - learn Lisp with a code-first tutorial comments
- Common Lisp Study Group: experiments with CFFI
- CLOS: Introduction and usage of defclass
- Nekoma Talks #19 - Common Lisp from a Clojurian perspective Part 2 (YouTube), part 1
- Review of 8 Common Lisp IDEs! Which one to choose? (EN Subs)
Aaaand that's it for the tour of the last couple years. Tell me if I missed something. I'll keep updating this post for a few days.
Happy lisping and show us what you build!
17 Feb 2025 5:06pm GMT
Joe Marshall: Advent of Code 2024: Day 6
A named-lambda is a lambda expression that has a name bound to it only within the scope of the lambda expression. You can use the name to refer to the lambda expression from within the body of the lambda expression. This allows you to recursively call the lambda expression. Named-lambdas are easily created with a macro that expands into a labels
form.
Named-lambdas are an alternative to using the Y operator to create recursive lambda expressions. Named-lambdas are a special form, so if you are uncomfortable with adding new special forms to the language, you'll probably prefer to use the Y operator.
Recall that let
expressions are just syntactic sugar for lambda
expressions. If you expand a let
expression using a named-lambda, you get a named-let expression. The name is bound to the lambda that binds the let variables. Invoking the name will re-invoke the let expression with different values for the bound variables.
Named lets take a moment to get used to, but once you get the hang of them, they are incredibly handy. They are especially useful when you use them for tail recursive loops. Here is an example where we use a named let to partition a list with a predicate:
(let next ((tail list) (yes '()) (no '())) (cond ((consp tail) (if (predicate (car tail)) (next (cdr tail) (cons (car tail) yes) no) (next (cdr tail) yes (cons (car tail) no)))) ((null? tail) (values yes no)) (t (error "Improper list."))))
When we invoke the name next
, we re-invoke the let expression with the new values for the bound variables. In this example, the calls to next
are in tail position, so the compiler turns them into jumps, making this a tail recursive loop.
The named-let syntax, with the name being the symbol before the bindings, is borrowed from MIT-Scheme. This syntax is easily implemented with a macro that expands into a labels
form if the name is present, but expands into a cl:let
if it is absent. You shadowing-import
the let
symbol into your package so that the macro will override the standard binding of let
.
For day 6, we have a guard patrolling a warehouse. The guard moves in straight lines unless he encounters an obstacle, where he will turn clockwise 90 degrees. If he moves off the grid, he goes home for the evening.
First, we'll read the grid and find the initial position of the guard:
(defun read-input (pathname) (read-file-into-grid (char-interner #'char-upcase (find-package "ADVENT2024/DAY6")) pathname)) (defun get-initial-position (grid) (let ((coord (collect-first (choose-if (lambda (coord) (member (grid-ref grid coord) '(^ < > v))) (scan-grid-coords grid))))) (ocoord coord (ecase (grid-ref grid coord) (^ +north+) (> +east+) (v +south+) (< +west+)))))
In the second part of the problem, we'll be allowed to place a single additional obstacle in the grid. patrol-step
attempts to move the guard one step forward, and turns him clockwise if he cannot move forward. obstacle-coord
is the additional obstacle or nil
:
(defun patrol-step (grid obstacle-coord oriented-position) (let ((next-ocoord (ocoord-advance oriented-position))) (cond ((not (on-grid? grid (ocoord-coord next-ocoord))) nil) ((or (eq (grid-ref grid (ocoord-coord next-ocoord)) '|#|) (equal (ocoord-coord next-ocoord) obstacle-coord)) (ocoord-cw oriented-position)) (t next-ocoord))))
patrol
places the guard at his initial position and repeatedly calls patrol-step
until the guard either walks off the grid or returns to an ocoord he has visited before (with the same orientation). We keep the history of visited ocoords in two ways: as a list and a hash table. The list gives us the history in order, while the hash table allows us to quickly check if we have visited an ocoord before (otherwise we'd have an O(n^2) algorithm). If the guard walks off the grid, we return the history list. If the guard returns to a previously visited ocoord, we return the symbol :loop
. Note the use of a named-let to loop the patrol steps.
(defun patrol (grid obstacle-coord start-opos) (let ((history-hash (make-hash-table :test 'equal))) (setf (gethash start-opos history-hash) t) (let iter ((opos start-opos) (history (list start-opos))) (let ((next (patrol-step grid obstacle-coord opos))) (cond ((null next) history) ((gethash next history-hash nil) :loop) (t (setf (gethash next history-hash) t) (iter next (cons next history))))))))
For part 1, we simply call patrol
with the initial position and nil
as the obstacle:
(defun unique-cells (history) (length (remove-duplicates (map 'list #'ocoord-coord history) :test #'equal))) (defun part-1 () (let* ((grid (read-input (input-pathname))) (initial-position (get-initial-position grid))) (unique-cells (patrol grid nil initial-position))))
For part 2, we iterate over the cells in the paths and see what happens if we place an obstacle there. We accumulate the locations that result in a loop:
(defun part-2 () (let* ((grid (read-input (input-pathname))) (initial-position (get-initial-position grid)) (unmodified-path (patrol grid nil initial-position)) (answer nil)) (dolist (obstacle (remove-duplicates (map 'list #'ocoord-coord unmodified-path) :test #'equal) (length (remove-duplicates answer :test #'equal))) (unless (and obstacle (equal obstacle (ocoord-coord initial-position))) (when (eq (patrol grid obstacle initial-position) :loop) (pushnew obstacle answer :test #'equal))))))
17 Feb 2025 8:33am GMT
16 Feb 2025
Planet Lisp
Joe Marshall: Advent of Code 2024: Day 5
For day 5, the input comes in two parts: There are rules of the form n|m, where n and m are numbers, and there are "updates" which are lists of numbers separated by commas. The rules are used to determine which updates are valid. An update is valid if it passes all applicable rules. A rule is applicable if the two numbers in the rule appear in the update. An update passes an applicable rule if the two numbers in the rule appear in the update in the same order as they appear in the rule.
To read the input, we read the lines and collect them into two lists. The rule list is all the lines that contain a pipe character, and the updates list is all the lines that contain a comma:
(defun read-input (input-file) (let ((lines (scan-file input-file #'read-line))) (let ((is-rule (#M(lambda (line) (find #\| line)) lines)) (is-update (#M(lambda (line) (find #\, line)) lines))) (values (collect 'list (#M(lambda (rule) (map 'list #'parse-integer (str:split #\| rule))) (choose is-rule lines))) (collect 'list (#M(lambda (update) (map 'list #'parse-integer (str:split #\, update))) (choose is-update lines)))))))
To test a rule, we find the location of the two numbers in the update and check that they are in the same order as they appear in the rule. If either number is not found, the rule is not applicable and trivially passes.
(defun test-rule (rule update) (let ((left-position (position (first rule) update)) (right-position (position (second rule) update))) (or (null left-position) (null right-position) (< left-position right-position)))) (defun test-rules (rules update) (collect-and (#Mtest-rule (scan 'list rules) (series update))))
Part 1 is to sum the middle numbers of all the updates that pass all the rules:
(defun middle-number (list) (elt list (/ (1- (length list)) 2))) (defun part-1 () (multiple-value-bind (rules updates) (read-input (input-pathname)) (collect-sum (#Mmiddle-number (choose-if (lambda (update) (test-rules rules update)) (scan 'list updates))))))
For part 2, we select the updates that fail the rules. We repair the update by sorting it using the rules as a sort predicate, then we sum the middle numbers of the repaired updates:
(defun sort-using-rules (rules list) (sort list (lambda (left right) (find (list left right) rules :test #'equal)))) (defun part-2 () (multiple-value-bind (rules updates) (read-input (input-pathname)) (collect-sum (#Mmiddle-number (#M(lambda (update) (sort-using-rules rules update)) (choose-if (lambda (update) (not (test-rules rules update))) (scan 'list updates)))))))
16 Feb 2025 8:24am GMT
15 Feb 2025
Planet Lisp
Joe Marshall: Advent of Code 2024: Day 4
Day 4 part 1 is your standard word search. First we read the grid of letters:
(defun read-input (input-pathname) (read-file-into-grid (char-interner #'char-upcase (find-package "ADVENT2024/DAY4")) input-pathname))
A "trace" is a row, column, or diagonal of letters. To search a trace for the word, we examine each suffix of the trace to see if starts with the word. We also check the reverse of the word:
(defun search-trace (trace target) (let ((rev (reverse target))) (collect-sum (#M(lambda (suffix) (if (or (starts-with-subseq target suffix) (starts-with-subseq rev suffix)) 1 0)) (scan-suffixes trace)))))
Then we search all the traces:
(defun search-trace-list (trace-list target) (collect-sum (#M(lambda (trace) (search-trace trace target)) (scan 'list trace-list)))) (defun search-grid (grid target) (collect-sum (#M(lambda (get-trace-list) (search-trace-list (funcall get-trace-list grid) target)) (scan 'list (list (lambda (grid) (collect 'list (scan-rows grid))) (lambda (grid) (collect 'list (scan-columns grid))) (lambda (grid) (collect 'list (scan-falling-diagonals grid))) (lambda (grid) (collect 'list (scan-rising-diagonals grid)))))))) (defun part-1 () (search-grid (read-input (input-pathname)) #(X M A S)))
Note that since scan-rows
etc. and collect
are macros, so we cannot pass them as first class functions. Instead we pass lambdas that call them so that the full macro expression is visible to the compiler.
For part 2, we are searching for Xs of "MAS" in the grid. We search for A
s, then check for M
and S
in the diagonals.
m-s1?
is a helper function that checks if a pair of coords contains an M
and an S
.
(defun m-s1? (grid coord1 coord2) (and (on-grid? grid coord1) (on-grid? grid coord2) (eql (grid-ref grid coord1) 'M) (eql (grid-ref grid coord2) 'S)))
m-s?
checks if a pair of coords contains an M
and an S
in any order.
(defun m-s? (grid coord1 coord2) (or (m-s1? grid coord1 coord2) (m-s1? grid coord2 coord1)))
x-mas?
checks whether an A
is surrounded by an M
and an S
.
(defun x-mas? (grid coord) (and (on-grid? grid coord) (eql (grid-ref grid coord) 'A) (and (m-s? grid (coord-northwest coord) (coord-southeast coord)) (m-s? grid (coord-northeast coord) (coord-southwest coord)))))
Then we just count the occurrances:
(defun search-x-mas (grid) (collect-sum (#M(lambda (coord) (if (x-mas? grid coord) 1 0)) (scan-grid-coords grid)))) (defun part-2 () (search-x-mas (read-input (input-pathname))))
15 Feb 2025 7:09am GMT
12 Feb 2025
Planet Lisp
Joe Marshall: Advent of Code 2024: Day 3
For Day 3, we are given a "corrupted" block of memory as a string. We are to find the "uncorrupted instructions" in the block and emulate them.
For this problem, we don't attempt to force things into the series paradigm. The cl-ppcre
library provides a bunch of functions for working with regular expressions, and the do-register-groups
macro is ideal for this problem. It iterates over all the matches of a regular expression, binding submatches to some variables, with some optional processing of the submatch. (If the cl-ppcre
library offered a function that returned a series of matches, we could use that, but it offers a do
macro.)
First, we read the input:
(defun read-input (input-pathname) (read-file-into-string input-pathname))
Next, we define a regular expression to match the instructions:
(defparameter *mul-instruction* "(mul\\((\\d{1,3}),(\\d{1,3})\\))")
Now we just iterate over all the matches:
(defun part-1 () (let ((answer 0)) (cl-ppcre:do-register-groups (whole (#'parse-integer left) (#'parse-integer right)) (*mul-instruction* (read-input (input-pathname))) (declare (ignore whole)) (incf answer (* left right))) answer))
do-register-groups
is an example of a macro where the parenthesized subexpressions do not indicate function calls. The first parenthesized subgroup is a variable list, and within the variable list, a parenthesized subgroup indicates a transformer to be applied before binding the variable. So in this case, we are binding the variables whole
, left
, and right
, and we run the matching subgroup through parse-integer
before binding the left
and right
variables.
The second parenthesized subgroup is a list of the regular expression to match and the string to match within. After these irregular parenthesized subgroups, the remaining is a body of code that is executed for each match.
In the body of the code, we ignore the whole
variable (which is the whole match) and increment the answer by the product of the left
and right
variables. As is usual for a do
macro, we transport the data out of the loop by side effecting a lexically scoped variable.
For part 2, we have additional instructions to emulate. Our loop will now have some state to it, and we will side effect the state as we iterate over the matches. We can just extend the regular expression and add a cond
to the body of the do-register-groups
to handle the new instructions. As we iterate over the matches, we side effect the emulation state:
(defparameter *do-mul-instruction* "(do\\(\\))|(don't\\(\\))|(mul\\((\\d{1,3}),(\\d{1,3})\\))") (defun part-2 () (let ((answer 0) (on t)) (cl-ppcre:do-register-groups (turn-on turn-off whole (#'parse-integer left) (#'parse-integer right)) (*do-mul-instruction* (read-input (input-pathname))) (declare (ignore whole)) (cond (turn-on (setq on t)) (turn-off (setq on nil)) (on (incf answer (* left right))) (t nil))) answer))
Strictly speaking, we don't need to use side effects. We could rework this to be purely functional, but this seems unnatural. Yes, there is a bit of cognitive overhead in remembering that there is a state variable that determines whether or not we are executing an instruction, but the code is quite understandable.
"Do" macros usually need some side effects, but we can localize the side effects by using a let
to lexically bind the state variables and then side effecting them from within the loop. This is an effective compromise between the functional and imperative programming paradigms.
12 Feb 2025 1:49pm GMT
Joe Marshall: Advent of Code 2024: Day 2
For Day 2 in the Advent of Code, we are given a file where each line in the file contains a list of integers separated by spaces. We will be performing some manipulations on these lists.
First, we need to read the file. We make a function to read a line as a string, then read the integers from the string and collect the result into a list.
(defun read-levels (stream eof-error-p eof-value) (let ((line (read-line stream eof-error-p eof-value))) (if (eq line eof-value) eof-value (with-input-from-string (stream line) (collect 'list (scan-stream stream))))))
We use this function to read the entire file into a list of lists of integers.
(defun read-input (input-pathname) (collect 'list (scan-file input-pathname #'read-levels)))
We are concerned with the deltas between adjacent elements in a series of integers. We make a function to calculate the deltas. This will be an optimizable-series-function
because it returns a series of deltas. We declare
the argument to be an "off-line" input series as well. This code will be transformed into the equivalent loop code where we consume the deltas.
chunk
is a series function that takes a series and produces n
series of chunks that are offset by a specified amount. We produce chunks of size 2, offset by 1. This returns two series, the left number of each pair of numbers and the right number of each pair of numbers. By mapping #'- over these series, we get the series of deltas between adjacent numbers.
(defun deltas (series) (declare (optimizable-series-function) (off-line-port series)) (multiple-value-bind (left right) (chunk 2 1 series) (#M- right left)))
As per the puzzle, a series of deltas is considered "safe" if it is strictly ascending or descending, and each step by which it ascends or descends is between 1 and 3 inclusive. We get the series of deltas, map #'plusp to get a series of booleans indicating whether each delta is positive, and collect-and
on the series of booleans. Likewise with #'minusp for descending. Finally, we create a series of booleans indicating whether the absolute value of the delta is <= 3 and collect-and
this as well. Whether the deltas are considered "safe" is just a boolean operation on these three boolean values:
(defun safe-levels? (list) (let ((deltas (deltas (scan list)))) (let ((ascending (collect-and (#Mplusp deltas))) (descending (collect-and (#Mminusp deltas))) (small (collect-and (#M<= (Mmabs deltas) (series 3))))) (and small (or ascending descending)))))
The first part of the puzzle asks us to count the number of lines considered "safe":
(defun part-1 () (count-if #'safe-levels? (read-input (input-pathname))))
The second part of the puzzle relaxes the safety restriction by saying that you are allowed to 'dampen' the list by removing a single outlier before checking for safety.
(defun safe-dampened-levels? (levels) (find-if #'safe-levels? (remove-one-element levels))) (defun part-2 () (count-if #'safe-dampened-levels? (read-input (input-pathname))))
12 Feb 2025 12:54pm GMT
Joe Marshall: Advent of Code 2024: Day 1
Half the problem of solving an Advent of Code puzzle is dealing with the puzzle input. It is generally in some ad hoc format that requires a bespoke parser. There are a few approches you can take.
- Read the input as a string and directly call string manipulation functions to extract the data.
- Read the input as a string and use regular expressions to extract the data.
- Use the lisp reader to read the input as a lisp data structure. This requires that the input looks like lisp objects.
- Tweak the Lisp reader to read the data in a custom format. This works if the input looks a lot like lisp objects.
For Day 1, the input is two columns of numbers. If we just scan the file with the lisp reader, we'll get a single list of numbers. We can convert this into two lists with the series chunk
function:
(defun read-input (input-pathname) (multiple-value-bind (left-column right-column) (chunk 2 2 (scan-file input-pathname)) (values (collect 'list left-column) (collect 'list right-column))))
For part 1 of the puzzle, we sort both columns and then walk through them in parallel finding the absolute difference between the columns and summing that.
(defun part-1 () (multiple-value-bind (left-column right-column) (read-input (input-pathname)) (collect-sum (#Mabs (#M- (scan (sort left-column #'<)) (scan (sort right-column #'<)))))))
For part 2, we look at each number in the left column and multiply it by how many times it appears in the right column. We sum these quantities.
(defun part-2 () (multiple-value-bind (left-column right-column) (read-input (input-pathname)) (collect-sum (#M(lambda (item) (* item (count item right-column))) (scan left-column)))))
These examples show how we can use series and built-in sequence functions to eliminate loops.
12 Feb 2025 12:45pm GMT
11 Feb 2025
Planet Lisp
Joe Marshall: Advent of Code 2024: Day 0
I wanted to write some blog posts, but I was short of material. For the fun of it, I've decided to write a series of posts about solving the 2024 Advent of Code problems in Common Lisp. I see that other people were doing this in real time, but it is too late for that. Besides, I didn't want the stress of trying to solve the problems as part of a competition. I wanted to take my time and focus on code quality rather than on how fast I can write it.
I noticed that some programmers were less experienced in Common Lisp. They tended to code up solutions that used low-level Common Lisp operations instead of using one of Common Lisp's powerful sequence operations. For example, they might use a loop to iterate over a list and incf
a counter instead of just using a call to count
. I want to show how to effectively use the rich set of Common Lisp library functions to write concise, readable, and efficient code.
I'm trying to decide what I think of the series
package that provides a more functional approach to iteration without sacrificing performance. For a lot of iterations, it is easy to write series code, but it for other iterations it isn't so obvious. I wanted a little practice in using series and seeing its limitations.
Conventions
One of the features of Common Lisp is that you can tailor the language to fit the problem space. The first step in solving the problem suite is to configure the language. Since I wanted to explore using the series
package, I set up my Lisp so that series
was available in all the packages. I also installed the alexandria
library, which is a collection of utilities that flesh out the Common Lisp standard library with some obvious "missing" functions.
The series
package includes an optional #M
reader macro that gives you a shorthand for writing mapping expressions. I added the "named" let syntax which attaches a name to the binding lambda of a let
expression allowing you to invoke the reinvoke the let
as a recursive function. The default delarations were set to ensure that the compiler could would generate tail recursive code. Tail recursion coupled with named-let is a powerful iteration facility.
I set up the directory structure to have a subdirectory for each day. Each problem in the entire Advent of Code could fit in its own solution.lisp
file, so each subdirectory had files input.txt
and solution.lisp
, and usually sample-input.txt
and maybe one or more sample-input-
n.txt
The parent directory had an advent2024.asd
file, a package.lisp
file that defined all the packages, an initialize.lisp
file that customized Common Lisp and installed some bootstrap values in each package, and a misc.lisp
file that contained some common definitions that were exported to all the packages.
I set up my Lisp to have a separate package for each day. The package definition file contained 25 package definitions, each one virtually identical, e.g.:
(defpackage "ADVENT2024/DAY16" (:shadow "VALIDATE") (:import-from "ALEXANDRIA" "FLATTEN" "HASH-TABLE-ALIST" "HASH-TABLE-KEYS" "HASH-TABLE-VALUES" "LENGTH=" "MAPPEND" "MAP-PERMUTATIONS" "MAP-PRODUCT" "READ-FILE-INTO-STRING" "STARTS-WITH-SUBSTRING" ) (:shadowing-import-from "NAMED-LET" "LET") (:shadowing-import-from "SERIES" "DEFUN" "FUNCALL" "LET*" "MULTIPLE-VALUE-BIND" ) (:export "PART-1" "PART-2" "+SOLUTION-1+" "+SOLUTION-2+" "VALIDATE") (:use "ADVENT2024" "COMMON-LISP" "FOLD" "FUNCTION" "NAMED-LET" "SERIES"))
This basically set up Lisp to have series
available, and imported a few symbols from alexandria
.
Each day's puzzle has two parts, so each package exports the symbols PART-1
and PART-2
to be defined as zero argument functions that compute and return the solution to the respective parts. The symbols +SOLUTION-1+
and +SOLUTION-2+
are defined as defparameter
values. The initialization function installs a validate
function checks that (part-1)
returns +SOLUTION-1+
and (part-2)
returns +SOLUTION-2+
in each package.
misc.lisp
The misc.lisp
file contains code that is common to more than one puzzle.
The grid abstraction
The problem space of many of the puzzles is two dimensional, and it is natural to use a two-dimensional lisp array for the representation. I enhance this with a lightweight abstraction called a grid.
A grid is adressed by a coord, which is an ordered pair of column and row. These are simply the car
and cdr
of a cons cell. The functions that construct and select from a coord
are all given compiler-macro
definitions. In the 99% of the cases where you simply call the constructor or selector, the compiler macro will expand the code. In the 1% case, where you pass the constructor or selector as a first-class function, the function definition is passed.
(deftype grid-index () '(integer ,(- array-dimension-limit) (,array-dimension-limit))) (deftype coord () '(cons (grid-index) (grid-index))) (eval-when (:compile-toplevel :load-toplevel :execute) (defun coord (column row) (check-type column grid-index) (check-type row grid-index) (cons column row)) ) (define-compiler-macro coord (column row) '(cons ,column ,row)) (defun column (coord) (check-type coord coord) (car coord)) (define-compiler-macro column (coord) '(car ,coord )) (defun row (coord) (check-type coord coord) (cdr coord)) (define-compiler-macro row (coord) '(cdr ,coord)) (defun scan-coords (row-count col-count) (declare (optimizable-series-function)) (multiple-value-bind (rows cols) (map-fn '(values grid-index grid-index) #'floor (scan-range :below (* row-count col-count)) (series col-count)) (declare (type (series grid-index) rows cols)) (map-fn 'coord #'coord cols rows)))
A grid is just a two-dimensional array of atoms:
(deftype grid () '(array atom 2)) (defun make-grid (height width &rest; keys) (apply #'make-array (list height width) keys)) (defun row-list->grid (row-list) (make-grid (length row-list) (length (first row-list)) :initial-contents row-list)) (defun grid-height (grid) (check-type grid grid) (array-dimension grid 0)) (define-compiler-macro grid-height (grid) '(array-dimension ,grid 0)) (defun grid-width (grid) (check-type grid grid) (array-dimension grid 1)) (define-compiler-macro grid-width (grid) '(array-dimension ,grid 1))
A coord is on a grid if it is within the bounds of the grid:
(defun on-grid? (grid coord) (and (>= (column coord) 0) (< (column coord) (grid-width grid)) (>= (row coord) 0) (< (row coord) (grid-height grid))))
You may want to check if the coord is on the grid before calling grid-ref
.
(defun grid-ref (grid coord) (check-type grid grid) (check-type coord coord) (aref grid (row coord) (column coord))) (define-compiler-macro grid-ref (grid coord) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (aref ,grid (row ,coord-var) (column ,coord-var))))) (defsetf grid-ref (grid coord) (value) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (setf (aref ,grid (row ,coord-var) (column ,coord-var)) ,value)))) (defun scan-grid-coords (grid) (declare (optimizable-series-function)) (scan-coords (grid-height grid) (grid-width grid))) (defun scan-grid (grid) (declare (optimizable-series-function 2)) (#2m(lambda (grid coord) (values coord (grid-ref grid coord))) (series grid) (scan-coords (grid-height grid) (grid-width grid))))
You can invert a grid. This will give you a hash table that maps the atoms in the grid to a list of their coords.
(defun invert-grid (grid &optional; initial-value) (if initial-value (multiple-value-bind (coords vals) (scan-grid grid) (collect-hash-push-except vals coords (list initial-value))) (multiple-value-bind (coords vals) (scan-grid grid) (collect-hash-push vals coords))))
You can extract a row, column, or diagonal from a grid:
(defun grid-row (grid row-number) (check-type grid grid) (make-array (list (grid-width grid)) :displaced-to grid :displaced-index-offset (array-row-major-index grid row-number 0))) (defun grid-column (grid columm-number) (check-type grid grid) (let ((answer (make-array (grid-height grid)))) (dotimes (row (grid-height grid) answer) (setf (svref answer row) (grid-ref grid (coord columm-number row)))))) (defun grid-falling-diagonal (grid diagonal-number) (check-type grid grid) (let ((start-column (if (minusp diagonal-number) 0 diagonal-number)) (start-row (if (minusp diagonal-number) (- diagonal-number) 0))) (let ((limit (min (- (grid-width grid) start-column) (- (grid-height grid) start-row)))) (let ((answer (make-array (list limit)))) (do ((row start-row (+ row 1)) (column start-column (+ column 1)) (index 0 (+ index 1))) ((>= index limit) answer) (setf (svref answer index) (grid-ref grid (coord column row)))))))) (defun grid-rising-diagonal (grid diagonal-number) (check-type grid grid) (let ((start-column (if (minusp diagonal-number) (- diagonal-number) 0)) (start-row (if (minusp diagonal-number) (1- (grid-height grid)) (- (grid-height grid) diagonal-number 1)))) (let ((limit (min (- (grid-width grid) start-column) (1+ start-row)))) (let ((answer (make-array (list limit)))) (do ((row start-row (- row 1)) (column start-column (+ column 1)) (index 0 (+ index 1))) ((>= index limit) answer) (setf (svref answer index) (grid-ref grid (coord column row))))))))
Given a grid, you can get the series of rows, columns, or diagonals:
(defun scan-rows (grid) (declare (optimizable-series-function)) (map-fn 'vector #'grid-row (series grid) (scan-range :below (grid-height grid)))) (defun scan-columns (grid) (declare (optimizable-series-function)) (map-fn 'vector #'grid-column (series grid) (scan-range :below (grid-width grid)))) (defun scan-falling-diagonals (grid) (declare (optimizable-series-function)) (map-fn 'vector #'grid-falling-diagonal (series grid) (scan-range :from (1+ (- (grid-height grid))) :below (grid-width grid)))) (defun scan-rising-diagonals (grid) (declare (optimizable-series-function)) (map-fn 'vector #'grid-rising-diagonal (series grid) (scan-range :from (- 1 (grid-width grid)) :below (grid-height grid))))
An orientation
is a unit coord.
(deftype unit () '(integer -1 1)) (deftype orientation () '(cons (unit) (unit))) (defun unit-vector (column row) (check-type column unit) (check-type row unit) (cons column row)) (defparameter +north+ (unit-vector 0 -1)) (defparameter +northeast+ (unit-vector 1 -1)) (defparameter +east+ (unit-vector 1 0)) (defparameter +southeast+ (unit-vector 1 1)) (defparameter +south+ (unit-vector 0 1)) (defparameter +southwest+ (unit-vector -1 1)) (defparameter +west+ (unit-vector -1 0)) (defparameter +northwest+ (unit-vector -1 -1))
You can do 2d-vector arithmetic on a coord
(defun 2v+ (left right) (coord (+ (column left) (column right)) (+ (row left) (row right)))) (defun 2v- (left right) (coord (- (column left) (column right)) (- (row left) (row right))))
Given a coord
, you can get the coord
of the adjacent cell in a given orientation
. Note that the new coord might not be on the grid if you're at the edge.
(defun coord-north (coord) (check-type coord coord) (2v+ coord +north+)) (define-compiler-macro coord-north (coord) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (coord (column ,coord-var) (1- (row ,coord-var)))))) (defun coord-northeast (coord) (check-type coord coord) (2v+ coord +northeast+)) (define-compiler-macro coord-northeast (coord) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (coord (1+ (column ,coord-var)) (1- (row ,coord-var)))))) (defun coord-east (coord) (check-type coord coord) (2v+ coord +east+)) (define-compiler-macro coord-east (coord) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (coord (1+ (column ,coord-var)) (row ,coord-var))))) (defun coord-southeast (coord) (check-type coord coord) (2v+ coord +southeast+)) (define-compiler-macro coord-southeast (coord) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (coord (1+ (column ,coord-var)) (1+ (row ,coord-var)))))) (defun coord-south (coord) (check-type coord coord) (2v+ coord +south+)) (define-compiler-macro coord-south (coord) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (coord (column ,coord-var) (1+ (row ,coord-var)))))) (defun coord-southwest (coord) (check-type coord coord) (2v+ coord +southwest+)) (define-compiler-macro coord-southwest (coord) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (coord (1- (column ,coord-var)) (1+ (row ,coord-var)))))) (defun coord-west (coord) (check-type coord coord) (2v+ coord +west+)) (define-compiler-macro coord-west (coord) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (coord (1- (column ,coord-var)) (row ,coord-var))))) (defun coord-northwest (coord) (check-type coord coord) (2v+ coord +northwest+)) (define-compiler-macro coord-northwest (coord) (let ((coord-var (gensym "COORD-"))) '(let ((,coord-var ,coord)) (coord (1- (column ,coord-var)) (1- (row ,coord-var))))))
An ocoord
is a coord that has a direction associated with it. It is a coord
plus an orientation
.
(deftype ocoord () '(cons coord orientation)) (defun ocoord (coord orientation) (check-type coord coord) (check-type orientation orientation) (cons coord orientation)) (define-compiler-macro ocoord (coord orientation) '(cons ,coord ,orientation)) (defun ocoord-coord (ocoord) (check-type ocoord ocoord) (car ocoord)) (define-compiler-macro ocoord-coord (ocoord) '(car ,ocoord)) (defun ocoord-orientation (ocoord) (check-type ocoord ocoord) (cdr ocoord)) (define-compiler-macro ocoord-orientation (ocoord) '(cdr ,ocoord))
The point of an ocoord
is to be able to take a step forward in the direction of the orientation
, or to turn clockwise or counterclockwise.
(defun ocoord-advance (ocoord) (check-type ocoord ocoord) (ocoord (2v+ (ocoord-coord ocoord) (ocoord-orientation ocoord)) (ocoord-orientation ocoord))) (define-compiler-macro ocoord-advance (ocoord) (let ((ocoord-var (gensym "OCOORD-"))) '(let ((,ocoord-var ,ocoord)) (ocoord (2v+ (ocoord-coord ,ocoord-var) (ocoord-orientation ,ocoord-var)) (ocoord-orientation ,ocoord-var))))) (defun ocoord-cw (ocoord) (check-type ocoord ocoord) (ocoord (ocoord-coord ocoord) (cond ((equal (ocoord-orientation ocoord) +north+) +east+) ((equal (ocoord-orientation ocoord) +east+) +south+) ((equal (ocoord-orientation ocoord) +south+) +west+) ((equal (ocoord-orientation ocoord) +west+) +north+)))) (defun ocoord-ccw (ocoord) (check-type ocoord ocoord) (ocoord (ocoord-coord ocoord) (cond ((equal (ocoord-orientation ocoord) +north+) +west+) ((equal (ocoord-orientation ocoord) +east+) +north+) ((equal (ocoord-orientation ocoord) +south+) +east+) ((equal (ocoord-orientation ocoord) +west+) +south+))))
The grid input to many of the puzzles is presented as "ASCII art" characters in a file. For example, the input might look like this:
....#..... .........# .......... ..#....... .......#.. .......... .#..^..... ........#. #......... ......#...
To read this into a grid, we'll need a function that converts a string into a list of atoms. We'll need a function that converts a char to an atom:
(defun string-mapper (char-fn) "Returns a function that maps strings to lists." (lambda (line) (collect 'list (map-fn 't char-fn (scan 'string line)))))
We can use this to read the input file into a grid:
(defun read-file-into-grid (char-fn filename) "Returns the contents of the file as a two-dimensional array." (row-list->grid (collect 'list (map-fn 'list (string-mapper char-fn) (scan-file filename #'read-line)))))
char-fn
is called on each character in the file. If it is #'identity
, then the grid will be a grid of characters. However, we usually want a grid of atoms, so we supply a function that converts a character to an atom.
(defun char->decimal (char) (- (char-code char) (char-code #\0))) (defun char-interner (char-folder package) (lambda (char) (if (digit-char-p char) (char->decimal char) (intern (string (funcall char-folder char)) package))))
We can use this to read the input file into a grid:
;; Case folding (read-file-into-grid (char-interner #'char-upcase *package*) "input.txt") ;; Case preserving (read-file-into-grid (char-interner #'identity *package*) "input.txt")
Other miscellaneous functions
advent-pathname
converts a relative pathname to an absolute pathname in the advent2024
directory. advent-pathname
is used to find the input files.
(defun advent-pathname (pathname) (merge-pathnames pathname (asdf/system:system-source-directory "advent2024")))
cartesian-product-list
takes a list of lists and returns a list of lists that are the cartesian product of the input lists. For example, (cartesian-product-list '((1 2) (3 4)))
returns ((1 3) (1 4) (2 3) (2 4))
.
(defun map-cons (car cdrs) (map 'list (lambda (cdr) (cons car cdr)) cdrs)) (defun cartesian-product (&rest; lists) (cartesian-product-list lists)) (defun cartesian-product-list (lists) (fold-left (lambda (tails terms) (mappend (lambda (term) (map-cons term tails)) terms)) (list nil) (reverse lists)))
integer-log
is used to find the number of digits an integer has in a given base.
(defun integer-log (n base) "Returns two values, the integer-log of <n> in <base>, and the leftmost digit in <base>." (if (< n base) (values 0 n) (multiple-value-bind (ilog l) (integer-log n (* base base)) (if (< l base) (values (* ilog 2) l) (values (+ (* ilog 2) 1) (/ l base))))))
Miscellaneous list functions
I gave the miscellaneous list functions as a puzzle in a previous post. I'll repeat them here for convenience.
map-pairs
takes a list of items and maps a function over all pairs of items. For example:
(map-pairs #'list '(1 2 3)) ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
revmap
is like map
, but it returns a list in reverse order.
revmap-cons
, given a car and list of cdrs, returns a list of lists where each list has the car and one of the cdrs. The lists are returned in reverse order.
revmappend
is like mappend
, but it returns the list in reverse order.
remove-one-element
returns a list of lists. Each sublist is the input list with one element removed.
Miscellaneous scanner
scan-suffixes
takes a sequence and returns a series of the suffixes of the sequence. If include-empty?
is true (the default), then the empty sequence is the last suffix. If proper?
is true (default false), then the original full sequence is omitted from the series.
Armed with these miscellaneous functions, we can tackle the puzzles. I'll write up some solutions in the next few posts.
11 Feb 2025 1:39pm GMT
10 Feb 2025
Planet Lisp
Joe Marshall: Out of Practice List-fu
How is your list-fu? Mine gets rusty when I don't manipulate lists for a while. Here are some simple puzzles to get the rust out.
1. Write a function that takes a list of items and maps a function over the pairs of items in the list, in the following way: The first argument to the function is taken from one of the elements in the list. The second argument is taken from one of the subsequent elements in the list. E.g., if the list is (a b c d), then
(map-pairs (lambda (x y) '(F ,x ,y)) '(a b c d)) ((F A B) (F A C) (F A D) (F B C) (F B D) (F C D))
2. Write a function revmap
that is like mapcar
, but the result is in reverse order.
3. Write a function map-cons
that takes a car
and a list of cdr
s, and returns a list of the car
consed on each of the cdr
s.
4. Write a function revmappend
that is like alexandria:mappend
but is more efficient because it doesn't try to preserve the order of the elements.
5. Write a function remove-one-element
that takes a list of n
elements and returns n
lists of n-1
elements, where each sublist has one element removed from the original list.
10 Feb 2025 7:45pm GMT