#![deny(overflowing_literals)]
#![allow(dead_code)]

fn count_steps(target: u64) -> usize {
    use std::cmp::Ordering;

    if target == 0 || target == 1 {
        return 0;
    }

    let mut prev = std::iter::once(1).collect::<Vec<_>>();
    let mut steps = 0;

    loop {
        steps += 1;
        let mut buf = Vec::with_capacity(prev.len() * 3);

        for &x in &prev {
            let x_1 = x + 1;
            match x_1.cmp(&target) {
                Ordering::Greater => unreachable!(),
                Ordering::Equal => return steps,
                Ordering::Less => {
                    buf.push(x_1);
                }
            }

            if let Some(x2) = x.checked_mul(2) {
                match x2.cmp(&target) {
                    Ordering::Greater => (),
                    Ordering::Equal => return steps,
                    Ordering::Less => {
                        buf.push(x2);
                        if let Some(x3) = x.checked_mul(3) {
                            match x3.cmp(&target) {
                                Ordering::Greater => (),
                                Ordering::Equal => return steps,
                                Ordering::Less => {
                                    buf.push(x3);
                                }
                            }
                        }
                    }
                }
            }
        }

        buf.sort_unstable();
        buf.dedup();
        prev = buf;
    }
}

fn count_steps_hash(target: u64) -> usize {
    use std::cmp::Ordering;
    use std::collections::HashSet;

    if target == 0 || target == 1 {
        return 0;
    }

    let mut prev = std::iter::once(1).collect::<HashSet<_>>();
    let mut steps = 0;

    loop {
        steps += 1;
        let mut buf = HashSet::new();

        for &x in &prev {
            let x_1 = x + 1;
            match x_1.cmp(&target) {
                Ordering::Greater => unreachable!(),
                Ordering::Equal => return steps,
                Ordering::Less => {
                    buf.insert(x_1);
                }
            }

            if let Some(x2) = x.checked_mul(2) {
                match x2.cmp(&target) {
                    Ordering::Greater => (),
                    Ordering::Equal => return steps,
                    Ordering::Less => {
                        buf.insert(x2);
                        if let Some(x3) = x.checked_mul(3) {
                            match x3.cmp(&target) {
                                Ordering::Greater => (),
                                Ordering::Equal => return steps,
                                Ordering::Less => {
                                    buf.insert(x3);
                                }
                            }
                        }
                    }
                }
            }
        }

        prev = buf;
    }
}

use std::collections::HashMap;
struct StepsMemo(HashMap<u64, usize>);

impl StepsMemo {
    fn new() -> Self {
        let mut seed = HashMap::new();
        seed.insert(0, 0);
        seed.insert(1, 0);
        StepsMemo(seed)
    }

    fn count_steps(&mut self, target: u64) -> usize {
        if target == 0 || target == 1 {
            return 0;
        }

        let mut tasks = vec![target];
        while let Some(target) = tasks.pop() {
            if self.0.get(&target).is_none() {
                let target_1 = target - 1;
                match self.0.get(&target_1) {
                    None => {
                        tasks.push(target);
                        tasks.push(target - 1);
                        if target % 2 == 0 {
                            tasks.push(target / 2)
                        }
                        if target % 3 == 0 {
                            tasks.push(target / 3)
                        }
                    }
                    Some(&step1) => {
                        let mut steps = step1;
                        if target % 2 == 0 {
                            let target_div_2 = target / 2;
                            match self.0.get(&target_div_2) {
                                None => {
                                    tasks.push(target_div_2);
                                    if target % 3 == 0 {
                                        tasks.push(target / 3);
                                    }
                                }
                                Some(&step2) => steps = step2.min(steps),
                            }
                        }
                        if target % 3 == 0 {
                            let target_div_3 = target / 3;
                            match self.0.get(&target_div_3) {
                                None => tasks.push(target_div_3),
                                Some(&step3) => steps = step3.min(steps),
                            }
                        }
                        self.0.insert(target, steps + 1);
                    }
                }
            }
        }

        self.0[&target]
    }
}

fn main() {
    use std::time::Instant;

    let moment = Instant::now();
    let answer = count_steps(999_999);
    let elapsed = moment.elapsed();
    println!("{}", answer);
    println!("{:?}", elapsed);
}