day13 solution 2

1 files changed, 37 insertions, 25 deletions

diff --git a/src/bin/day13.rs b/src/bin/day13.rs
index 965d7c0..4536aab 100644
--- a/src/bin/day13.rs
+++ b/src/bin/day13.rs
@@ -5,13 +5,13 @@ static DAY: u8 = 13;
 fn main() {
     let input = advent::read_file(DAY);
     println!("{DAY}a: {}", win_tokens(input.trim_end()));
-    println!("{DAY}b: {}", 0);
+    println!("{DAY}b: {}", win_tokens_big(input.trim_end()));
 }
 
 struct Machine {
-    button_a: (u32, u32),
-    button_b: (u32, u32),
-    prize: (u32, u32),
+    button_a: (i64, i64),
+    button_b: (i64, i64),
+    prize: (i64, i64),
 }
 
 impl Machine {
@@ -29,12 +29,12 @@ impl Machine {
         let captures_b = re_b.captures(button_b).unwrap();
         let captures_p = re_p.captures(prizes).unwrap();
 
-        let a_x = captures_a.get(1).unwrap().as_str().parse::<u32>().unwrap();
-        let a_y = captures_a.get(2).unwrap().as_str().parse::<u32>().unwrap();
-        let b_x = captures_b.get(1).unwrap().as_str().parse::<u32>().unwrap();
-        let b_y = captures_b.get(2).unwrap().as_str().parse::<u32>().unwrap();
-        let p_x = captures_p.get(1).unwrap().as_str().parse::<u32>().unwrap();
-        let p_y = captures_p.get(2).unwrap().as_str().parse::<u32>().unwrap();
+        let a_x = captures_a.get(1).unwrap().as_str().parse::<i64>().unwrap();
+        let a_y = captures_a.get(2).unwrap().as_str().parse::<i64>().unwrap();
+        let b_x = captures_b.get(1).unwrap().as_str().parse::<i64>().unwrap();
+        let b_y = captures_b.get(2).unwrap().as_str().parse::<i64>().unwrap();
+        let p_x = captures_p.get(1).unwrap().as_str().parse::<i64>().unwrap();
+        let p_y = captures_p.get(2).unwrap().as_str().parse::<i64>().unwrap();
 
         Machine {
             button_a: (a_x, a_y),
@@ -43,27 +43,39 @@ impl Machine {
         }
     }
 
-    fn lowest_prize(&self) -> Option<u32> {
-        let mut best_prize = None;
-        for a in 0 ..= 100 {
-            for b in 0 ..= 100 {
-                if (a * self.button_a.0) + (b * self.button_b.0) != self.prize.0 {
-                    continue;
-                }
-                if (a * self.button_a.1) + (b * self.button_b.1) != self.prize.1 {
-                    continue;
-                }
-                let prize = 3 * a + b;
-                best_prize = Some(best_prize.unwrap_or(u32::MAX).min(prize));
-            }
+    fn lowest_prize(&self) -> Option<i64> {
+        let dividend = (self.prize.0 * self.button_a.1) - (self.prize.1 * self.button_a.0);
+        let divisor = (self.button_b.0 * self.button_a.1) - (self.button_b.1 * self.button_a.0);
+        if divisor == 0 || (dividend % divisor != 0) {
+            return None
         }
-        best_prize
+        let b = dividend / divisor;
+
+        let dividend = self.prize.0 - (b * self.button_b.0);
+        let divisor = self.button_a.0;
+        if divisor == 0 || (dividend % divisor != 0) {
+            return None;
+        }
+        let a = dividend / divisor;
+
+        Some(3 * a + b)
     }
 }
 
-fn win_tokens(input: &str) -> u32 {
+fn win_tokens(input: &str) -> i64 {
+    input.split("\n\n")
+         .map(Machine::new)
+         .map(|machine| machine.lowest_prize().unwrap_or(0))
+         .sum()
+}
+
+fn win_tokens_big(input: &str) -> i64 {
     input.split("\n\n")
          .map(Machine::new)
+         .map(|machine| Machine {
+                            button_a: machine.button_a,
+                            button_b: machine.button_b,
+                            prize: (machine.prize.0 + 10000000000000, machine.prize.1 + 10000000000000) })
          .map(|machine| machine.lowest_prize().unwrap_or(0))
          .sum()
 }