F. Appendix F: Chapter 6 Exercise & Challenge Solutions

Written by Massimo Carli

Exercise 6.1

In this section, you learned it’s useful to avoid creating multiple instances of immutable classes because they represent the same value. Given the following immutable class Id:

 class Id(val id: Int)

How would you change it to prevent any client from creating multiple instances of Id for the same id?

When you run this code:

 fun main() {
   val id1 = // Create Id for id = 1
   val id2 = // Create Id for id = 1
   val id3 = // Create Id for id = 2
   val id4 = // Create Id for id = 2
   println("${id1 === id2}")
   println("${id1 === id2}")
   println("${id1 === id3}")
   println("${id3 === id4}")
}

You get:

true
true
false
true

Exercise 6.1 solution

In Effective Java — the book by Joshua Bloch mentioned earlier in the chapter — “Item 1” states: “Consider using static factory methods instead of constructors”. This is because they allow you to control the way an instance of a class is created. In this case, “controlling” means:

• Deciding whether or not to allow the creation.
• Returning instances of different classes depending on some criteria. For example, returning a different implementation of the sort algorithm depending on the number of items.
• Reusing the same instance if it’s an option.

The last point is the one you’ll use to do the exercise. Consider, for instance, the following code:

class Id private constructor(val id: Int) { // 1
  companion object { // 2
    private val ids = mutableMapOf<Int, Id>() // 3
    fun of(id: Int): Id { // 4
      var existingId = ids[id]
      if (existingId == null) { // 5
        existingId = Id(id)
        ids[id] = existingId
      }
      return existingId // 6
    }
  }
}

In this code, you:

1. Define a class Id with a private constructor. With this, no client can directly create an instance of Id — only a method of the same Id class can.

2. Create a companion object so you can invoke the factory method without an instance of Id.

3. Define ids as a MutableMap<Int, Id> to store all the Id instances you create for a given id.

4. Implement the static factory method of, which allows you to create an instance of Id using the simple instance Id.of(1).

5. Check if you already have an instance of Id for a given id. If you don’t have an existing Id for the given id, you create a new one and save it in ids.

6. Return the new or recycled Id.

The main in the exercise becomes:

fun main() {
  val id1 = Id.of(1)
  val id2 = Id.of(1)
  val id3 = Id.of(2)
  val id4 = Id.of(2)
  println("${id1 === id2}")
  println("${id1 === id2}")
  println("${id1 === id3}")
  println("${id3 === id4}")
}

Run it, and you get what you expect:

true
true
false
true

Exercise 6.2

What happens if the Id class in Exercise 6.1 is a data class?

Exercise 6.2 solution

To see what happens when Id is a data class, you just need to add data to the class declaration:

data class Id private constructor(val id: Int) {
  // ...
}

This compiles fine but, if you look carefully, IntelliJ gives you the warning in Figure 6a.1:

This means that with data classes, you can always create a copy of a class through the copy method. It’s also important to note how the value you get with copy is an object with its own identity.

You can prove this by running the following code:

fun main() {
  val id1 = Id.of(1)
  val id2 = id1.copy()
  println("${id1 == id2}") // 1
  println("${id1 === id2}") // 2
}

The output is:

true
false

The value you get with copy is:

1. Structurally equal to the original one.
2. Referentially equal to the original one.

Unfortunately, there’s nothing you can do to fix this. To understand why, look at the decompiled code:

public final class Id {
   // ...
   private Id(int id) { // 1
      this.id = id;
   }

   @NotNull
   public final Id copy(int id) { // 2
      return new Id(id);
   }

   // $FF: synthetic method
   public static Id copy$default(Id var0, int var1, int var2, Object var3) {
      if ((var2 & 1) != 0) {
         var1 = var0.id;
      }

      return var0.copy(var1);
   }
   // ...
}

In this code, note that the:

1. Id constructor is private.
2. copy invokes the Id constructor, making de facto public.

The potential Kotlin value classes should solve these kinds of problems.

Exercise 6.3

The Tower of Hanoi is a classic example of a recursive function. It is a famous game consisting of three rods and a set of n disks of different radii. At the beginning, all the disks are stacked on the first rod. You need to move all the disks from the first rod to the third, following some rules.

• Only one disk may be moved at a time.
• Each move consists of taking the top disk from one of the stacks and placing it on top of another stack or on an empty rod.
• No disk may be placed on top of a disk that’s smaller than it.

Can you implement this in Kotlin?

Exercise 6.3 solution

To solve this problem, remember that:

1. You have three rods.
2. You must follow the rules for moving each disk.
3. When moving disks from rod 1 to rod 3, you can use rod 2 as an intermediate step.
4. For moving n disks from rod 1 to rod 3, you need to move n-1 disks from rod 1 to rod 2 using rod 3. Then, move the remaining from rod 1 to rod 3. Finally, you move the remaining n-1 from rod 2 to rod 3 using rod 1. You can see a visualization for this on Wikipedia.

Following these steps, you end up writing code like this:

fun moveDisk(disks: Int, from: Int, to: Int, using: Int) {
  if (disks > 0) {
    moveDisk(disks - 1, from, using, to)
    println("Moving $disks from $from to $to")
    moveDisk(disks - 1, using, to, from)
  }
}

In this code, you represent the number of disks with a number, as well as each rod. The parameters include what disk you’re currently trying to move, the rod you’re moving from, the rod you’re moving to, and the rod you’re using as the intermediary.

You recursively start by moving the disks above the current one from the from rod to the using rod. You can then move them from the using rod to the to rod and work your way down the stack.

To test this, run:

fun main() {
  moveDisk(disks = 4, from = 1, to = 3, using = 2)
}

The output is:

Moving 1 from 1 to 2
Moving 2 from 1 to 3
Moving 1 from 2 to 3
Moving 3 from 1 to 2
Moving 1 from 3 to 1
Moving 2 from 3 to 2
Moving 1 from 1 to 2
Moving 4 from 1 to 3
Moving 1 from 2 to 3
Moving 2 from 2 to 1
Moving 1 from 3 to 1
Moving 3 from 2 to 3
Moving 1 from 1 to 2
Moving 2 from 1 to 3
Moving 1 from 2 to 3

You can change the number of disks as well and watch the result.

Exercise 6.4

Tail-recursive functions usually provide better performance. Can you prove this using the chrono function in Util.kt?

/** Utility that measures the time for executing a lambda N times */
fun chrono(times: Int = 1, fn: () -> Unit): Long {
  val start = System.nanoTime()
  (1..times).forEach({ fn() })
  return System.nanoTime() - start
}

Exercise 6.4 solution

In the chapter, you encountered different recursive implementations for the factorial of a number n:

fun recursiveFactorial(n: Int): Int = when (n) { // 1
  1 -> 1
  else -> n * recursiveFactorial(n - 1)
}

tailrec fun tailRecFactorial(n: Int, fact: Int = 1): Int = when (n) { // 2
  1 -> fact
  else -> tailRecFactorial(n - 1, n * fact)
}

These are:

1. Recursive, but not a tail-recursive implementation recursiveFactorial.
2. A tail-recursive implementation tailRecFactorial using the tailrec keyword.

For the sake of this exercise, you also create noTailRecFactorial as a version of tailRecFactorial but without the tailrec keyword:

fun noTailRecFactorial(n: Int, fact: Int = 1): Int = when (n) { // 2
  1 -> fact
  else -> noTailRecFactorial(n - 1, n * fact)
}

To measure the performance of the three different implementations, run the following code:

fun main() {
  val times = 1000000
  println("recursiveFactorial ${chrono(times) {
    recursiveFactorial(50)
  }}") // 1
  println("tailRecFactorial   ${chrono(times) {
    tailRecFactorial(50)
  }}") // 2
  println("noTailRecFactorial ${chrono(times) {
    noTailRecFactorial(50)
  }}") // 3
}

The output will be something like:

recursiveFactorial 92446751
tailRecFactorial   8587841
noTailRecFactorial 50125777

Of course, your values will probably be different, but what matters here is the comparison. As you can see:

• recursiveFactorial is the slowest.
• tailRecFactorial is the fastest.
• noTailRecFactorial is faster than recursiveFactorial but slower than tailRecFactorial.

This suggests that tail-recursive implementations, when possible, are the best in terms of performance.

Challenge 6.1: Immutability and recursion

In “Immutability and recursion”, you implemented recAddMulti5 as a recursive function. Is the loop internal function tail recursive?

Challenge 6.1 solution

Yes, you can write recAddMulti5 like this, adding tailrec to loop:

fun recAddMulti5(list: List<Int>): Int {
  tailrec fun loop(i: Int, sum: Int): Int = when { // HERE
    i == list.size -> sum
    list[i] % 5 == 0 -> loop(i + 1, sum + list[i])
    else -> loop(i + 1, sum)
  }
  return loop(0, 0)
}

fun main() {
  val list = listOf(1, 5, 10, 12, 34, 55, 80, 23, 35, 12, 80)
  println(recAddMulti5(list))
}

Challenge 6.2: Tail-recursive Fibonacci

Fibonacci is one of the most famous sequences you can implement using recursion. Remember, the nth Fibonacci number is the sum of the two previous Fibonacci numbers, starting with 0, 1, 1.... Can you implement it as a tail-recursive function? Can you prove the tail-recursive function has better performance than the non-tail-recursive companion?

Challenge 6.2 solution

You can implement a function that provides the nth value in the Fibonacci sequence with a tail-recursive function like this:

tailrec fun tailRecFib(n: Int, a: Int = 0, b: Int = 1): Int = when (n) {
  0 -> a
  1 -> b
  else -> tailRecFib(n - 1, b, a + b)
}

The non-tail-recursive version is:

fun noTailRecFib(n: Int): Int = when (n) {
  0 -> 0
  1 -> 1
  else -> noTailRecFib(n - 1) + noTailRecFib(n - 2)
}

To compare the performance of the two implementations, run the following code:

fun main() {
  println(chrono {
    noTailRecFib(40) // 1
  })
  println(chrono {
    tailRecFib(40) // 2
  })
}

The output will be something like:

527457813 // 1
12316 // 2

This proves huge performance improvements when using tail-recursive functions.