DEV Community

Daily Challenge #24 - Shortest Step

dev.to staff on July 25, 2019

Today's challenge comes from user bdowds on CodeWars. Given a number, return the shortest amount of steps it would take from 1 to land exactly on...
Collapse
 
wheatup profile image
Hao • Edited

If you convert the number to binary, the steps are exactly

(number of 1s - 1) * 2 + number of 0s

2  -> "10"   -> (1 - 1) * 2 + 1 = 1 step
7  -> "111"  -> (3 - 1) * 2 + 0 = 4 steps
12 -> "1100" -> (2 - 1) * 2 + 2 = 4 steps

This way we don’t need loops or recursion.

String.prototype.count = function(char){
  return this.split(char).length - 1;
}

function countSteps(n) {
  let binary = n.toString(2);
  return (binary.count('1') - 1) * 2 + binary.count('0');
}
Collapse
 
maxart2501 profile image
Massimo Artizzu

I was about to submit something like that, so have my applause instead πŸ‘πŸŽ‰

A little more thinking on the problem can really simplify the solution!

(On a side note, I wouldn't extend a native prototype, but that's out of context now πŸ˜…)

Collapse
 
wheatup profile image
Hao

That was my original version, then I thought writing two functions might confuse people so I changed it into this. It's just for the sake of demonstration and better readability.πŸ€—But you were right, it is a bad habit to extend a native prototype.

Collapse
 
coreyja profile image
Corey Alexander

Wow this is brilliant! Nice job!

Collapse
 
savagepixie profile image
SavagePixie • Edited

There is probably a better way that doesn't use loops, but these are my initial thoughts:

(using JavaScript)

function countSteps(n) {
   let steps = 0
   while (n > 1) {
      n % 2 == 0 ? n /= 2 : n--
      steps++
   }
   return steps
}
Collapse
 
andreasjakof profile image
Andreas Jakof

That was my idea as well.

Collapse
 
_jayantsharma profile image
Jayant Sharma

How would you come to this concept as I have no idea of this concept to far extend. Have you done these type of quest. or this(concept of using modulus) is the only way of solving this problem?

Collapse
 
savagepixie profile image
SavagePixie • Edited

Well, I imagine that there are other ways to solve it. I came to it when I realised that it wasn't a coding problem as much as a maths problem. There are two key things that we know:

  • For natural numbers, doubling a number always makes it bigger than adding one (except when the number is 1, then it doesn't matter). So adding one is only needed to reach numbers with odd divisors
  • The number that we need to reach

Therefore, since we know the number that we need to reach, it is a lot quicker to work backwards (from the number we need to reach) than to make guesses from number 1. Starting from the end, every time we get to an odd number we subtract 1 (the backward of adding one) and every time we get to an even number we divide by 2 (the backward of multiplying by two).
Since we are dividing by 2 every time we can, that'll ensure that we're always taking as few steps as possible.
Since the amount of steps is the same whether we go 1->n or n->1, working backwards will give us the same result.

Collapse
 
avalander profile image
Avalander

Here's some recursion. I think it will work, but I'm not sure since I'm on my phone, I'll test it when I get home.

const steps = (n, acc = 0) =>
  n === 1
    ? acc
    : n % 2 === 0
    ? steps(n / 2, acc + 1)
    : steps(n - 1, acc + 1)
Collapse
 
coreyja profile image
Corey Alexander

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

pub fn shortest_step_exhaustive_recurse(num: u64) -> Option<u64> {
    fn recursive_helper(cur: u64, goal: u64) -> Option<u64> {
        if cur == goal {
            Some(0)
        } else if cur > 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)
}

pub fn shortest_step_count_down(num: u64) -> Option<u64> {
    if num == 0 {
        None
    } else if num == 1 {
        Some(0)
    } else if num % 2 == 0 {
        Some(1 + shortest_step_count_down(num / 2)?)
    } else {
        Some(1 + shortest_step_count_down(num - 1)?)
    }
}

#[cfg(test)]
mod tests {
    use crate::*;

    #[test]
    fn all_algos_work_for_three() {
        assert_eq!(shortest_step_exhaustive_recurse(3), Some(2));
        assert_eq!(shortest_step_count_down(3), Some(2));
    }

    #[test]
    fn all_algos_work_for_twelve() {
        assert_eq!(shortest_step_exhaustive_recurse(12), Some(4));
        assert_eq!(shortest_step_count_down(12), Some(4));
    }

    #[test]
    fn all_algos_match_up_to_200() {
        for i in 0..200 {
            assert_eq!(
                shortest_step_count_down(i),
                shortest_step_exhaustive_recurse(i),
                "Algos don't match for {}",
                i
            );
        }
    }
}

Collapse
 
alvaromontoro profile image
Alvaro Montoro • Edited

Elixir

defmodule Challenge do
   def shortest_step(n) when n <= 1 do
      0
   end

   def shortest_step(n) do
      if rem(n,2) == 0 do
        1 + shortest_step(div(n, 2))
      else 
        1 + shortest_step(n-1)
      end
   end
end

First time doing anything on Elixir. It was fun :)

Live demo on Paiza.io.

Collapse
 
brightone profile image
Oleksii Filonenko • Edited

Elixir:

defmodule ShortestStep do
  import Integer

  @spec steps(non_neg_integer) :: non_neg_integer
  def steps(start) when start > 0, do: do_steps(start)

  @spec do_steps(non_neg_integer) :: non_neg_integer
  defp do_steps(1), do: 0
  defp do_steps(current) when is_odd(current), do: do_steps(current - 1) + 1
  defp do_steps(current), do: do_steps(div(current, 2)) + 1
end

Recursive thinking is fun :)

Collapse
 
willsmart profile image
willsmart • Edited

JS using a bit of bitwise math


// Wow,.. fancy :|
step = n => (n&~1) >> ((~n)&1)    // note that they're ~'s, not -'s

// Count how many times we need to iterate step until it hits 0
countSteps = n => {
  if (n<=0 || Math.floor(n)!==n) throw new Error(`countSteps only accepts positive integers, ${n} was passed`);

  let count =0;
  while (n=step(n)) count++;
  return count;
}

(couple of edits to make it cleaner)

Collapse
 
peter279k profile image
peter279k

Here is the simple solution with Python:

def shortest_steps_to_num(num):
    steps = 0
    if num == 1:
        return steps

    while num != 1:
        if num % 2 == 0:
            num /= 2
            num = int(num)
        else:
            num -= 1

        steps += 1

    return steps
Collapse
 
udiudi profile image
Udi • Edited

Ruby:

number = 12

def step(n, step)
  return step if n == 1

  n = n % 2 == 0 ? n / 2 : n -= 1
  step(n, step + 1)
end

puts step(number, 0)

:)

Collapse
 
ynndvn profile image
La blatte

And here goes an ugly one!

a=(i)=>{t=-1;while(i){i%2?i--:i/=2;++t}return t}