Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- diff --git a/src/day02.rs b/src/day02.rs
- index c09c8ae..fabefae 100644
- --- a/src/day02.rs
- +++ b/src/day02.rs
- @@ -1,4 +1,3 @@
- -use std::cmp::max;
- use std::collections::HashSet;
- pub fn parse(contents: &str) -> Vec<(u64, u64)> {
- @@ -14,6 +13,34 @@ fn num_digits(n: u64, b: u32) -> usize {
- (0..).take_while(|i| (b as u64).pow(*i) <= n).count()
- }
- +// Returns the count of numbers with period `rep` between `id_start` and `id_end` (inclusive).
- +fn count_between(rep: usize, id_start: u64, id_end: u64) -> i128 {
- + let digits_start = ((num_digits(id_start, 10) + (rep - 1)) / rep) as u32;
- + let digits_end = (num_digits(id_end, 10) / rep) as u32;
- + let mut count = 0;
- + for digits in digits_start..=digits_end {
- + let mut factor = 0;
- + for r in 0..rep as u32 {
- + factor += 10u64.pow(r * digits);
- + }
- +
- + let mut invalid_check_start = 10u64.pow(digits - 1).max(id_start / factor);
- + if invalid_check_start * factor < id_start {
- + invalid_check_start += 1;
- + }
- +
- + let end_invalid_ids = (10u64.pow(digits) - 1).min(id_end / factor);
- + if end_invalid_ids < invalid_check_start {
- + break;
- + }
- +
- + let n = end_invalid_ids - invalid_check_start;
- + count += factor as i128
- + * ((n as i128 + 1) * invalid_check_start as i128 + ((n as i128 * (n as i128 + 1)) / 2));
- + }
- + count
- +}
- +
- // #[aoc(day2, part1)]
- #[allow(dead_code)]
- pub fn part_a(contents: &str) -> u64 {
- @@ -70,29 +97,11 @@ pub fn part_a_binary(contents: &str) -> u64 {
- #[aoc(day2, part1, smarter)]
- // #[allow(dead_code)]
- -pub fn part_a_smarter(contents: &str) -> u128 {
- +pub fn part_a_smarter(contents: &str) -> i128 {
- let vec = parse(contents);
- let mut invalid_id_sum = 0;
- for (id_start, id_end) in vec {
- - let digits_start = (num_digits(id_start, 10) as f64 / 2.0).ceil() as usize;
- - let digits_end = max(num_digits(id_end, 10) / 2, 1);
- - for digits in digits_start..=digits_end {
- - let factor = 10u64.pow(digits as u32) + 1;
- -
- - let mut invalid_check_start = 10u64.pow(digits as u32 - 1).max(id_start / factor);
- - while invalid_check_start * factor < id_start {
- - invalid_check_start += 1;
- - }
- -
- - let end_invalid_ids = (10u64.pow(digits as u32) - 1).min(id_end / factor);
- - if end_invalid_ids < invalid_check_start {
- - continue;
- - }
- - let n = end_invalid_ids - invalid_check_start;
- - invalid_id_sum += factor as u128
- - * ((n + 1) as u128 * invalid_check_start as u128
- - + ((n as u128 * (n as u128 + 1)) / 2));
- - }
- + invalid_id_sum += count_between(2, id_start, id_end);
- }
- invalid_id_sum
- }
- @@ -198,36 +207,7 @@ pub fn part_b_smarter(contents: &str) -> i128 {
- continue;
- }
- for (id_start, id_end) in vec.iter() {
- - if num_digits(*id_end, 10) < rep {
- - continue;
- - }
- - let digits_start = (num_digits(*id_start, 10) as f64 / rep as f64).ceil() as usize;
- - let digits_end = num_digits(*id_end, 10) / rep;
- -
- - for digits in digits_start..=digits_end {
- - let mut factor = 0;
- -
- - for r in 0..rep {
- - factor += 10u64.pow(r as u32 * digits as u32);
- - }
- -
- - let mut invalid_check_start = 10u64.pow(digits as u32 - 1).max(*id_start / factor);
- -
- - if invalid_check_start * factor < *id_start {
- - invalid_check_start += 1;
- - }
- -
- - let end_invalid_ids = (10u64.pow(digits as u32) - 1).min(id_end / factor);
- -
- - if end_invalid_ids < invalid_check_start {
- - continue;
- - }
- - let n = end_invalid_ids - invalid_check_start;
- - invalid_id_sum += sign as i128
- - * factor as i128
- - * ((n + 1) as i128 * invalid_check_start as i128
- - + ((n as i128 * (n as i128 + 1)) / 2));
- - }
- + invalid_id_sum += sign as i128 * count_between(rep, *id_start, *id_end);
- }
- }
- invalid_id_sum
Advertisement
Add Comment
Please, Sign In to add comment