This is a part of my ongoing challenge of solving every Advent of Code puzzle in a different language.

The challenge we're tackling today is available here.

Crossed wires

This time, we’re given the path of two wires, expressed as movement instructions. We’re to find the closest intersection of these wires, relative to the starting location.

This seems straightforward enough. Build paths of the wires, find the intersections, then find the closest.

The Language

I feel like writing a lot of parentheses for this one. Let’s use a lisp. Lisps are a family of languages notable for using a distinctive syntax, where all your code is formatted as lists, between parentheses, where the first element of any given list is the function you call, and the rest are arguments. A lot of lisps are functional, as the style lends itself well for functional languages, as there is no difference between code and data.

This is how you’d print the result of 1 + 1 in any standard lisp (but the print may be named differently):

(print (+ 1 1))

Notice how the first element of both lists is a function, where + is a function just like print.

Nowadays, there are three main dialects of lisp that people use, which, in turn, have different implementations:

1. Clojure - a terrific functional lisp flavor. The standard implementations run on top of the JVM or transpile to JavaScript. We won’t use Clojure as I want to save both the JVM and JavaScript for later. This, in my anecdotal experience, is the most popular flavor of lisp currently used.
2. Common Lisp - a classic lisp flavor, with many features, like being able to write object-oriented code.
3. Scheme - a pristinely minimal flavor of lisp.

I decided to go with a Scheme, as I’ve tried the other two and it runs in my family.

There are many different implementations of scheme that we could use, but I’ve been hearing of racket over the past couple of years, so I’ll go with that.

Lisp has a very long and colorful history, tied to both hardcore academia and startup hackers. I don’t think it’s possible to overstate its influence on the languages we all use nowadays. For a better read about lisp, Paul Graham has written many essays as a love letter to lisp, which are a great read. As a result of PG’s love of lisp, hacker news is built using their dialect of it.

The Solution

Let’s check out the code:

#lang racket

(define (parse-input-operation i)
  (list (substring i 0 1) (string->number (substring i 1))))

(define (parse-input filename)
  (let ([lines (string-split (file->string filename) "\n")])
    (map (lambda (line) (map parse-input-operation (string-split line ","))) lines)))

; move a coordinate pair by 1 in a given direction
(define (move-direction coord direction)
  (case direction
    [("U") (list (car coord)        (add1 (cadr coord)))]
    [("D") (list (car coord)        (sub1 (cadr coord)))]
    [("L") (list (sub1 (car coord)) (cadr coord))]
    [("R") (list (add1 (car coord)) (cadr coord))]))

; apply a single operation to a coordinate pair
(define (apply-operation coord operation)
  (let ([operation-count (cadr operation)]
        [direction (car operation)])
    (foldl (lambda (_ lst)
             (cons (move-direction
                     (if (empty? lst) coord (car lst)) direction)
                   lst))
      '()
      (range operation-count))))

; follow a wire and build a list of coordinates
(define (build-path operations)
  (let ([path (foldl (lambda (operation lst)
                       (append (apply-operation (car lst) operation) lst))
                     '((0 0))
                     operations)])
    (drop-right path 1))) ; drop the original 0 point

(define (distance-from-start coord)
  (+ (abs (car coord)) (abs (cadr coord))))

(define (find-path-intersections paths)
  (let ([path-sets (map list->set paths)])
    (set->list (apply set-intersect path-sets))))

(define (reverse-index-of lst element)
  (- (length lst) (index-of lst element)))

; solution to problem 1
(define (find-closest-intersection paths)
  (let* ([intersections (find-path-intersections paths)]
         [distances (map distance-from-start intersections)])
    (apply min distances)))

; solution to problem 2
(define (find-fewest-step-intersection paths) 
  (let* ([intersections (find-path-intersections paths)]
         [steps (map (lambda (intersection)
                       (foldl (lambda (path sum) (+ sum (reverse-index-of path intersection)))
                              0
                              paths)) intersections)])
    (apply min steps)))


; main program starts here
(define input-paths (map build-path (parse-input "input")))
(find-closest-intersection input-paths)
(find-fewest-step-intersection input-paths)

The solution to the first part is exactly what we discussed earlier. First, we build lists of coordinates of where the wires are. Then, (using the built-in set type) we find where the wires intersect. Finally, we find the manhattan distance from 0, 0 and find the minimum distance. Most of the code is function definitions, with the last three lines executing code using all of them.

For the second problem, we had to do the same, but instead of finding the closest via manhattan distance, we had to find the intersection to whom it took the least distance for the wires themselves to reach. Since, in our implementation, we move with an increment of 1, I found it easiest to just add up the indexes of the intersections in both paths to find the distances.

I got hit with a couple of gotchas. Since most lisps use (effectively) classic linked lists as their main list implementation, it’s much more effective to prepend items than to append them. Thus, I ended up prepending everything. This also meant I had to reverse the index of an element relative to the start, as they grew in reverse order. This mistake took me a while to find.

We don’t have to print anything, as if a top-level expression returns something, it will be output automatically. This is what the last two lines do.

Retro

I haven’t used a lisp in a while. It becomes fun quite quickly, as there’s something supremely elegant about having all of your code just be lists of data, modifying other lists of data. Maybe we can fit another lisp in our 25 days.

If you want to look at the code in full, I’m putting all of the Advent of Code solutions on GitHub.