bendns' repos / aoc
heh
Diffstat (limited to 'src/main.rs')
-rw-r--r--src/main.rs82
1 files changed, 41 insertions, 41 deletions
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]