9ns.rs

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
}