🎄⌨️ Advent of Code 2018

#lang racket

(require rackunit)

(define input (string-trim (file->string "day05-input.txt")))

(define (ascii-vector str)
  (list->vector (map char->integer (string->list str))))

(define input-vec (ascii-vector input))

(define (ascii-at-pos str i)
  (char->integer (list-ref (string->list str) i)))

;; The ASCII values of characters of alternating case ("aA" or "Gg") will always differ by 32
;; Return the first such occurrence or "" if none exists
(define (first-alternating-case str)
  (or
   (for/first ([i (in-range (sub1 (string-length str)))]
               #:when (= 32 (abs (- (ascii-at-pos str i)
                                    (ascii-at-pos str (add1 i))))))
              (substring str i (+ i 2)))
   ""))

;; Eliminate the first pair of characters that differ only in case
(define (next-transformation str)
  (or (string-replace str (first-alternating-case str) "") str))

;; Vector versions
(define (next-nonzero vec i)
  (or 
   (for/first ([n (in-range (min (add1 i) (vector-length vec)) (vector-length vec))]
               #:when (positive? (vector-ref vec n)))
              n)
   i))

(define (vec-first-alternating-case vec)
  (or 
   (for/first ([i (in-range (vector-length vec))]
               #:when (and (positive? (vector-ref vec i))
                           (= 32 (abs (- (vector-ref vec i)
                                         (vector-ref vec (next-nonzero vec i)))))))
              (list i (next-nonzero vec i)))
   '()))

(define (vec-next-transform! vec)
  (define next-pair (vec-first-alternating-case vec))
  (cond
    [(not (empty? next-pair))
     (for ([i (in-list next-pair)])
          (vector-set! vec i 0))
     #t]
    [else #f]))

;; Keep transforming as above until there's nothing left to do
(define (boil str)
  (for/fold ([last-state ""]
             [current-state str]             
             #:result current-state)
            ([x (in-naturals)]
             #:break (string=? current-state last-state))
    (values current-state (next-transformation current-state))))

;; Let's see if vectors are faster
(define (vector-boil vec)
  (do ([xformed? (vec-next-transform! vec) (vec-next-transform! vec)])
    [(not xformed?)] ))

;; I ran this function and started eating a bowl of chili.
;; When I was done with the chili it hadn't completed yet.
(define (day01-part1-try1)
  (string-length (boil input)))

(define (ascii-vector->string vec)
  (list->string (map integer->char (vector->list (vector-filter positive? vec)))))

(define (day01-part1-try2)
  (vector-boil input-vec)
  (vector-length (vector-filter positive? input-vec)))

(module+ test
  (check-equal? (boil "dabAcCaCBAcCcaDA") "dabCBAcaDA")

  ;; Takes about 64sec on my laptop
  (check-equal? (time (day01-part1-try2)) 10584)) ; Correct answer for part one

#lang racket

(require rackunit sugar/debug)

;; For efficiency and convenience, I'll be dealing with inputs as ASCII values.
(define (ascii-list str)
  (map char->integer (string->list str)))

(define input (ascii-list (string-trim (file->string "day05-input.txt"))))

;; Treating lst as a stack, push an ASCII value on top.
;; If the new value is the same letter as the current top value
;; but differs by upper/lower case, eliminate both values.
(define (push-and-react lst val)
  (cond
    [(empty? lst) (list val)]
    [(= 32 (abs (- (car lst) val))) (rest lst)]
    [else (cons val lst)]))

;; Return a fully "reacted" version of the input list.
;; Reverses the list in the process, but the order of the finished
;; list does not matter for the solution, only the length.
(define (boil lst)
  (for/fold ([output '()])
            ([v (in-list lst)])
    (push-and-react output v)))

;; There it is: computes in 6msec!
(define (day05-part1)
  (length (boil input)))

(module+ test
  (define example-input (ascii-list "dabAcCaCBAcCcaDA"))
  (check-equal? (length (boil example-input)) 10)
  (check-equal? (day05-part1) 10584)) ; Correct answer for part one

;; Given a list and the ASCII value of an uppercase letter, first removes
;; all occurrences of that letter (both upper- and lower-case) then
;; boils the resulting list as above.
(define (remove-and-boil lst uc-asciival)
  (define (keeper? a)
    (not (member a (list uc-asciival (+ 32 uc-asciival)))))
  (boil (filter keeper? lst)))

;; For each letter of the alphabet, create a copy of input that first removes that
;; letter, then boils the list. Find the shortest such list.
;; Computes in about 550msec
(define (day05-part2)
  (define uc-letters (range 65 91))
  (define boiler (curry remove-and-boil input))
  (define boiled (map boiler uc-letters))
  (apply min (report (map length boiled))))

(module+ test
  (check-equal? (day05-part2) 6968))

;; This next has nothing to do with the solution; I was just curious which is the most
;; common letter in the original input, and if it was the removal of that letter
;; which yields the shortest boiled list. As it turns out: no.
(define (most-frequent-letter)
  (define (count-letter lst a)
    (count (lambda(c) (member c (list a (+ a 32)))) lst))
  (define letter-counts
    (map (curry count-letter input) (range 65 91)))
  (integer->char (+ 65 (index-of (report letter-counts) (apply max letter-counts)))))