heh
backwards
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | src/main.rs | 91 | ||||
| -rw-r--r-- | src/util.rs | 81 |
3 files changed, 107 insertions, 66 deletions
@@ -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'); } } } |