10
\$\begingroup\$

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) 
\$\endgroup\$
  • \$\begingroup\$ Your code contains an invalid test and your test contains an exact copy of your code. Is this intended/your real code? \$\endgroup\$ – Nobody Jul 2 '14 at 8:57
  • 3
    \$\begingroup\$ Have a look on difference between DFS and BFS. You are now using DFS and if you want the shortest sequence, I would recommend using BFS. \$\endgroup\$ – martijnn2008 Jul 2 '14 at 10:59
  • \$\begingroup\$ Fun fact: it's not his code. It's from Eloquent Javascript, 3rd edition. \$\endgroup\$ – AleksandrH Dec 16 '18 at 1:06
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "'ll leave the fun part of implementing this up to you :)" Fun is the least of the words I'd use to describe this problem. Solving the problem in reverse is a total pain in the ass in terms of reversing the "history" string you've built up. \$\endgroup\$ – AleksandrH Dec 16 '18 at 1:40
  • \$\begingroup\$ Okay, after cooling off a bit and trying this again, I figured out that I can get a string in prefix notation (e.g., * 3 + 5 * 3 1) if I work in reverse, so then all I need to do is convert it to infix notation. \$\endgroup\$ – AleksandrH Dec 16 '18 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy