Find sequence by adding 5 or multiplying by 3

Question

I wrote this little JavaScript function that starts with the number 1 and continually either adds 5 or multiplies by 3. This function tries to find a sequence of additions and multiplications that find that number.

Keep in mind, this function does not necessarily find the shortest sequence of operations.

I am looking for a review of my code and possible ways to make it more optimized. I'm also open to suggestions about how I can go about having this function find the shortest sequence of operations.

My code:

function findSequence(goal) {
  function find(start, history) {
    if (start == goal)
      return history;
    else if (start > goal)
      return null;
    else
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }
  return find(1, "1");
}

Test:

print(findSequence(178));

Output:

((((((((((((((1 + 5) + 5) + 5) + 5) + 5) + 5) + 5) + 5) + 5) + 5) + 5) * 3) + 5) + 5) 

Answer 1

This question is a bit related to a previous question. I will give you the same advice I did to the asker of the previous question.

Work from the other direction.

Currently, you're branching out starting from 1 trying to reach 178. Instead, start from 178 and try to reach 1. I'll show you how that will make the problem a lot easier.

• We're at 178. Can we divide by 3? 178 mod 3 != 0 so no. Instead we reduce by 5.
• 178 - 5 == 173. Can we divide by 3? 173 mod 3 != 0 so no, we reduce by 5 instead.
• 173 - 5 == 168. Can we divide by 3? 168 mod 3 == 0 so yes, we can. Let's do that.
• 168 / 3 == 56. Wait a minute... this number ends with a 6... Interesting. (56 - 1) mod 5 equals zero, so from here we can just reduce by 5 until we've reached our target of 1.

Instead of branching out in an exponential manner, we've reduced the problem to a linear approach. Simply by flipping things backwards.

Let's say that we don't want to do the end loop of reducing by 5 just because we can (we want the shortest path, right?), then I see no other solution than to branch out recursively. When checking for the division by 3, a lot of branches are removed so it will be possible to find the shortest path by branching.

I'll leave the fun part of implementing this up to you :)

Some comments about your current code

(Which, given the comments above you should remove and completely re-write using the "backwards" approach)

In Java at least, it's recommended to add braces for each if. Also, as you're using return inside each if there's no need for else.

function findSequence(goal) {
  function find(start, history) {
    if (start == goal) {
      return history;
    }
    if (start > goal) {
      return null;
    }
    return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }
  return find(1, "1");
}

I would also add a parameter to allow switching the start value, it will make it more flexible very easily.

I think it's good that you're hiding the find method inside the other function.