From 8f3ad5d907eeffc558d11639eea7e27dcdfe7b0b Mon Sep 17 00:00:00 2001 From: Jack Kinsey Date: Sat, 14 Dec 2024 18:35:55 -0500 Subject: [PATCH] Complete day 13 part 2 --- src/day13.rs | 242 ++++++++++++++++++++++++++++----------------------- 1 file changed, 134 insertions(+), 108 deletions(-) diff --git a/src/day13.rs b/src/day13.rs index 532ff4c..8e0d7f6 100644 --- a/src/day13.rs +++ b/src/day13.rs @@ -2,34 +2,9 @@ use regex::Regex; use std::ops::{Add, Sub}; #[derive(Debug, Hash, Eq, PartialEq, Copy, Clone)] -struct Point(i32, i32); - -#[rustfmt::skip] -const DIRS: [Point; 4] = [ - Point(-1, 0), - Point(0, -1), /* ctr */ Point(0, 1), - Point( 1, 0), -]; +struct Point(i64, i64); impl Point { - fn in_bounds(&self, bound: usize) -> bool { - let bound: i32 = bound.try_into().unwrap(); - self.0 >= 0 && self.1 >= 0 && self.0 < bound && self.1 < bound - } - - fn adjacent(self, bound: usize) -> impl Iterator { - self.adjacent_unchecked() - .filter(move |p| p.in_bounds(bound)) - } - - fn adjacent_unchecked(self) -> impl Iterator { - DIRS.iter().copied().map(move |d| self + d) - } - - fn scale(&self, multiplier: i32) -> Point { - Point(self.0 * multiplier, self.1 * multiplier) - } - fn cost(&self) -> u64 { (self.0 * 3 + self.1).try_into().unwrap() } @@ -71,63 +46,104 @@ fn parse(input: &str) -> Vec { .collect() } -#[derive()] -struct ButtonSeq { - curr: Option, -} - -impl ButtonSeq { - fn new() -> Self { - ButtonSeq { curr: None } - } -} - -impl Iterator for ButtonSeq { - type Item = Point; - - fn next(&mut self) -> Option { - self.curr = match self.curr { - None => Some(Point(0, 1)), - Some(Point(a, b)) if b < 3 => Some(Point(0, 3 * a + b + 1)), - Some(Point(a, b)) => Some(Point(a + 1, b - 3)), - }; - self.curr - } -} - impl Game { - fn check_win(&self, seq: Point) -> bool { - self.0.scale(seq.0) + self.1.scale(seq.1) == self.2 + fn solve_lin(&self) -> Option { + // solve as a system of equations: + // (must be linearly independent) + // g0*a + g1*b = g2 + // ax*a + bx*b = cx + // ay*a + by*b = cy + // -> a = (cy*bx - cx*by) / (ay*bx - ax*by) + // -> b = (cy*ax - cx*ay) / (by*ax - bx*ay) + let an = self.2 .1 * self.1 .0 - self.2 .0 * self.1 .1; + let ad = self.0 .1 * self.1 .0 - self.0 .0 * self.1 .1; + let bn = self.2 .1 * self.0 .0 - self.2 .0 * self.0 .1; + let bd = self.1 .1 * self.0 .0 - self.1 .0 * self.0 .1; + let (a, ar) = (an / ad, an % ad); + let (b, br) = (bn / bd, bn % bd); + // if a result isn't an integer, or is negative, no solution + // watch out for negative remainders!--(-n % -m) can be negative + if ar == 0 && br == 0 && a > 0 && b > 0 { + Some(Point(a, b)) + } else { + None + } } - fn find_min_winning(&self) -> Option { - ButtonSeq::new().find(|&seq| self.check_win(seq)) + // FIXME: not actually necessary to solve the puzzle, somehow + // fn solve_single(&self) -> Vec { + // // find all solutions to a single two-variable equation + // // (assuming the system formed by the game is not linearly independent + // // and using the equation with smaller factors) + // let ax = self.0 .0.min(self.0 .1); + // let bx = self.1 .0.min(self.1 .1); + // let cx = self.2 .0.min(self.2 .1); + // // ax*a + bx*b = cx + // let mut seqs = vec![]; + // // set a = 0 + // let (b0, br0) = (cx / bx, cx % bx); + // if br0 == 0 { + // seqs.push(Point(0, b0)); + // } + // // set b = 0 + // let (a0, ar0) = (cx / ax, cx % ax); + // if ar0 == 0 { + // seqs.push(Point(a0, 0)); + // } + // seqs + // } + + fn find_winning(&self) -> Option { + let (an, ad) = (self.0 .0.max(self.0 .1), self.0 .0.min(self.0 .1)); + let (ak, ar) = (an / ad, an % ad); + let (bn, bd) = (self.1 .0.max(self.1 .1), self.1 .0.min(self.1 .1)); + let (bk, br) = (bn / bd, bn % bd); + let (cn, cd) = (self.2 .0.max(self.2 .1), self.2 .0.min(self.2 .1)); + let (ck, cr) = (cn / cd, cn % cd); + // the points don't form a linearly independent system of equations; there are potentially + // multiple solutions + if ak == bk && bk == ck && ar == 0 && br == 0 && cr == 0 { + // FIXME: but, this doesn't happen in the puzzle input + // let mut seqs = self.solve_single(); + // seqs.sort_by_key(|p| p.cost()); + // seqs.first().copied() + unreachable!() + } else { + self.solve_lin() + } } - fn find_min_winning_dumb(&self) -> Option { - let mut opts: Vec<_> = (0..=100) - .flat_map(move |i| (0..=100).map(move |j| Point(i, j))) - .skip(1) - .filter(|&p| self.check_win(p)) - .collect(); - opts.sort_by_key(|p| p.cost()); - opts.first().copied() + fn find_winning_corrected(&self) -> Option { + let error = 10_000_000_000_000i64; + let check = Game(self.0, self.1, self.2 + Point(error, error)); + check.find_winning() } } pub fn part1(input: &str) -> u64 { parse(input) .iter() - .map(|g| g.find_min_winning_dumb()) - .map(|s| s.map(|s| s.cost()).unwrap_or_default()) + .flat_map(|g| g.find_winning()) + .map(|s| s.cost()) .sum() } pub fn part2(input: &str) -> u64 { parse(input) .iter() - .map(|g| g.find_min_winning()) - .map(|s| s.map(|s| s.cost()).unwrap_or_default()) + .inspect(|&g| { + let (an, ad) = (g.0 .0.max(g.0 .1), g.0 .0.min(g.0 .1)); + let (ak, ar) = (an / ad, an % ad); + let (bn, bd) = (g.1 .0.max(g.1 .1), g.1 .0.min(g.1 .1)); + let (bk, br) = (bn / bd, bn % bd); + if ak == bk && ar == 0 && br == 0 { + // this doesn't actually happen + println!("{:?}", g); + unreachable!(); + } + }) + .flat_map(|g| g.find_winning_corrected()) + .map(|s| s.cost()) .sum() } @@ -166,61 +182,72 @@ mod test { ) } - #[rustfmt::skip] #[test] - fn test_buttonseq() { + fn test_find_winning() { assert_eq!( - ButtonSeq::new().take(21).collect::>(), - [ - // Point(0, 0), -- excluded - Point(0, 1), - Point(0, 2), - Point(0, 3), Point(1, 0), - Point(0, 4), Point(1, 1), - Point(0, 5), Point(1, 2), - Point(0, 6), Point(1, 3), Point(2, 0), - Point(0, 7), Point(1, 4), Point(2, 1), - Point(0, 8), Point(1, 5), Point(2, 2), - Point(0, 9), Point(1, 6), Point(2, 3), Point(3, 0), - ] + Game(Point(94, 34), Point(22, 67), Point(8400, 5400)).find_winning(), + Some(Point(80, 40)) + ); + assert_eq!( + Game(Point(26, 66), Point(67, 21), Point(12748, 12176)).find_winning(), + None + ); + assert_eq!( + Game(Point(17, 86), Point(84, 37), Point(7870, 6450)).find_winning(), + Some(Point(38, 86)) + ); + assert_eq!( + Game(Point(69, 23), Point(27, 71), Point(18641, 10279)).find_winning(), + None ); - let table = [ - (Point(32, 3), Point(33, 0)), - (Point(33, 0), Point(0, 100)), - (Point(33, 1), Point(1, 98)), - (Point(33, 2), Point(1, 99)), - (Point(34, 0), Point(1, 100)), - (Point(34, 1), Point(2, 98)), - (Point(34, 2), Point(2, 99)), - (Point(35, 0), Point(2, 100)), - // ... skip a bit ... - // (Point(98, 0), Point(66, 100)), - // (Point(99, 0), Point(66, 100)), - ]; - for (curr, next) in table { - assert_eq!(ButtonSeq { curr: Some(curr) }.next(), Some(next)); - } + // FIXME: this is a genuine edge case but it doesn't show up in the input so i'm ignoring it + // // Thanks Claude + // assert_eq!( + // Game(Point(2, 4), Point(3, 6), Point(12, 24)).find_min_winning(), + // Some(Point(0, 4)) + // ); + // // I came up with these ones though + // assert_eq!( + // Game(Point(2, 4), Point(3, 6), Point(17, 34)).find_min_winning(), + // Some(Point(1, 5)) + // ); + // assert_eq!( + // Game(Point(3, 6), Point(5, 10), Point(18, 36)).find_min_winning(), + // Some(Point(1, 3)) + // ); + // assert_eq!( + // Game(Point(5, 10), Point(3, 6), Point(18, 36)).find_min_winning(), + // Some(Point(0, 6)) + // ); + // assert_eq!( + // Game(Point(2, 4), Point(3, 6), Point(24, 48)).find_min_winning(), + // Some(Point(0, 8)) + // ); + // assert_eq!( + // Game(Point(3, 6), Point(2, 4), Point(24, 48)).find_min_winning(), + // Some(Point(0, 12)) + // ); } #[test] - fn test_find_min_winning() { - assert_eq!( - Game(Point(94, 34), Point(22, 67), Point(8400, 5400)).find_min_winning(), - Some(Point(80, 40)) - ); + fn test_find_winning_corrected() { assert_eq!( - Game(Point(26, 66), Point(67, 21), Point(12748, 12176)).find_min_winning(), + Game(Point(94, 34), Point(22, 67), Point(8400, 5400)).find_winning_corrected(), None ); assert_eq!( - Game(Point(17, 86), Point(84, 37), Point(7870, 6450)).find_min_winning(), - Some(Point(38, 86)) + Game(Point(26, 66), Point(67, 21), Point(12748, 12176)).find_winning_corrected(), + Some(Point(118679050709, 103199174542)) ); assert_eq!( - Game(Point(69, 23), Point(27, 71), Point(18641, 10279)).find_min_winning(), + Game(Point(17, 86), Point(84, 37), Point(7870, 6450)).find_winning_corrected(), None ); + assert_eq!( + Game(Point(69, 23), Point(27, 71), Point(18641, 10279)).find_winning_corrected(), + Some(Point(102851800151, 107526881786)) + ); } #[test] @@ -234,8 +261,7 @@ mod test { } #[test] - #[ignore] fn test_part2() { - assert_eq!(part2(&crate::input(13).unwrap()), 0) + assert_eq!(part2(&crate::input(13).unwrap()), 79352015273424) } } -- 2.38.5