adventofcode

git clone https://git.ce9e.org/adventofcode.git

commit
387fe63045a164a7ed2436df870e112ceba8e28d
parent
3853c442c3a187d57ae07d48d3c1130454d35111
Author
Tobias Bengfort <tobias.bengfort@posteo.de>
Date
2024-01-03 15:43
foo

Diffstat

A 2023/24/rational.rs 113 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A 2023/24/solution.rs 158 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 271 insertions, 0 deletions


diff --git a/2023/24/rational.rs b/2023/24/rational.rs

@@ -0,0 +1,113 @@
   -1     1 use std::fmt::Debug;
   -1     2 use std::fmt::Display;
   -1     3 use std::fmt::Formatter;
   -1     4 use std::ops::Add;
   -1     5 use std::ops::Div;
   -1     6 use std::ops::Mul;
   -1     7 use std::ops::Neg;
   -1     8 use std::ops::Sub;
   -1     9 
   -1    10 fn gcd(a: i128, b: i128) -> i128 {
   -1    11     let mut x1 = a.abs().max(b.abs());
   -1    12     let mut x2 = a.abs().min(b.abs());
   -1    13 
   -1    14     while x2 > 0 {
   -1    15         (x1, x2) = (x2, x1 % x2);
   -1    16     }
   -1    17 
   -1    18     return x1;
   -1    19 }
   -1    20 
   -1    21 #[derive(Clone, Copy)]
   -1    22 pub struct Rational {
   -1    23     pub numerator: i128,
   -1    24     pub denominator: i128,
   -1    25 }
   -1    26 
   -1    27 impl Rational {
   -1    28     fn new(numerator: i128, denominator: i128) -> Self {
   -1    29         let mut a = gcd(numerator, denominator);
   -1    30         if denominator < 0 {
   -1    31             a = -a;
   -1    32         }
   -1    33         return Self {
   -1    34             numerator: numerator / a,
   -1    35             denominator: denominator / a,
   -1    36         };
   -1    37     }
   -1    38 
   -1    39     pub fn n(i: i128) -> Self {
   -1    40         return Self::new(i, 1);
   -1    41     }
   -1    42 
   -1    43     pub fn as_f64(self) -> f64 {
   -1    44         return self.numerator as f64 / self.denominator as f64;
   -1    45     }
   -1    46 }
   -1    47 
   -1    48 impl Display for Rational {
   -1    49     fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
   -1    50         if self.denominator == 1 {
   -1    51             return write!(f, "{}", self.numerator);
   -1    52         } else {
   -1    53             return write!(f, "{}/{}", self.numerator, self.denominator);
   -1    54         }
   -1    55     }
   -1    56 }
   -1    57 
   -1    58 impl Debug for Rational {
   -1    59     fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
   -1    60         return write!(f, "{}", self);
   -1    61     }
   -1    62 }
   -1    63 
   -1    64 impl Neg for Rational {
   -1    65     type Output = Self;
   -1    66 
   -1    67     fn neg(self) -> Self {
   -1    68         return Self::new(-self.numerator, self.denominator);
   -1    69     }
   -1    70 }
   -1    71 
   -1    72 impl Add<Self> for Rational {
   -1    73     type Output = Self;
   -1    74 
   -1    75     fn add(self, other: Self) -> Self {
   -1    76         return Self::new(
   -1    77             (self.numerator * other.denominator).checked_add(other.numerator * self.denominator).unwrap(),
   -1    78             self.denominator * other.denominator,
   -1    79         );
   -1    80     }
   -1    81 }
   -1    82 
   -1    83 impl Sub<Self> for Rational {
   -1    84     type Output = Self;
   -1    85 
   -1    86     fn sub(self, other: Self) -> Self {
   -1    87         return self + -other;
   -1    88     }
   -1    89 }
   -1    90 
   -1    91 impl Mul<Self> for Rational {
   -1    92     type Output = Self;
   -1    93 
   -1    94     fn mul(self, other: Self) -> Self {
   -1    95         return Self::new(
   -1    96             self.numerator * other.numerator,
   -1    97             self.denominator * other.denominator,
   -1    98         );
   -1    99     }
   -1   100 }
   -1   101 
   -1   102 impl Div<Self> for Rational {
   -1   103     type Output = Self;
   -1   104 
   -1   105     fn div(self, other: Self) -> Self {
   -1   106         let r = Self::new(
   -1   107             self.numerator * other.denominator,
   -1   108             self.denominator * other.numerator,
   -1   109         );
   -1   110         println!("{} / {} = {}", self, other, r);
   -1   111         return r;
   -1   112     }
   -1   113 }

diff --git a/2023/24/solution.rs b/2023/24/solution.rs

@@ -0,0 +1,158 @@
   -1     1 #[path = "../lib.rs"]
   -1     2 mod lib;
   -1     3 
   -1     4 #[path = "./r.rs"]
   -1     5 mod r;
   -1     6 
   -1     7 use std::convert::TryInto;
   -1     8 
   -1     9 type F = r::Rational;
   -1    10 
   -1    11 fn f(i: i128) -> F {
   -1    12     return F::n(i);
   -1    13 }
   -1    14 
   -1    15 fn unf(f: F) -> i128 {
   -1    16     println!("{}", f);
   -1    17     assert!(f.numerator % f.denominator == 0);
   -1    18     return f.numerator / f.denominator;
   -1    19 }
   -1    20 
   -1    21 fn parse_input() -> Vec<([i128; 3], [i128; 3])> {
   -1    22     return lib::iter_input().map(|line| {
   -1    23         let (a, b) = line.split_once('@').unwrap();
   -1    24         let p: Vec<i128> = a.split(',').map(|s| s.trim().parse().unwrap()).collect();
   -1    25         let d: Vec<i128> = b.split(',').map(|s| s.trim().parse().unwrap()).collect();
   -1    26         return (
   -1    27             p.try_into().unwrap(),
   -1    28             d.try_into().unwrap(),
   -1    29         );
   -1    30     }).collect();
   -1    31 }
   -1    32 
   -1    33 fn intersect(h1: ([i128; 3], [i128; 3]), h2: ([i128; 3], [i128; 3])) -> bool {
   -1    34     // 200_000_000_000_000 <= x1 + t1*dx1 = x2 + t2*dx2 <= 400_000_000_000_000
   -1    35     // 200_000_000_000_000 <= y1 + t1*dy1 = y2 + t2*dy2 <= 400_000_000_000_000
   -1    36     // t1 = (x2 - x1 + t2*dx2) / dx1
   -1    37     // y1 + (x2 - x1 + t2*dx2) / dx1 * dy1 = y2 + t2*dy2
   -1    38     // y1 + x2*dy1/dx1 - x1*dy1/dx1 + t2*dx2*dy1/dx1 = y2 + t2*dy2
   -1    39     // y1 - y2 + x2*dy1/dx1 - x1*dy1/dx1 = t2*dy2 - t2*dx2*dy1/dx1
   -1    40     // y1 - y2 + x2*dy1/dx1 - x1*dy1/dx1 = t2 * (dy2 - dx2*dy1/dx1)
   -1    41     // t2 = ((y1 - y2) + (x2 - x1)*dy1/dx1) / (dy2 - dx2*dy1/dx1)
   -1    42     // t2 = ((y1 - y2)*dx1 - (x1 - x2)*dy1) / (dy2*dx1 - dx2*dy1)
   -1    43 
   -1    44     // in xy, lines intersect if they are not parallel
   -1    45     // dy1 / dx1 != dy2 / dx2
   -1    46     // dy1 * dx2 != dy2 * dx1
   -1    47 
   -1    48     let ([x1, y1, _z1], [dx1, dy1, _dz1]) = h1;
   -1    49     let ([x2, y2, _z2], [dx2, dy2, _dz2]) = h2;
   -1    50 
   -1    51     let d = dy1 * dx2 - dx1 * dy2;
   -1    52     if d == 0 {
   -1    53         return false;
   -1    54     }
   -1    55 
   -1    56     let dt1 = (y2 - y1) * dx2 - (x2 - x1) * dy2;
   -1    57     if (dt1 < 0 && d >= 0) || (dt1 >= 0 && d < 0) {
   -1    58         return false;
   -1    59     }
   -1    60 
   -1    61     let dt2 = (y2 - y1) * dx1 - (x2 - x1) * dy1;
   -1    62     if (dt2 < 0 && d >= 0) || (dt2 >= 0 && d < 0) {
   -1    63         return false;
   -1    64     }
   -1    65 
   -1    66     let x = unf(f(x1) + f(dx1) * f(dt1) / f(d));
   -1    67     let y = unf(f(y1) + f(dy1) * f(dt1) / f(d));
   -1    68 
   -1    69     // let min = 7.0;
   -1    70     // let max = 27.0;
   -1    71     let min = 200_000_000_000_000;
   -1    72     let max = 400_000_000_000_000;
   -1    73 
   -1    74     return x >= min && x <= max && y >= min && y <= max;
   -1    75 }
   -1    76 
   -1    77 fn part1(hail: &Vec<([i128; 3], [i128; 3])>) -> i128 {
   -1    78     let mut count = 0;
   -1    79     for i in 0..hail.len() {
   -1    80         for j in 0..i {
   -1    81             if intersect(hail[i], hail[j]) {
   -1    82                 count += 1;
   -1    83             }
   -1    84         }
   -1    85     }
   -1    86     return count;
   -1    87 }
   -1    88 
   -1    89 fn solve<const N: usize>(matrix: &[[F; N]; N], b: &[F; N]) -> [F; N] {
   -1    90     let mut tmp = matrix.clone();
   -1    91     let mut result = b.clone();
   -1    92 
   -1    93     for k in 0..N {
   -1    94         result[k] = result[k] / tmp[k][k];
   -1    95         for j in (k..N).rev() {
   -1    96             tmp[k][j] = tmp[k][j] / tmp[k][k];
   -1    97         }
   -1    98 
   -1    99         for i in (k + 1)..N {
   -1   100             result[i] = result[i] - result[k] * tmp[i][k];
   -1   101             for j in (k..N).rev() {
   -1   102                 tmp[i][j] = tmp[i][j] - tmp[k][j] * tmp[i][k];
   -1   103             }
   -1   104         }
   -1   105     }
   -1   106 
   -1   107     for k in (0..N).rev() {
   -1   108         for i in 0..k {
   -1   109             result[i] = result[i] - result[k] * tmp[i][k];
   -1   110         }
   -1   111     }
   -1   112 
   -1   113     return result;
   -1   114 }
   -1   115 
   -1   116 
   -1   117 fn part2(hail: &Vec<([i128; 3], [i128; 3])>) -> i128 {
   -1   118     // x + ti*dx = xi + ti*dxi
   -1   119     // y + ti*dy = yi + ti*dyi
   -1   120     // z + ti*dz = zi + ti*dzi
   -1   121 
   -1   122     // (p - pi) / (di - d)   = ti
   -1   123     // (x - xi) / (dxi - dx) = ti
   -1   124 
   -1   125     // (p - pi) / (di - d) = (x - xi) / (dxi - dx)
   -1   126     // p*dxi - d*xi - x*di + dx*pi + x*d - p*dx = pi*dxi - xi*di
   -1   127     // p*(dxi - dxj) - d*(xi - xj) - x*(di - dj) + dx*(pi - pj) = pi*dxi - xi*di - pj*dxj + xj*dj
   -1   128 
   -1   129     let mut matrix = [[f(0); 4]; 4];
   -1   130     let mut b = [f(0); 4];
   -1   131 
   -1   132     let ([xj, yj, zj], [dxj, dyj, dzj]) = hail[0];
   -1   133     let pj = xj + yj + zj;
   -1   134     let dj = dxj + dyj + dzj;
   -1   135 
   -1   136     for i in 0..4 {
   -1   137         let ([xi, yi, zi], [dxi, dyi, dzi]) = hail[i + 1];
   -1   138         let pi = xi + yi + zi;
   -1   139         let di = dxi + dyi + dzi;
   -1   140 
   -1   141         matrix[i][0] = f(dxi - dxj);
   -1   142         matrix[i][1] = f(xj - xi);
   -1   143         matrix[i][2] = f(dj - di);
   -1   144         matrix[i][3] = f(pi - pj);
   -1   145         b[i] = f(pi * dxi - xi * di - pj * dxj + xj * dj);
   -1   146     }
   -1   147 
   -1   148     let result = solve(&matrix, &b);
   -1   149 
   -1   150     return unf(result[0]);
   -1   151 }
   -1   152 
   -1   153 fn main() {
   -1   154     let hail = parse_input();
   -1   155 
   -1   156     println!("part1: {}", part1(&hail));
   -1   157     println!("part2: {}", part2(&hail));
   -1   158 }