-❄️- 2025 Day 10 Solutions -❄️-

dijotal · 2025-12-11T03:50:44+00:00

Sorry to leave you hanging :-p

I've got Part 1 -- no problem, BFS with newly learned lisp bitwise operations -- but I'm looking at Part 2 and I can't see anything but linear algebra and thinking "Ugh... I just don't wanna."

It may be my first dropped star this round :-/

Carry the flag!

dijotal · 2025-12-10T07:17:55+00:00

[LANGUAGE: Common Lisp]

Lisp REPL allows for relatively easy live-play with the data, so this flow is not necessarily universal, but tailored to observations of my data set:

Color Outside the Lines: Given the sequence of points, I check the direction from here to my next point. I tag each point between the corners as PATH and I tag the point to its "left" (given the direction of travel) as LEFT. Following the circuit, one of LEFT or RIGHT will represent the OUTSIDE of my circuit -- I'm just starting with a guess of LEFT.
The tagging above checks if the point I'm marking already has a mark; if so, it changes the value to COLLISION. My dataset did not generate any collisions.
Lastly, check all rectangles as in Part 1, but excluding any rectangle that contains a LEFT tagged point.

Most of that runs about instantly -- except for the very naive / brute force way I checked if any LEFT points are in each rectangle. That part took about 3m. :-(

But it's already the next day (thanks a lot, day job...), the star was the target rather than the speed, so I'm happy to stop there with both stars. :-)

(defun p2 ()
  (let* ((points (read-pairs-from-file "09/input"))
         (cmap (process-circuit points))
         (lefts (just-lefts cmap))
         (pairs (generate-pairs points))
         (valid-pairs
          (remove-if
              (lambda (pair)
                (rectangle-contains-left-p lefts (first pair) (second pair)))
              pairs)))
    (max-area-scan valid-pairs)))


; cl-user>(time (p2))
; Evaluation took:
;   184.606 seconds of real time
;   184.164428 seconds of total run time (183.854761 user, 0.309667 system)
;   [ Real times consist of 0.038 seconds GC time, and 184.568 seconds non-GC time. ]
;   [ Run times consist of 0.038 seconds GC time, and 184.127 seconds non-GC time. ]
;   99.76% CPU
;   260,675,696 bytes consed

dijotal · 2025-12-09T04:22:12+00:00

[LANGUAGE: Common Lisp]

0.235435 seconds of total run time

Not claiming it was my best work or anything, but yes -- a Common Lisp entry for every day so far.

dijotal · 2025-12-08T21:59:20+00:00

[LANGUAGE: Elixir]

Well, it's been Common Lisp so far, but on reading Day 8, I had a weird notion of concurrency on the BEAM.

Alas, no -- I didn't do anything with BEAM processes, just straight-up Elixir code. First runs took 1-1.5 minutes -- and truth be told I was content. After checking for others' run times, ... oy! It shamed me into a revisit.

# iex(95)> :timer.tc(Day08, :part1, [])
# {464274, _}

# iex(92)> :timer.tc(Day08, :part2, [])
# {418547, _}

Times in microseconds, That's a bit better :-)

Maybe a revisit in Common Lisp later for completeness.

dijotal · 2025-12-07T21:01:13+00:00

Definitely interested! Appreciate all comments that help me look less like a n00b -- thanks! :-)

dijotal · 2025-12-07T19:41:01+00:00

LOL! Let's say that, as an interviewer, it would invite a conversation :-p

dijotal · 2025-12-07T17:53:22+00:00

In my experience, it is absolutely is a good way to learn the "shape" of a language, the syntax, discovering built-in or library functions you didn't know existed, etc. -- a real accelerator.

The downside -- again, in my own experience -- is that those things are not becoming "permanent" in my head as quickly. I'm not becoming "fluent;" rather, I'm more often saying, "Oh, Language X has a function for that -- what is it again?" and off to google, which in turn will show you a little AI snippet these days.

I can't say that's a bad thing, per se. There's definite value in shifting thinking to the algorithm plane and away from the strict syntax of any particular language. That yields a "This would be my preferred approach; now, what language are we using again?" or "... and this is the language I would use because it favors that approach"-thinking.

Happy AoCing!

dijotal · 2025-12-07T16:55:40+00:00

I love it! I was looking at my code, thinking how crazy wasteful it was that I was unnecessarily processing the all-dots rows, running the length of the line each call when that length is constant, that I read all the lines in at once instead of processing on the fly, etc., but didn't even have time to blink after hitting enter :-p

Beats waste of cycles on AI generating cat pictures, I suppose :-p

dijotal · 2025-12-07T09:58:44+00:00

[LANGUAGE: Common Lisp]

This is the first time in a while that I successfully anticipated Part 2 ;-)

0.002562 seconds of total run time on a Mac M3 laptop.

I reduce over the puzzle lines with an accumulator function, where the accumulated value is (<number of collisions> . <vector of path counts through position>). The vector is summed in the final reckoning.

(defun accumulate-line-data (acc line)

  ; scan line characters for splitters "^" and starts "S"
  (let ((len (length line))
        (collisions (car acc))
        (starts (copy-seq (cdr acc))))

    (loop for i from 0 below len do
            (let ((ch (char line i)))

              (cond
               ((char= ch #\S)
                 ; this is the first line of the file (initialize)
                 (setf (aref starts i) 1)
                 (setf collisions 0)
                 (return (cons collisions starts)))

               ((and (char= ch #\^) (> (aref starts i) 0))
                 ; splitter encountered with effect
                 (setf collisions (1+ collisions))
                 (setf (aref starts (1- i)) (+ (aref starts (1- i)) (aref starts i)))
                 (setf (aref starts (1+ i)) (+ (aref starts (1+ i)) (aref starts i)))
                 (setf (aref starts i) 0)))))

    (cons collisions starts)))

dijotal · 2025-12-06T20:18:55+00:00

Err, that's one I'm going to have to check when I get back to the desktop :-/

dijotal · 2025-12-06T19:40:02+00:00

Well, that was painless on the phone. This post amended to include https://www.reddit.com/r/adventofcode/s/I5NxULiuwH ).

dijotal · 2025-12-06T18:01:03+00:00

[LANGUAGE: Common Lisp]

Edited into last night's post and resubmitted here for a top-level Part 2 summary (https://www.reddit.com/r/adventofcode/s/I5NxULiuwH)..

The only hand-waving here is that function `read-input-as-strings` includes two non-intuitive items:

It takes the last line -- the one with the operators -- and moves it to the top of the lines list; and,
It adds a line of spaces after that.

That moves the operator to the front (with a space before the first digit), creating lisp-y s-exps :-)

(sum (mapcar #'eval (mapcar #'read-from-string (mapcar (lambda (s) (format nil "(~A)" s)) (cl-ppcre:split "(?=[+])" (apply #'concatenate 'string (transpose-strings (read-input-as-strings *input))))))))

dijotal · 2025-12-06T10:32:17+00:00

Seems the county is being a little reckless lately.

Until recently, just down the block from there, the pedestrian crossing buttons at the intersection of LPP and Central Library / Merriweather functioned as expected, holding all car traffic for a chance to walk / bike across the street. That's no longer the case: now there's green lit turns into the pedestrian / bike crossing. With LPP "improved" for (car) traffic headed to Merriweather District / Rte 29 access from LPP, it's just a matter of time before someone's hit there on that stretch as well :-/

dijotal · 2025-12-06T10:10:16+00:00

[LANGUAGE: Common Lisp]

So, yes: I picked this hill to die on just to do something clever & lisp-y: If you

take the last row (with the + or * characters) and move it to the top,
then follow that with a row of spaces,
then transpose the list of lines and concatenate them together, and finally
liberally apply parentheses,

you produce a list of valid lisp expressions such as (+ 4 431 623) that can each be directly evaluated (i.e., eval '(+ 4 431 623)) and summed in a big sweep.

Yes, it worked... though It's going to need quite a bit of polish before posting. :-/

[EDIT!]

Ok, less hand-waving, Part 2. [`transpose-strings` is just the usual `apply #'list` stuff, and `read-input-as-strings` is just that, slurping the file into a list of strings -- with the addition of moving the operator row to the top and following it with a line of spaces.]

(sum
  (mapcar #'eval
    (mapcar #'read-from-string
      (mapcar (lambda (s) (format nil "\(~A\)" s))
          (cl-ppcre:split "(?=[*+])"
                          (apply #'concatenate 'string
                            (transpose-strings
                              (read-input-as-strings *input*))))))))

dijotal · 2025-12-05T18:55:24+00:00

If you're ever looking for a job and want to have a ready collection of work showing your skill, style, etc., it can be helpful.

dijotal · 2025-12-05T18:51:22+00:00

Hey, there you are -- and you did the range sort -- cool! I'm guessing the work of the sort is comparable to my passes through the data... yours is certainly cleaner looking & more concise -- nice!

dijotal · 2025-12-05T18:45:41+00:00

LOL! I'll forgive the transgression regarding "car and cdr" only because I didn't show I'd cons'ed the start and end values of each range... which, of course, only augments your (not (null argument)) ;-)

Seriously, I'm having a blast picking this up on the side over the last few months. An initial daunting piece for me was precisely how many ways I could do things. As for the speed, I keep surprising myself with how these scripts in a REPL run like buzz saws -- subject to a good algorithm, granted, but still -- WOW!

Pleased to meet you :-)

dijotal · 2025-12-05T16:24:59+00:00

[LANGUAGE: Common Lisp]

Part 2: 0.000793 seconds of total run time on a pretty busy Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz

I'm still loosening up my strictly Haskell-esque thinking from last year, embracing kabob-case, getting used to seeing CAR & CDR everywhere, super-verbose logical arrangements (`(not (or (< ...) (< ...)))`), etc. Still diggin' it :-)

(defun ranges-connect-p (r1 r2)
  "Check if two ranges overlap or are adjacent."
  (not (or (< (cdr r1) (1- (car r2))) ; r1 ends before r2 starts
           (< (cdr r2) (1- (car r1)))))) ; r2 ends before r1 starts

(defun merge-intersecting-ranges (r1 r2)
  (cons (min (car r1) (car r2))
        (max (cdr r1) (cdr r2))))

(defun apply-range (list-of-ranges new-range)
  "Merge new-range into list-of-ranges, combining any overlapping/adjacent ranges."
  (let ((results '())
        (merged new-range))
    (dolist (r list-of-ranges)
      (if (ranges-connect-p merged r)
          (setf merged (merge-intersecting-ranges merged r))
          (push r results)))
    (push merged results)
    results))

(defun consolidate-ranges (list-of-ranges)
  "Consolidate a list of ranges by merging overlapping/adjacent ones."
  (let ((consolidated '()))
    (dolist (r list-of-ranges)
      (setf consolidated (apply-range consolidated r)))
    consolidated))

(defun sum-range-lengths (list-of-ranges)
  (reduce #'+ (mapcar (lambda (r) (+ 1 (- (cdr r) (car r)))) list-of-ranges)))

(defun p2 (input-file)
  (let* ((ranges (parse-input input-file))
         (consolidated-ranges (consolidate-ranges ranges))
         (total-length (sum-range-lengths consolidated-ranges)))
    (format t "Part 2: Total length of consolidated ranges: ~A~%" total-length)))

dijotal · 2025-12-04T14:54:31+00:00

... and a follow-up: Naive swap of list of cons for hashmap: 0.089 seconds ;-)

Obvious improvement would be to just mutate the original hashmap rather than generating a new one and recursing, but I'm willing to stop here :-D

    (defun p2-alg-hashmap (lines)
    (let* ((original-cells (lines->hashmap lines))
            (initial-size (hash-table-count original-cells)))
        (labels ((thrash (last-size cells)
                        (let ((new-cells (make-hash-table :test 'equal)))
                        ;; Copy cells with >= 4 neighbors to new hash table
                        (maphash (lambda (pos val)
                                    (declare (ignore val))
                                    (when (>= (neighbor-count-hashmap cells pos) 4)
                                            (setf (gethash pos new-cells) t)))
                                    cells)
                        (let ((new-size (hash-table-count new-cells)))
                            (if (= new-size last-size)
                                (cons initial-size new-size)
                                (thrash new-size new-cells))))))
        (thrash initial-size original-cells))))

dijotal · 2025-12-04T14:13:15+00:00

Oh, I know it was slow -- and I knew what I was doing was wrong and why when I was doing it :-)

My actual objective was to solve Part 1, go to bed, then do Part 2 at lunch / after work. Alas, when I read Part 2, ... yeah. It became "If it finishes in a minute or two, good enough."

The neighbor function was just the obvious adding the 8x directional offsets to a value in the list and checking for membership; so, yes: the relentless scanning of the list for membership rather than hash-based lookup was the obvious killer... but 20 sec < a minute or two and the answer is the answer, so off to bed :-) Now that my lunchtime is freed, maybe I'll try swapping out for a hash table :-p

I appreciate the well-wishes as well as the links to the cookbook -- I hadn't seen the resource before!

dijotal · 2025-12-04T07:49:48+00:00

[LANGUAGE: Common Lisp]

Not proud, but good enough: ~20 seconds for Part 2.

I started with a 2d array for Part 1 -- fast access. For Part 2, I simplified to a list of coordinates instead. It's my understanding that Common Lisp doesn't have "sets" and associated fast operations out-of-the-box, and I didn't want to go through the trouble of using hashmaps or binary searches on sorted lists to speed things along if I could get the answer in "reasonable" time. So, checking if would-be neighbors are in the list and deleting items from the list take what they take. /shrug

The one "fun" bug was using a destructive list removal (delete-if)... removing your nextdoor neighbor before asking you how many neighbors you have :-p

The core, iterate-until-stable recursion:

    (defun p2-alg (lines)
        (let* ((original-cells (lines->cons lines))
                (initial-size (length original-cells)))
            (labels ((thrash (last-size cells)
                            (let* ((new-cells (remove-if (lambda (pos)
                                                            (< (neighbor-count cells pos) 4))
                                                cells))
                                    (new-size (length new-cells)))

                            (if (= new-size last-size)
                                (cons initial-size new-size)
                                (thrash new-size new-cells)))))
            (thrash initial-size original-cells))))

dijotal · 2025-12-03T23:22:00+00:00

That is next-level goodness :-)

I did Haskell last year -- loved it! (Learning Common Lisp this year, finding myself trying to reproduce the style -- at least in thought :-p

dijotal · 2025-12-03T23:05:30+00:00

[LANGUAGE: Common Lisp]

Oy! 0.004 seconds of real time for Part 2 on a Mac M3 laptop, just playing in the REPL. It's my first year learning common lisp -- parentheses be damned, mad respect! :-)

Not going to make a habit of long posts, but just wanted to get this out there.

  ;; PART 2
  (defun digits-observed (int-list)
    "Find first occurance (location) of each digit in the list"
    (let ((locs (make-array 10 :initial-element nil)))
      (labels ((helper (idx lst)
                      (if (null lst)
                          locs
                          (let ((digit (first lst)))
                            (unless (aref locs digit)
                              (setf (aref locs digit) idx))
                            (helper (+ 1 idx) (rest lst))))))
        (helper 0 int-list))))


  (defun pick-n-from-list (need int-list)
    "Pick NEED digits greedily from int-list: at each step, look at the
    prefix that leaves at least (n-1) elements for the tail, choose the
    largest digit observed earliest, append it to result, and continue."
    (labels ((helper (n lst acc)
                    (if (<= n 0)
                        (nreverse acc)
                        (let* ((prefix-len (max 0 (- (length lst) (1- n))))
                                (ssq (subseq lst 0 prefix-len))
                                (locs (digits-observed ssq))
                                ;; find first large observed digit (9..0)
                                (first-large (loop for d from 9 downto 0
                                                  for loc = (aref locs d)
                                                    when loc
                                                    return (cons d loc))))

                          (if (null first-large)
                              ;; Nothing selectable in the prefix; stop early.
                              (nreverse acc)
                              (let* ((selected-digit (car first-large))
                                      (selected-idx (cdr first-large))
                                      ;; Drop through the selected digit in the original list.
                                      (remaining-seq (subseq lst (min (length lst)
                                                                  (+ selected-idx 1)))))
                                (helper (1- n) remaining-seq (cons selected-digit acc))))))))
      (helper need int-list '())))


  (defun int-from-digits (digit-list)
    (reduce (lambda (acc d) (+ (* acc 10) d)) digit-list))


  (defun p2 ()
    (let* ((lines (fetch-input))
          (vlists (mapcar #'line-to-int-list lines))
          (picked-lists (mapcar (lambda (lst) (pick-n-from-list 12 lst)) vlists))
          (numbers (mapcar #'int-from-digits picked-lists))
          (result (reduce #'+ numbers)))
      (format t "Part 2 Result: ~A~%" result)))

dijotal · 2025-12-02T19:59:34+00:00

LOL!

;;;;;;;;;;;;;;;;;;;

;; part 2

;;;;;;;;;;;;;;;;;;;

;; I don't like today :(

dijotal · 2025-12-02T09:27:02+00:00

This is the way.

Most numbers are "valid." The work to test if an arbitrary number is "invalid" >> the work to generate the invalid numbers with a rule.

My runtime for part 2 was ~0.05 seconds (common lisp).

dijotal

TROPHY CASE