🎄⌨️ Advent of Code 2018

day05-try1.rkt

File day05-try1.rkt from the latest check-in


#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