I wrote two versions of this. The first one I wrote was an exhaustive search. Then I read some answers here and wanted to write up the solution @savagepixie
had and compared them. They matched on all the numbers I tested on (up to 200 in the test case).
At first I wasn't convinced that the 'simpler' solution of counting down was gonna work, but I was definitely wrong! It performs way better than my exhaustive search and seems to be just as accurate
pubfnshortest_step_exhaustive_recurse(num:u64)->Option<u64>{fnrecursive_helper(cur:u64,goal:u64)->Option<u64>{ifcur==goal{Some(0)}elseifcur>goal{None}else{[cur+1,cur*2].iter().filter_map(|next_try|recursive_helper(*next_try,goal)).map(|attempt|attempt+1).min()}}recursive_helper(1,num)}pubfnshortest_step_count_down(num:u64)->Option<u64>{ifnum==0{None}elseifnum==1{Some(0)}elseifnum%2==0{Some(1+shortest_step_count_down(num/2)?)}else{Some(1+shortest_step_count_down(num-1)?)}}#[cfg(test)]modtests{usecrate::*;#[test]fnall_algos_work_for_three(){assert_eq!(shortest_step_exhaustive_recurse(3),Some(2));assert_eq!(shortest_step_count_down(3),Some(2));}#[test]fnall_algos_work_for_twelve(){assert_eq!(shortest_step_exhaustive_recurse(12),Some(4));assert_eq!(shortest_step_count_down(12),Some(4));}#[test]fnall_algos_match_up_to_200(){foriin0..200{assert_eq!(shortest_step_count_down(i),shortest_step_exhaustive_recurse(i),"Algos don't match for {}",i);}}}
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
I wrote two versions of this. The first one I wrote was an exhaustive search. Then I read some answers here and wanted to write up the solution @savagepixie had and compared them. They matched on all the numbers I tested on (up to 200 in the test case).
At first I wasn't convinced that the 'simpler' solution of counting down was gonna work, but I was definitely wrong! It performs way better than my exhaustive search and seems to be just as accurate