Skip to content

Instantly share code, notes, and snippets.

@indiv0

indiv0/day_6_1.rs

Created December 8, 2023 09:38
Show Gist options
  • Save indiv0/f589872a1323075ab0376c56479b04b8 to your computer and use it in GitHub Desktop.
Save indiv0/f589872a1323075ab0376c56479b04b8 to your computer and use it in GitHub Desktop.
Download ZIP
9ns.rs
Raw
day_6_1.rs
// ===========
// === Run ===
// ===========
pub fn run(s: &str) -> u64 {
let (times, distances) = parse_input(s);
let times = &[times.0, times.1, times.2, times.3];
let distances = &[distances.0, distances.1, distances.2, distances.3];
let wins0 = simulate_race(times[0] as u16, distances[0]) as u64;
let wins1 = simulate_race(times[1] as u16, distances[1]) as u64;
let wins2 = simulate_race(times[2] as u16, distances[2]) as u64;
let wins3 = simulate_race(times[3] as u16, distances[3]) as u64;
let counter = wins0 * wins1 * wins2 * wins3;
counter
}
#[inline(always)]
pub fn parse_input(s: &str) -> ((u8, u8, u8, u8), (u16, u16, u16, u16)) {
const PREFIX: &str = "Distance: ";
const PREFIX_LEN: usize = PREFIX.len();
const SPACE_LEN: usize = 3;
const NL_LEN: usize = 1;
const LINE_LEN: usize = PREFIX_LEN + 3 + SPACE_LEN + 4 + SPACE_LEN + 4 + SPACE_LEN + 4 + NL_LEN;
const TOTAL_LEN: usize = LINE_LEN * 2;
let s = s.as_bytes();
let times = &s[PREFIX_LEN..=LINE_LEN];
let times = [
parse_u8_2((times[1], times[2])),
parse_u8_2((times[8], times[9])),
parse_u8_2((times[15], times[16])),
parse_u8_2((times[22], times[23])),
];
let distances = &s[(LINE_LEN + PREFIX_LEN)..TOTAL_LEN - NL_LEN];
let distances = [
parse_u16_3((distances[0], distances[1], distances[2])),
parse_u16_4((distances[6], distances[7], distances[8], distances[9])),
parse_u16_4((distances[13], distances[14], distances[15], distances[16])),
parse_u16_4((distances[20], distances[21], distances[22], distances[23])),
];
((
times[0],
times[1],
times[2],
times[3],
), (
distances[0],
distances[1],
distances[2],
distances[3],
))
}
#[inline(always)]
const fn parse_u8_2((a, b): (u8, u8)) -> u8 {
b_to_u8(a) * 10 + b_to_u8(b)
}
#[inline(always)]
const fn parse_u16_3((a, b, c): (u8, u8, u8)) -> u16 {
b_to_u16(a) * 100 + b_to_u16(b) * 10 + b_to_u16(c)
}
#[inline(always)]
const fn parse_u16_4((a, b, c, d): (u8, u8, u8, u8)) -> u16 {
b_to_u16(a) * 1000 + b_to_u16(b) * 100 + b_to_u16(c) * 10 + b_to_u16(d)
}
// Let,
// a = acceleration
// v = velocity
// t_a = time for acceleration
// t_m = time for movement
// T = total time
// d = distance travelled
// D = race record distance + 1
//
// We have,
// d = (a * t_a) * t_m
// = (a * t_a) * (T - t_a)
// = a * t_a * T - a * t_a * t_a
// = -a * t_a^2 + a * t_a * T
// T = t_a + t_m => t_m = T - t_a
//
// The roots of f(t_a) = D gives us the values of t_a, between which, d will be greater or equal to
// D.
//
// t_a = ( aT +- sqrt( (aT)^2 - 4aD ) ) / 2
// = ( aT +- det ) / 2
//
// where det = sqrt( (aT)^2 - 4aD )
//
// => t1 = (aT - det) / 2
// and t2 = (aT + det) / 2
//
// The number of ways to win is the number of valid integer time values between the two roots =
// ceil(t1) - floor(t2) + 1
#[inline(always)]
fn simulate_race(t: u16, d: u16) -> u16 {
assert!(t <= 999);
assert!(d <= 9999);
let t = t as f32;
let d = d as f32 + 0.5;
let at = t;
// FIXME [NP]: use square?
let det = ((at * at - 4. * d)).sqrt();
assert!(det <= 50.);
let t1 = ((at - det) / 2.).ceil();
let t2 = ((at + det) / 2.).floor();
let n = t2 - t1 + 1.;
assert!(n.is_sign_positive());
n as u16
}
// Converts a byte of ASCII `[0-9]` to the equivalent `u8`.
#[inline(always)]
const fn b_to_u8(b: u8) -> u8 {
b - b'0'
}
// Converts a byte of ASCII `[0-9]` to the equivalent `u16`.
#[inline(always)]
const fn b_to_u16(b: u8) -> u16 {
b_to_u8(b) as u16
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment