Merge branch 'main' of https://github.com/hunkyjimpjorps/AdventOfCode into main

2 files changed, 42 insertions, 39 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)))
diff --git a/2022/day-21/day-21.rkt b/2022/day-21/day-21.rkt
index 60ee4d8..fccd6ad 100644
--- a/2022/day-21/day-21.rkt
+++ b/2022/day-21/day-21.rkt
@@ -19,40 +19,25 @@
   (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
+;; 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"))
-
-(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))]
-            #:when (= result-1 result-2))
-  guess)
+(define known-side (evaluate-monkey branch-2))
+(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)))