heh
Diffstat (limited to 'src/main.rs')
| -rw-r--r-- | src/main.rs | 231 |
1 files changed, 184 insertions, 47 deletions
diff --git a/src/main.rs b/src/main.rs index b79317e..fc39b79 100644 --- a/src/main.rs +++ b/src/main.rs @@ -78,36 +78,48 @@ use crate::util::UnionFind; #[unsafe(no_mangle)] #[implicit_fn::implicit_fn] pub unsafe fn p1(x: &'static [u8]) -> impl Debug { - let v = util::uints::<i64>(x).array_chunks::<3>().collect_vec(); - let k = v - .iter() - .copied() - .ι::<usize>() - .array_combinations::<2>() - .sorted_by_key(|[(a, _), (b, _)]| { - ((a[0] - b[0]).pow(2) + (a[1] - b[1]).pow(2) + (a[2] - b[2]).pow(2)).isqrt() - }); - let mut uf = UnionFind::new(1000); - for [a, b] in k.into_iter() { - uf.union(a.1, b.1); - // if (0..1000).map(|n| uf.find(n)).all_equal() { - // return v[a.1][0] * v[b.1][0]; - // } - } - - (0..1000) - .map(|x| uf.group_size(x)) - .sorted() - .rev() - .take(3) - .product::<usize>() + let p = util::uints::<i64>(x) + .array_chunks::<2>() + .collect::<Vec<_>>(); + let mut i = fimg::Image::<_, 1>::alloc( + p.iter().map(|[x, _]| *x).max().unwrap() as u32 / 12, + p.iter().map(|[_, x]| *x).max().unwrap() as u32 / 12, + ); + i.points( + &p.iter() + .map(|[a, b]| (*a as i32 / 12, *b as i32 / 12)) + .collect::<Vec<_>>(), + [255], + ); + i.points( + &[ + (98278 / 12, 50283 / 12), + (98278 / 12, 4250 / 12), + (63518 / 12, 4250 / 12), + (63518 / 12, 50283 / 12), + (98278 / 12, 50283 / 12), + ], + [129], + ); + i.save("hm.png"); + i.show(); + return p + .into_iter() + .array_combinations() + .map_w(|z @ [[x1, y1], [x2, y2]]| { + // dbg!(z); + ((x2 - x1 - 1).abs() * (y2 - y1 - 1).abs()) + }) + .max_by_key(|x| x.1) + .unwrap(); } -unsafe fn p2(x: &[u8]) -> i64 { - fn sq(p1: [i64; 3], p2: [i64; 3]) -> i64 { - (p1[0] - p2[0]).pow(2) + (p1[1] - p2[1]).pow(2) + (p1[2] - p2[2]).pow(2) - } +pub(crate) fn sq(p1: [i64; 3], p2: [i64; 3]) -> i64 { + (p1[0] - p2[0]).pow(2) + (p1[1] - p2[1]).pow(2) + (p1[2] - p2[2]).pow(2) +} +#[unsafe(no_mangle)] +pub(crate) unsafe fn p2(x: &[u8]) -> i64 { let mut p = x.as_ptr(); let end = p.add(x.len()); @@ -130,35 +142,160 @@ unsafe fn p2(x: &[u8]) -> i64 { (points[0][i], points[1][i], points[2][i]) = (x, y, z); i += 1; } - (0..1000) + (281..955) .map(|i| { - let former = from_fn(|j| points[j][i] as i64); - let (dist, retval) = (0..1000) - .filter(|j| i != *j) - .filter_map(|j| { - let d = sq(former, from_fn(|i| points[i][j] as i64)) as i64; - Some((d, points[0][i] as i64 * points[0][j] as i64)) - }) - .min_by_key(|&(d, _)| d) - .unwrap_or((i64::MAX, 0)); + // let former = from_fn(|j| points[j][i] as i64); + // let (_dist, _retval) = (0..1000) + // .filter(|j| i != *j) + // .filter_map(|j| { + // let with: [i64; 3] = from_fn(|i| points[i][j] as i64); + // let d = sq(former, from_fn(|i| points[i][j] as i64)) as i64; + // // println!("{former:?} <-> {with:?}: {d}"); + // Some((d, points[0][i] as i64 * points[0][j] as i64)) + // }) + // .min_by_key(|&(d, _)| d) + // .unwrap_or((i64::MAX, 0)); + // dbg!(_dist); + + let [_x, _y, _z] = from_fn(|j| points[j][i]); + let x = i32x8::splat(_x); + let y = i32x8::splat(_y); + let z = i32x8::splat(_z); + // result of min distance + let mut dist = i64x8::splat(i64::MAX); + // result of the multiply + let mut retval = Simd::splat(0); + let [(x_, xrest), (y_, yrest), (z_, zrest)] = { + [ + points[0][25..905].as_chunks::<8>(), + points[1][25..905].as_chunks::<8>(), + points[2][25..905].as_chunks::<8>(), + ] + }; + // let mut rmin = [i64::MAX; 16]; + // let mut reduced = i64::MAX; + for (x_, y_, z_) in izip!(x_, y_, z_) { + let x_ = Simd::from_slice(x_); + let y_ = Simd::from_slice(y_); + let z_ = Simd::from_slice(z_); + let one = (x - x_).cast::<i64>(); + let two = (y - y_).cast::<i64>(); + let thr = (z - z_).cast::<i64>(); + let d = one * one + two * two + thr * thr; + // let min = izip!(x_.to_array(), y_.to_array(), z_.to_array()) + // .map(|(x, y, z)| { + // sq( + // [x as i64, y as i64, z as i64], + // [_x as i64, _y as i64, _z as i64], + // ) + // }) + // .collect_array::<16>() + // .unwrap(); + // rmin = min + // .zip(rmin) + // .map(|(x, y)| if x.min(y) == 0 { y } else { x.min(y) }); + + // dbg!(d); + let m = d.simd_lt(dist) & d.simd_ne(Simd::splat(0)); + // dbg!(d); + // reduced = reduced.min(m.select(d, Simd::splat(i64::MAX)).reduce_min()); + // min_by_key ( distance ) + dist = m.select(d, dist); + // println!("{rmin:?} {dist:?}"); + // assert_eq!(rmin, dist.to_array()); + // dbg!(dist); + + // points[0][1] * points[1][0] + retval = m.select(x.cast::<i64>() * x_.cast::<i64>(), retval); + } + // dbg!(rmin, reduced); + + // let (dist_, retval_) = izip!(xrest, yrest, zrest) + // .filter_map(|t| { + // let d = sq( + // [_x as i64, _y as i64, _z as i64], + // <[_; 3]>::from(t).map(|x| *x as i64), + // ); + // Some((d, _x as i64 * *t.0 as i64)) + // }) + // // .chain(izip!(dist.to_array(), retval.to_array())) + // .min_by_key(|&(d, _)| d) + // .unwrap(); + // dbg!(dist, retval, dist_, _retval); + (dist, retval) + // todo x8? + // let dist = dist + // .to_array() + // .into_iter() + // .zip(retval.to_array()) + // .min_by_key(|x| x.0) + // .unwrap(); + // let rest = retval; + // let (dist, retval) = izip!(xrest, yrest, zrest) + // .filter_map(|t| { + // let d = sq( + // [_x as i64, _y as i64, _z as i64], + // <[_; 3]>::from(t).map(|x| *x as i64), + // ) as i64; + // Some((d, _x as i64 * *t.0 as i64)) + // }) + // .chain(izip!(dist.to_array(), retval.to_array())) + // .filter(|(d, _)| *d != 0) + // .min_by_key(|&(d, _)| d) + // .unwrap(); + // println!("{i}"); + // assert_eq!(dist, _dist); + // assert_eq!(retval, _retval); + // println!("pass"); + // (dist, retval) }) - .fold((0, -1i64), |(best, mxd), (rmin, set)| { - if rmin > mxd { (set, rmin) } else { (best, mxd) } + .fold((-1, 0), |(_scdist, _scretval), (dist, retval)| { + // we do a lil maxxing + // eprintln!("dist = {dist:?}\nretval = {retval:?}\n_dist = {_dist:?}\n_retval = {_retval:?}"); + let (scdist, scretval) = dist + .to_array() + .into_iter() + .zip(retval.to_array()) + .min_by_key(|x| x.0) + .unwrap(); + // eprintln!("min of new {scdist} {scretval}"); + // let m = Simd::splat(dbg!(dist.reduce_min().max(scdist))).simd_ge(_dist); + // eprintln!("{} >= {_dist:?} {m:?}", dist.reduce_min()); + // eprintln!("dmatched = {:?}",m.select(dist, Simd::splat(0))); + // eprintln!("rmatched = {:?}",m.select(retval, Simd::splat(0))); + // dbg!(real); + + if scdist > _scdist { + (scdist, scretval) + } else { + (_scdist, _scretval) + } + // m.select(dist, _dist), + // m.select(retval, _retval), + + // if dist > mxd {} }) - .0 + .1 + + // .reduce_min() } -const ISIZE: usize = include_bytes!("inp.txt").len(); -fn main() { + +pub(crate) const ISIZE: usize = include_bytes!("inp.txt").len(); + +pub(crate) fn main() { + // dbg!(sq([75262, 24842, 97390], [69492, 23068, 98918])); use atools::prelude::*; - unsafe { println!("{:?}", p2(include_bytes!("inp.txt"))) }; - unsafe { println!("{:?}", p2(include_bytes!("../1"))) }; // 8141888143 - unsafe { println!("{:?}", p2(include_bytes!("../2"))) }; // 83173 * 97891 - unsafe { println!("{:?}", p2(include_bytes!("../3"))) }; // 8465902405 + unsafe { println!("{:?}", p1(include_bytes!("../input_day_9"))) }; + + // unsafe { println!("{:?}", p2(include_bytes!("inp.txt"))) }; + // unsafe { println!("{:?}", p2(include_bytes!("../1"))) }; // 3200955921 + // unsafe { println!("{:?}", p2(include_bytes!("../2"))) }; // 8141888143 + // unsafe { println!("{:?}", p2(include_bytes!("../3"))) }; // 8465902405 } #[bench] -fn benc(b: &mut test::Bencher) { +pub(crate) fn benc(b: &mut test::Bencher) { let i = boxd(include_bytes!("inp.txt")); b.iter(|| unsafe { p1(i) }); } |