bendns' repos / aoc
heh
better ilog10
Browse Source
bendn 2024-12-07
parent 0740f5a · commit cb21c09
Diffstat
-rw-r--r--Cargo.toml1
-rw-r--r--src/main.rs82
-rw-r--r--src/util.rs1
3 files changed, 43 insertions, 41 deletions
diff --git a/Cargo.toml b/Cargo.toml
index 010dcc4..0d6269a 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,6 +8,7 @@ edition = "2021"
[dependencies]
atools = "0.1.5"
bitvec = "1.0.1"
+car = "0.1.1"
# hinted = "0.0.1"
itertools = "0.12.0"
memchr = "2.6.4"
diff --git a/src/main.rs b/src/main.rs
index 45cc850..8c0d7e4 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -30,10 +30,16 @@ extern crate test;
pub mod util;
pub use util::prelude::*;
-const SIZE: usize = 10;
-
-fn concat(a: u64, b: u64) -> u64 {
- a * 10u64.pow(b.ilog10() + 1) + b
+// 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 {
@@ -52,62 +58,56 @@ fn search(mut nums: &[u64], should: u64, current: u64, ops: &[fn(u64, u64) -> u6
false
}
-#[no_mangle]
-pub fn run(i: &str) -> impl Display {
+#[inline]
+fn do_(ops: &[fn(u64, u64) -> u64], i: &str) -> u64 {
+ let mut v = Vec::with_capacity(10);
i.行()
.map(|x| {
+ v.clear();
let (a, b) = x.μ(':');
- let should = a.λ::<u64>();
- let nums = b.κ::<u64>().collect_vec();
- let mut nums = &*nums;
+ 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,
- &[
- (std::ops::Add::<u64>::add),
- (std::ops::Mul::<u64>::mul as fn(u64, u64) -> u64),
- ],
- ) as u64
+ should * search(nums, should, first, ops) 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,
+ )
+}
+
+#[no_mangle]
pub fn p2(i: &str) -> impl Display {
- i.行()
- .map(|x| {
- let (a, b) = x.μ(':');
- let should = a.λ::<u64>();
- let nums = b.κ::<u64>().collect_vec();
- let mut nums = &*nums;
- let &first = nums.take_first().ψ();
- should
- * search(
- nums,
- should,
- first,
- &[
- (std::ops::Add::<u64>::add),
- (std::ops::Mul::<u64>::mul as fn(u64, u64) -> u64),
- concat,
- ],
- ) as u64
- })
- .sum::<u64>()
+ 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 main() {
+ // (1..u32::MAX as u64).for_each(|a| assert_eq!(a.ilog10() + 1, digs(a)));
// let mut s = String::new();
// for i in 0..1280 {
let i = include_str!("inp.txt");
// s.push_str(i);
// }
// std::fs::write("src/inp.txt", s);
- println!("{}", run(i));
- println!("{}", p2(i));
+ assert_eq!(run(i).to_string(), 663613490587u64.to_string());
+ assert_eq!(p2(i).to_string(), 110365987435001u64.to_string());
}
#[bench]
diff --git a/src/util.rs b/src/util.rs
index f845230..d124334 100644
--- a/src/util.rs
+++ b/src/util.rs
@@ -968,6 +968,7 @@ pub mod reading {
}
}
}
+ v.push(s);
}
pub trait Ten {
fn ten() -> Self;