From 7d83fb6a52dfbb5b96b9d2de6b9e06dd78e60faa Mon Sep 17 00:00:00 2001 From: Hunky Jimpjorps Date: Wed, 21 Dec 2022 10:27:48 -0500 Subject: day 21 cleanup --- 2022/day-21/day-21.rkt | 32 +++++++++++--------------------- 1 file changed, 11 insertions(+), 21 deletions(-) diff --git a/2022/day-21/day-21.rkt b/2022/day-21/day-21.rkt index 60ee4d8..752dfb8 100644 --- a/2022/day-21/day-21.rkt +++ b/2022/day-21/day-21.rkt @@ -19,40 +19,30 @@ (for/hash ([m raw-monkeys] #:do [(match-define (monkey name op) (parse-monkey m))]) (values name op))) -(define (parse f name1 name2) +;; part 1 +(define (evaluate-monkey m-name [guess #f]) + (match-define (op f name1 name2) + (if (and guess (equal? m-name "humn")) + (op 'constant guess #f) + (hash-ref monkey-table m-name))) (match f ['constant name1] - ['+ (+ (evaluate-monkey name1) (evaluate-monkey name2))] - ['- (- (evaluate-monkey name1) (evaluate-monkey name2))] - ['* (* (evaluate-monkey name1) (evaluate-monkey name2))] - ['/ (/ (evaluate-monkey name1) (evaluate-monkey name2))])) - -;; part 1 -(define (evaluate-monkey m-name) - (match-define (op f name1 name2) (hash-ref monkey-table m-name)) - (parse f name1 name2)) + ['+ (+ (evaluate-monkey name1 guess) (evaluate-monkey name2 guess))] + ['- (- (evaluate-monkey name1 guess) (evaluate-monkey name2 guess))] + ['* (* (evaluate-monkey name1 guess) (evaluate-monkey name2 guess))] + ['/ (/ (evaluate-monkey name1 guess) (evaluate-monkey name2 guess))])) (evaluate-monkey "root") ;; part 2 (match-define (op _ branch-1 branch-2) (hash-ref monkey-table "root")) -(define (evaluate-monkey* m-name guess) - (match-define (op f name1 name2) - (if (equal? m-name "humn") (op 'constant guess #f) (hash-ref monkey-table m-name))) - (match f - ['constant name1] - ['+ (+ (evaluate-monkey* name1 guess) (evaluate-monkey* name2 guess))] - ['- (- (evaluate-monkey* name1 guess) (evaluate-monkey* name2 guess))] - ['* (* (evaluate-monkey* name1 guess) (evaluate-monkey* name2 guess))] - ['/ (/ (evaluate-monkey* name1 guess) (evaluate-monkey* name2 guess))])) - ;; the branch that doesn't depend on humn (define result-2 (evaluate-monkey branch-2)) ;; I plugged in numbers for guess to find a suitable starting range and settled on the first one ;; that I found that got me within a million (for/first ([guess (in-naturals 3059361690000)] - #:do [(define result-1 (evaluate-monkey* branch-1 guess))] + #:do [(define result-1 (evaluate-monkey branch-1 guess))] #:when (= result-1 result-2)) guess) -- cgit v1.2.3 From 3edaf521fe2102270563cf8c00bfa36b5486a7e6 Mon Sep 17 00:00:00 2001 From: Hunky Jimpjorps Date: Wed, 21 Dec 2022 15:10:19 -0500 Subject: day 21 revision --- 2022/day-21/day-21.rkt | 24 +++++++++++++----------- 1 file changed, 13 insertions(+), 11 deletions(-) diff --git a/2022/day-21/day-21.rkt b/2022/day-21/day-21.rkt index 752dfb8..9f08f97 100644 --- a/2022/day-21/day-21.rkt +++ b/2022/day-21/day-21.rkt @@ -22,9 +22,7 @@ ;; part 1 (define (evaluate-monkey m-name [guess #f]) (match-define (op f name1 name2) - (if (and guess (equal? m-name "humn")) - (op 'constant guess #f) - (hash-ref monkey-table m-name))) + (if (and guess (equal? m-name "humn")) (op 'constant guess #f) (hash-ref monkey-table m-name))) (match f ['constant name1] ['+ (+ (evaluate-monkey name1 guess) (evaluate-monkey name2 guess))] @@ -38,11 +36,15 @@ (match-define (op _ branch-1 branch-2) (hash-ref monkey-table "root")) ;; the branch that doesn't depend on humn -(define result-2 (evaluate-monkey branch-2)) - -;; I plugged in numbers for guess to find a suitable starting range and settled on the first one -;; that I found that got me within a million -(for/first ([guess (in-naturals 3059361690000)] - #:do [(define result-1 (evaluate-monkey branch-1 guess))] - #:when (= result-1 result-2)) - guess) +(define known-side (evaluate-monkey branch-2)) + +(for/fold ([lower-bound 0] [upper-bound 1e16] #:result (inexact->exact lower-bound)) + ([_ (in-naturals)]) + #:break (= lower-bound upper-bound) + (define midpoint (quotient (+ lower-bound upper-bound) 2)) + (define candidate (evaluate-monkey branch-1 midpoint)) + (println (~a midpoint " -> " candidate " -> " (- candidate known-side))) + (cond + [(= candidate known-side) (values midpoint midpoint)] + [(> candidate known-side) (values midpoint upper-bound)] + [(< candidate known-side) (values lower-bound midpoint)])) -- cgit v1.2.3 From 7fd928a370371f6aaa0b34f7f7ce63ea8c35baf2 Mon Sep 17 00:00:00 2001 From: Hunky Jimpjorps Date: Wed, 21 Dec 2022 16:16:23 -0500 Subject: day 21 simplification --- 2022/day-21/day-21.rkt | 19 ++++++------------- 1 file changed, 6 insertions(+), 13 deletions(-) diff --git a/2022/day-21/day-21.rkt b/2022/day-21/day-21.rkt index 9f08f97..fccd6ad 100644 --- a/2022/day-21/day-21.rkt +++ b/2022/day-21/day-21.rkt @@ -33,18 +33,11 @@ (evaluate-monkey "root") ;; part 2 +;; since humn only ever appears once, and it's never the divisor in a division operation, +;; the difference of the branches is linearly proportional to humn +;; therefore, if we find two points we can calculate the root directly (match-define (op _ branch-1 branch-2) (hash-ref monkey-table "root")) - -;; the branch that doesn't depend on humn (define known-side (evaluate-monkey branch-2)) - -(for/fold ([lower-bound 0] [upper-bound 1e16] #:result (inexact->exact lower-bound)) - ([_ (in-naturals)]) - #:break (= lower-bound upper-bound) - (define midpoint (quotient (+ lower-bound upper-bound) 2)) - (define candidate (evaluate-monkey branch-1 midpoint)) - (println (~a midpoint " -> " candidate " -> " (- candidate known-side))) - (cond - [(= candidate known-side) (values midpoint midpoint)] - [(> candidate known-side) (values midpoint upper-bound)] - [(< candidate known-side) (values lower-bound midpoint)])) +(define humn-zero (- known-side (evaluate-monkey branch-1 0))) +(define humn-one (- known-side (evaluate-monkey branch-1 1))) +(- (/ humn-zero (- humn-one humn-zero))) -- cgit v1.2.3 From 19db5e23c743f6dcca1f6c982f590a8cb948a126 Mon Sep 17 00:00:00 2001 From: HJ Date: Wed, 21 Dec 2022 23:30:01 -0500 Subject: 2020 day 16 progress --- 2020/day-16/day-16.rkt | 36 +++++++++++++++++++++++++++--------- 1 file changed, 27 insertions(+), 9 deletions(-) diff --git a/2020/day-16/day-16.rkt b/2020/day-16/day-16.rkt index 64271c7..9a38eda 100644 --- a/2020/day-16/day-16.rkt +++ b/2020/day-16/day-16.rkt @@ -1,6 +1,8 @@ #lang racket -(require advent-of-code +(require racket/struct + advent-of-code + fancy-app relation threading rebellion/base/range) @@ -22,13 +24,29 @@ (match-define (list (app (λ~>> make-lines (map process-rules)) ticket-rules) (app (λ~>> make-lines second seperate-fields) your-ticket) (app (λ~>> make-lines rest (map seperate-fields)) other-tickets)) - (~> (fetch-aoc-input (find-session) 2020 16) (string-split "\n\n"))) + (~> (fetch-aoc-input (find-session) 2020 16 #:cache #true) (string-split "\n\n"))) -(define (ticket-scanning-error-rate ticket rules) - (for/sum ([ticket-field (in-list ticket)] - [ticket-rule (in-list rules)] - #:do [(match-define (field-rule _ r1 r2) ticket-rule)] - #:unless (or (range-contains? r1 ticket-field) (range-contains? r2 ticket-field))) - ticket-field)) +;; part 1 +(define (fails-all-checks? field rules) + (define rule-list (~>> rules (map (λ~> struct->list rest)) flatten)) + (for/and ([rule (in-list rule-list)]) + (not (range-contains? rule field)))) -(for/sum ([ticket (in-list other-tickets)]) (ticket-scanning-error-rate ticket ticket-rules)) \ No newline at end of file +(define (ticket-scanning-error-rate tickets rules) + (for*/sum + ([ticket (in-list tickets)] (field (in-list ticket)) #:when (fails-all-checks? field rules)) + field)) + +(ticket-scanning-error-rate other-tickets ticket-rules) + +;; part 2 +(define valid-tickets (filter (ormap (fails-all-checks? _ ticket-rules) _) other-tickets)) + +(define fields (apply map list valid-tickets)) + +(for/list ([field (in-list fields)]) + (for*/list ( + [rule (in-list ticket-rules)] + #:unless (not (or (range-contains? (field-rule-range1 rule) value) + (range-contains? (field-rule-range2 rule) value)))) + (field-rule-name rule))) -- cgit v1.2.3