ADDED day05-try1.rkt Index: day05-try1.rkt ================================================================== --- day05-try1.rkt +++ day05-try1.rkt @@ -0,0 +1,85 @@ +#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 ADDED day05.rkt Index: day05.rkt ================================================================== --- day05.rkt +++ day05.rkt @@ -0,0 +1,65 @@ +#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)))))