bendns' repos / aoc
heh
Diffstat
-rw-r--r--Cargo.toml1
-rw-r--r--src/main.rs91
-rw-r--r--src/util.rs81
3 files changed, 107 insertions, 66 deletions
diff --git a/Cargo.toml b/Cargo.toml
index 0d6269a..470ee4f 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -7,7 +7,6 @@ edition = "2021"
[dependencies]
atools = "0.1.5"
-bitvec = "1.0.1"
car = "0.1.1"
# hinted = "0.0.1"
itertools = "0.12.0"
diff --git a/src/main.rs b/src/main.rs
index 8c0d7e4..c1a5d37 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -30,36 +30,8 @@ extern crate test;
pub mod util;
pub use util::prelude::*;
-// https://stackoverflow.com/a/9721570
-fn digs(x: u64) -> u64 {
- static powers: [u64; 20] = car::from_fn!(|x| 10u64.pow(x as u32));
- static mdigs: [u32; 65] = car::from_fn!(|x| 2u128.pow(x as u32).ilog10() + 1);
- let bit = std::mem::size_of::<u64>() * 8 - x.leading_zeros() as usize;
- let mut digs = mdigs[bit];
- if x < powers[digs as usize - 1] {
- digs -= 1;
- }
- powers[digs as usize]
-}
-
-fn search(mut nums: &[u64], should: u64, current: u64, ops: &[fn(u64, u64) -> u64]) -> bool {
- let Some(&a) = nums.take_first() else {
- return current == should;
- };
- for op in ops {
- let result = op(current, a);
- if result > should {
- continue;
- }
- if search(nums, should, result, ops) {
- return true;
- }
- }
- false
-}
-
#[inline]
-fn do_(ops: &[fn(u64, u64) -> u64], i: &str) -> u64 {
+fn do_(i: &str, search: fn(&[u64], u64) -> bool) -> u64 {
let mut v = Vec::with_capacity(10);
i.行()
.map(|x| {
@@ -67,35 +39,57 @@ fn do_(ops: &[fn(u64, u64) -> u64], i: &str) -> u64 {
let (a, b) = x.μ(':');
let should = reading::all(a);
reading::κ(C! { &b[1..] }, &mut v);
- let mut nums = &*v;
- let &first = nums.take_first().ψ();
- should * search(nums, should, first, ops) as u64
+ should * search(&v, should) as u64
})
.sum::<u64>()
}
#[no_mangle]
pub fn run(i: &str) -> impl Display {
- do_(
- &[
- (std::ops::Add::<u64>::add),
- (std::ops::Mul::<u64>::mul as fn(u64, u64) -> u64),
- ],
- i,
- )
+ // go backwards for extreme pruning ability
+ fn search(nums: &[u64], tv: u64) -> bool {
+ match nums {
+ &[tail] => tv == tail,
+ [head @ .., tail] => {
+ let (q, r) = (tv / tail, tv % tail);
+ if r == 0 && search(head, q) {
+ return true;
+ }
+ let Some(result) = tv.checked_sub(*tail) else {
+ return false;
+ };
+ search(head, result)
+ }
+ [] => unreachable!(),
+ }
+ }
+ do_(i, search)
}
#[no_mangle]
pub fn p2(i: &str) -> impl Display {
- do_(
- &[
- (std::ops::Add::<u64>::add),
- (std::ops::Mul::<u64>::mul as fn(u64, u64) -> u64),
- |a, b| a * digs(b) + b,
- // |a, b| a * 10u64.pow(b.checked_ilog10().ψ() + 1) + b,
- ],
- i,
- )
+ fn search(nums: &[u64], tv: u64) -> bool {
+ match nums {
+ &[tail] => tv == tail,
+ [head @ .., tail] => {
+ let (q, r) = (tv / tail, tv % tail);
+ if r == 0 && search(head, q) {
+ return true;
+ }
+ let Some(result) = tv.checked_sub(*tail) else {
+ return false;
+ };
+ if (tv - *tail) % util::powers[tail.ͱ() as usize] == 0
+ && search(head, tv / util::powers[tail.ͱ() as usize])
+ {
+ return true;
+ }
+ search(head, result)
+ }
+ [] => unreachable!(),
+ }
+ }
+ do_(i, |n, should| search(n, should))
}
fn main() {
@@ -106,6 +100,7 @@ fn main() {
// s.push_str(i);
// }
// std::fs::write("src/inp.txt", s);
+ // println!("{}", p2(i));
assert_eq!(run(i).to_string(), 663613490587u64.to_string());
assert_eq!(p2(i).to_string(), 110365987435001u64.to_string());
}
diff --git a/src/util.rs b/src/util.rs
index d124334..72e0457 100644
--- a/src/util.rs
+++ b/src/util.rs
@@ -16,10 +16,10 @@ pub mod prelude {
#[allow(unused_imports)]
pub(crate) use super::{bits, dang, leek, mat, shucks, C};
pub use super::{
- even, gcd, gt, l, lcm, lt, nail, pa, r, rand, reading, reading::Ext, sort, Dir, FilterBy,
- FilterBy3, GreekTools, IntoCombinations, IntoLines, IterͶ, NumTupleIterTools, ParseIter,
- Printable, Skip, TakeLine, TupleIterTools2, TupleIterTools2R, TupleIterTools3, TupleUtils,
- UnifiedTupleUtils, UnsoundUtilities, Widen, Ͷ, Α, Κ, Λ, Μ,
+ even, gcd, gt, l, lcm, lt, nail, pa, r, rand, reading, reading::Ext, sort, DigiCount, Dir,
+ FilterBy, FilterBy3, GreekTools, IntoCombinations, IntoLines, IterͶ, NumTupleIterTools,
+ ParseIter, Printable, Skip, TakeLine, TupleIterTools2, TupleIterTools2R, TupleIterTools3,
+ TupleUtils, UnifiedTupleUtils, UnsoundUtilities, Widen, Ͷ, Α, Κ, Λ, Μ,
};
pub use itertools::izip;
pub use itertools::Itertools;
@@ -552,30 +552,72 @@ impl<T> Α<T> for Option<T> {
}
}
-pub trait Ͷ {
+pub trait DigiCount {
+ fn ͱ(self) -> u32;
+}
+
+pub const powers: [u64; 20] = car::from_fn!(|x| 10u64.pow(x as u32));
+// https://stackoverflow.com/a/9721570
+impl DigiCount for u64 {
+ fn ͱ(self) -> u32 {
+ static powers: [u64; 20] = car::from_fn!(|x| 10u64.pow(x as u32));
+ static mdigs: [u32; 65] = car::from_fn!(|x| 2u128.pow(x as u32).ilog10() + 1);
+ let bit = std::mem::size_of::<Self>() * 8 - self.leading_zeros() as usize;
+ let mut digs = mdigs[bit];
+ if self < powers[digs as usize - 1] {
+ digs -= 1;
+ }
+ digs
+ }
+}
+
+impl DigiCount for u32 {
+ fn ͱ(self) -> Self {
+ static powers: [u32; 10] = car::from_fn!(|x| 10u32.pow(x as u32));
+ static mdigs: [u32; 33] = car::from_fn!(|x| 2u128.pow(x as u32).ilog10() + 1);
+ let bit = std::mem::size_of::<Self>() * 8 - self.leading_zeros() as usize;
+ let mut digs = mdigs[bit];
+ if self < powers[digs as usize - 1] {
+ digs -= 1;
+ }
+ digs
+ }
+}
+
+impl DigiCount for u16 {
+ fn ͱ(self) -> u32 {
+ self.checked_ilog10().ψ() + 1
+ }
+}
+
+impl DigiCount for u8 {
+ fn ͱ(self) -> u32 {
+ self.checked_ilog10().ψ() + 1
+ }
+}
+
+pub trait Ͷ: DigiCount {
fn ͷ(self) -> impl Iterator<Item = u8>;
+ fn Ͷ(self, i: u8) -> u8;
}
macro_rules! digs {
($for:ty) => {
impl Ͷ for $for {
fn ͷ(self) -> impl Iterator<Item = u8> {
- let digits = (self.ilog10() + 1) as u8;
- (0..digits)
- .rev()
- .map(move |n| ((self / (10 as $for).pow(n as _)) % 10) as u8)
+ let digits = self.ͱ() as u8;
+ (0..digits).rev().map(move |n| self.Ͷ(n))
+ }
+ fn Ͷ(self, i: u8) -> u8 {
+ ((self / (10 as $for).pow(i as _)) % 10) as u8
}
}
};
}
digs!(u64);
-digs!(i64);
-digs!(i32);
digs!(u32);
digs!(u16);
-digs!(i16);
digs!(u8);
-digs!(i8);
#[derive(Copy, Clone, PartialEq, PartialOrd)]
pub struct Ronge {
@@ -955,16 +997,21 @@ pub mod reading {
}
}
use crate::util::prelude::*;
- pub fn κ(x: &[u8], v: &mut Vec<u64>) {
- let mut s = 0;
+ pub fn κ<
+ T: Default + std::ops::Mul<T, Output = T> + Add<T, Output = T> + From<u8> + Copy + Ten,
+ >(
+ x: &[u8],
+ v: &mut Vec<T>,
+ ) {
+ let mut s = T::default();
for &b in x {
match b {
b' ' => {
v.push(s);
- s = 0;
+ s = T::default();
}
b => {
- s = s * 10 + (b - b'0') as u64;
+ s = s * T::ten() + T::from(b - b'0');
}
}
}