Skip to content
1101s.wiki

Studio 4

Studio Worksheets

  1. Studio 4 Worksheet
  2. Studio 4 In-class Worksheet

Tower of Hanoi đź—Ľ

This is a classic tree recursion problem!

function hanoi (n, from, to, spare) {
    // YOUR SOLUTION HERE
}

// Examples
hanoi(3, 'A', 'C', 'B'); // 7
hanoi(4, 'B', 'C', 'A'); // 15
Answers

To move a disk, we need to move the disks above it first. Therefore, we can break the problem down into 3 parts:

  1. Move the top n-1 disks from from to spare
  2. Move the bottom disk from from to to
  3. Move the n-1 disks from spare to to
function hanoi (n, from, to, spare) {
    display(stringify(from) + " -> " + stringify(to)); 
    return n <= 1
            ? n
            : tower_of_hanoi(n-1, source, aux, target) +
              1 +
              tower_of_hanoi(n-1, aux, target, source);
}

thrice(thrice(thrice))

Let’s first start with thrice(thrice) from the studio sheet and recall whats the intuition behind it.

Interpreting thrice(thrice)

The important thing to note here is that when we are dealing with HOFs, we passing around computational sequences instead of “data”/primitive values that we were so used to doing in the first few weeks.

We know that when you call thrice(f)(x) where f is a function, we are composing a function that has a form of f(f(f(x))). In simple terms, we applying the function successively for total of three times.

Extrapolating that, when we do a thrice(thrice), we are composing a function of form thrice(thrice(thrice.... A additional point to note here is the function signature of thrice(thrice)

We will assume that input are of type Number here

// (Number -> Number) -> Number -> Number
// |        f       |   | input | | result |
function thrice(f) {
    return compose(compose(f, f), f);
}

// ( (Number -> Number) -> Number -> Number ) -> (Number -> Number) -> Number -> Number
// |            signature of `thrice`         |  |       f        |   | input | | output |
thrice(thrice)

Why 27 and not 9?

This is with respect to one of the studio questions when we call thrice(thrice)(x => x + 1)(0). Many (including me) would think that the result will be 9, but 🤯 when they realize it is supposed to be 27. Now, why is that so?

When we call thrice(thrice)(f), we observe that it will be composed into a function of form thrice(thrice(thrice(f))) (recall the effects of thrice(f)(x) mentioned above).

  1. Then the important thing to note here is that the most inner thrice(f) will be composed into the form of f(f(f and subsequently
  2. this f(f(f becomes the new computational sequence that is passed to the “middle” thrice.
  3. And just like how thrice(f) works, the second thrice will take f(f(f as the function to compose three times, resulting in fff (fff (fff
  4. Repeat the process and we will get fff fff fff (fff fff fff (fff fff fff

Now pluck in the original (x => x + 1) to thrice(thrice) and we will see that there are 3 * 3 * 3 = 27 successive applications of f. Therefore, thrice(thrice)(x => x + 1)(0) === 27.

One more thrice

Now it is time to answer the question of thrice(thrice(thrice)). With all that intuition we have built from thrice(thrice), let’s see what happens when we call thrice(thrice(thrice))(x => x + 1)(0).

  1. We know that thrice(thrice) results in a 3 * 3 * 3 = 27 applications
  2. Using the same logic from above, thrice(thrice(thrice)) then results in something like thrice(f{27})
    • f{27} means 27 successive applications of f
  3. Which means thrice(thrice(thrice)) -> thrice(f{27}) -> f{27}(f{27}(f{27}
  4. That is equals to 27 * 27 * 27 = 19683 successive applications

Some cool things you can do with HOFs