adventofcode

commit

557e065dfb9cbb60a158ee15cd4809662a302f9e

parent

387fe63045a164a7ed2436df870e112ceba8e28d

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2024-01-03 15:43

Revert "foo"

This reverts commit 387fe63045a164a7ed2436df870e112ceba8e28d.

Diffstat

2 files changed, 0 insertions, 271 deletions

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

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

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

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