#![deny(overflowing_literals)]

type Input = u32;

const BOUND: Input = 1_000_000;
const _ENSURE_NO_OVERFLOW: Input = BOUND * 3;

#[derive(Debug, PartialEq, Eq)]
enum CountStepsError {
    Zero,
    OutOfBound,
}

fn count_steps(target: Input) -> Result<usize, CountStepsError> {
    use std::cmp::Ordering::*;
    use CountStepsError::*;

    if target == 0 {
        return Err(Zero);
    }

    if target >= BOUND {
        return Err(OutOfBound);
    }

    if target == 1 {
        return Ok(0);
    }

    let mut prev = vec![1];
    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) {
                Greater => unreachable!(),
                Equal => return Ok(steps),
                Less => {
                    buf.push(x_1);
                }
            }

            let x2 = x * 2;
            match x2.cmp(&target) {
                Greater => (),
                Equal => return Ok(steps),
                Less => {
                    buf.push(x2);

                    let x3 = x * 3;
                    match x3.cmp(&target) {
                        Greater => (),
                        Equal => return Ok(steps),
                        Less => {
                            buf.push(x3);
                        }
                    }
                }
            }
        }

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

#[test]
fn some_variants() {
    assert_eq!(count_steps(1), Ok(0));
    assert_eq!(count_steps(9), Ok(2));
    assert_eq!(count_steps(15), Ok(4));
    assert_eq!(count_steps(82), Ok(5));
    assert_eq!(count_steps(768), Ok(9));
}

#[test]
fn check_error() {
    use CountStepsError::*;

    assert_eq!(count_steps(0), Err(Zero));
    assert_eq!(count_steps(BOUND), Err(OutOfBound));
}