Advent of Code 2025 Discussions

General
1

Hello all!

Thread to post Advent of Code solutions and discussions around them. For day 1 I am pretty happy with most of my solution, except that I have this function:

(define field-size 100)

(define (zero-crossings initial-position delta)
  (+
   (- (abs (quotient (+ initial-position delta) field-size))
      (abs (quotient initial-position field-size)))
   (if (or
        (= initial-position 0)
        (= (sgn initial-position) (sgn (+ initial-position delta))))
       0
       1)))

It's is pretty hard to follow what is happening there. Did anyone think of a better way of doing this?

1 Like
2

Hi, @felipetavares!

Happy advent.

Yours is pretty compact, well done.

I came up with this, as another data point:

(define (rotate/count-zeros pointer turn)
  (define-values (rotations leftover) (quotient/remainder turn full-rotation))
  (define result (+ pointer leftover))
  (define zeroes
    (case (sgn leftover)
      [(-1)
       (if (and (<= result 0) (< 0 pointer))
           (+ (- rotations) 1)
           (- rotations))]
      [(+1)
       (if (<= full-rotation result)
           (+ rotations 1)
           rotations)]
      [else
       (abs rotations)]))
  (values
   (modulo result full-rotation) zeroes))
2 Likes
3

Oh that's a much nicer idea IMO. Now wondering if that is a stepping stone for a nice closed form solution :thinking:

4

This is the best I could do, inverting a bit of the logic of when I count when it ends up in a zero:

(define (zero-crossings initial-position delta)
    (+
     (abs (quotient delta field-size))
     (let ([final-position (+ initial-position (remainder delta field-size))])
       (if (or (< final-position 0)
               (> final-position field-size)
               (zero? initial-position))
           1 0))))

EDIT: which is larger than my original one, but somehow I find this much more readable.

1 Like
5

I gave up on figuring out a formula for part 2 based on integer division after a few failed attempts and ended up just simulating turning the dial a click at a time via brute force. I'm not proud but it worked.

(define (part2 instructions)
  (define (spin-the-dial dial distance)
    (define delta (if (positive? distance) 1 -1))
    (let loop ([dial dial]
               [distance distance]
               [zeros 0])
      (cond
        [(zero? distance) (values dial zeros)]
        [else
         (define new-pos (acase (+ dial delta)
                           [(-1) 99]
                           [(100) 0]
                           [else it]))
         (loop new-pos (- distance delta) (if (zero? new-pos) (add1 zeros) zeros))])))
  (for/fold ([zero-count 0]
             [dial 50]
             #:result zero-count)
            ([distance (in-list instructions)])
    (define-values (new-pos zeros) (spin-the-dial dial distance))
    (values (+ zero-count zeros) new-pos)))

Part 1 was a lot simpler:

(define (part1 instructions)
  (for/fold ([zero-count 0]
             [dial 50]
             #:result zero-count)
            ([distance (in-list instructions)])
    (define new-pos (modulo (+ dial distance) 100))
    (values (if (zero? new-pos) (add1 zero-count) zero-count) new-pos)))

Not shown: Parsing the input into a list of numbers (R50 -> 50, L12 -> -12, etc.), and the definition of that anaphoric acase macro, which I tossed in because I wanted at least something clever.

2 Likes
6

Today I went full brute force, not sure if there was a much better solution I completely missed? Something with prime decomposition of string lengths?

(define (check-id id)
  (let ([len (string-length id)])
    (for/or ([step (in-inclusive-range 1 (/ len 2))])
      (if (zero? (remainder len step))
        (for/and ([idx (in-range step len step)])
          (equal? (substring id 0 step) (substring id idx (+ idx step))))
        #f))))

(define (check num-range)
  (for/list ([id (in-inclusive-range (first num-range) (second num-range))])
    (if (check-id (number->string id)) id 0)))
7

I used Common Lisp instead of Racket for today's problem, but the equivalents to some things I did in it:

string= from the srfi/13 string library lets you compare sections of strings, avoiding the need for substring and saving the garbage collector from a lot of extra work.

The maximum length of a string representation of the numbers in the puzzle input is something like 10 characters. For part 2, it's trivial to create a pre-defined set of possible lengths of subsequences of the strings and use them instead of always looping through a range and repeatedly figuring out which numbers work. For example, an 8 digit number can have subsequences of length 1, 2 or 4. I just had a vector of lists of those lengths and only checked against the appropriate one ((for/or ([len (in-list (vector-ref groupings (string-length num)))]) (repeats-length-n? num len))).

2 Likes
8

Haha, why'd I use numbers?

(define (comp limit)
  (if (not limit) values (lambda (k) (= k limit))))

(define (cons=? x y)
  (if (pair? y) (and (= x (car y)) (list x)) (cons x y)))

(define (repeated-number? x #:repeat [limit #false])
  (define n (+ 1 (order-of-magnitude x)))
  (define ? (comp limit))
  (for/or ([k (in-list (divisors n))]
           #:when (and (< 1 k) (? k)))
    (define m (expt 10 (/ n k)))
    (let residues ([x x] [p null])
      (cond
        [(not p) #false]
        [else
         (define-values (q r) (quotient/remainder x m))
         (if (zero? q) (cons=? r p) (residues q (cons=? r p)))]))))
1 Like
9

@bakgatviooldoos I did start out trying to go the number route, but strings seemed too simple not to switch :stuck_out_tongue:

EDIT: math/number-theory seems very cool! Didn't know about it!

10

Today my weapon of choice was "inefficient list operations:"

(define (max-joltage n bank)
  (if (and (> n 0) (>= (length bank) n))
      (let* ([valid-len (- (length bank) (- n 1))]
             [digit (apply max (take bank valid-len))])
        (apply max
               (for/list ([i (in-inclusive-range 1 valid-len)]
                          #:when (= (last (take bank i)) digit))
                 (+
                  (* (expt 10 (- n 1)) digit)
                  (max-joltage (- n 1) (drop bank i))))))
      0))
11

Relied heavily on mutable sets for day four. For those "graphical" problems I often find the most sane (but perhaps not the most efficient) structure is just keeping a "bag of coordinates."

For example, reading the file is:

(define size
  (for/last ([row (file->lines "input")]
             [y (in-naturals)])
    (for/last ([c row]
               [x (in-naturals)])
      (when (equal? c #\@)
        (set-add! diag (cons x y)))
      (cons x y))))

The operation of removing rolls wasn't pretty, though... I relied on a couple globals for counting the number of removed items and for signaling when no further items could be removed:

(define (rm p)
  (set-remove! diag p)
  (set! removed (+ removed 1))
  (set! reduced #t))

(define (reduce)
  (set! reduced #f)
  (for ([pos diag])
    (when (< (count (curry set-member? diag) (adj (car pos) (cdr pos))) 4)
      (rm pos)))
  (when reduced (reduce)))

I really wanted a better signaling mechanism there. I wonder if there is a more idiomatic way of doing it. I think if I used immutable sets I probably could integrate it in the recursion by comparing the old set and new set directly, but with mutable sets I am not sure.