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))))))