Rosetta Code: Towers of Hanoi

JavaScript
1

Tell us what’s happening:
Although the code output correct result in the console.log ( tried all the tests).
The solution didn’t pass them.
I can’t understand what’s wrong.
I return 2D array and all internal array are matching, but still not passing tests.
Bug??

Your code so far


var result = [];

function towerOfHanoi(n, a, b, c) {
if (n > 0) {
   towerOfHanoi(n - 1, a, c, b);
   result.push([a, b]);
   towerOfHanoi(n - 1, c, b, a);
 }
  return result;
}

console.log(towerOfHanoi(3, 'A', 'B', 'C'))

Your browser information:

User Agent is: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/81.0.4044.129 Safari/537.36.

Challenge: Towers of Hanoi

Link to the challenge:

2

image
image489×917 8.8 KB

So if I slap a console.log right before your return statement, the function returns multiple times. The test suite is grabbing that first return result and since it doesn’t match, failing.

1 Like
3

You shouldn’t be using a global variable here. You want to use true recursion and local variables.

1 Like
4

Thank you, make sense…

5

Then I will be not able to store the final result, coz if declare the variable inside the scope it will redefine after each self call (recursion )… right?

6

Nope, each function call has its own scope.

See:

function fibonacci(n) {
  if (n <== 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    let f_nMinusOne = fibonacci(n-1);
    let f_nMinusTwo = fibonacci(n-2);
    return f_nMinusOne + f_nMinusTwo;
  }
}

console.log(fibonacci(10));

This code wouldn’t work at, all if each function call changed the variables in other scopes.

Each declaration of the local variables is scoped to each function call. That’s the point of functions, function scope, and recursion.

See also the Free Code Camp lessons on recursion:



1 Like
7

The Fibonacci I solved in this way ( by knowing the algorithm) I use a bit of a trick;)
But there was no need to store the whole chain of actions

function fibonacci(n) {
 if (n < 3) return 1;
 return fibonacci(n-1)+fibonacci(n-2);
 }

With Hanoi exercise, I can print out pair by pair source -> destination.
And recursion works correct, but I can not get how to store pairs into an array ( not to lose them and not to repeat)
And I think I missed the best case.

However, Thank you :hugs: so much for the new recursion exercises. Looks like they were added recently, coz I didn’t have them when have been going through JS.
Probably it will give me a hint :face_with_monocle: :wink: :upside_down_face:

8

I solved with the use of helper function. Is there a more elegant way to solve it?
:face_with_monocle:
Don’t feel like this solution is the best one… but so far I was able to come with…

function towerOfHanoi(n, a, b, c) {
   var result = [];
   moveDisc(n, a, b, c, result)
   return result;
}

function moveDisc(n, a, b, c, result) {
   if (n > 0) {
      moveDisc(n - 1, a, c, b, result);
      result.push([a, b]);
      moveDisc(n - 1, c, b, a, result);
   }
}
console.log(towerOfHanoi(3, 'A', 'B', 'C'))
9

here, your more elegant solution comes from here

so, what would be the result from towerOfHanoi(n - 1, a, c, b) and from towerOfHanoi(n - 1, c, b, a)? how are those results put in the array in relation to [a, b]?

instead of pushing, create an array with these, using concat or the spread operator, and return the value returned from these

after that you just need to consider what the base case should be, instead of returning result, maybe an empty array?

1 Like
10

Thank you for the explanation… :hugs:
The solution with concat is more complicated for me. It took a while to understand what should be concatenated to what… :exploding_head:
But it definitely cleaner and simpler when you got the understanding…

function towerOfHanoi(n, a, b, c) {
 if(n==0){
    return []
 }
  else if (n > 0) {
return  towerOfHanoi(n - 1,a, c, b).concat([[a,b]
 ]).concat(towerOfHanoi(n - 1, c, b, a))
   }
}
11

I would have done something like [...towerOfHanoi(n - 1,a, c, b), [a,b], ...towerOfHanoi(n - 1, c, b, a)

but congratulations!

also, as a suggestion, instead of n===0, try using n < = 0 or if for some reason a negative n is inserted, you get infinite recursion

2 Likes
12

Love it! beauty in its simplicity :heart_eyes: