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(-) (limited to '2022/day-21') 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(-) (limited to '2022/day-21') 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(-) (limited to '2022/day-21') 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