use std::ops::RangeInclusive;

fn main() {
    max_root(2, 1000_000_000);
    max_root(10, 20);
    max_root(6000, 7000);
    max_root(100_000_000, 100_000_000);
    max_root(4, 16);
}

fn max_root(from: u32, to: u32) -> u32 {
    assert!(from >= 2);
    assert!(to <= 1000_000_000);
    assert!(from <= to);

    #[inline(always)]
    fn dirty_root(x: u32) -> u32 {
        f32::sqrt(x as f32) as u32
    }

    fn rec(range: RangeInclusive<u32>, step: u32) -> Option<(u32, u32)> {
        let (from, to) = range.clone().into_inner();
        if to == 1 || from > to {
            return None;
        }

        let new_from = dirty_root(from);
        let new_to = dirty_root(to);

        let contains_new_from = range.contains(&(new_from * new_from));
        let contains_new_to = range.contains(&(new_to * new_to));

        let new_range = new_from.max(2)..=new_to;
        let next_step = step + 1;

        if contains_new_from || contains_new_to {
            match rec(new_range.clone(), next_step) {
                Some((num, the_step)) if range.contains(&(num * num)) => {
                    Some((num * num, the_step))
                }
                _ => {
                    if contains_new_from {
                        Some((new_from * new_from, next_step))
                    } else {
                        Some((new_to * new_to, next_step))
                    }
                }
            }
        } else {
            None
        }
    }

    match rec(from..=to, 0) {
        Some((num, step)) => {
            println!("Number in charge [{}] on step [{}]", num, step);
            step
        }
        None => 0,
    }
}