F.
Appendix F: Chapter 6 Exercise & Challenge Solutions
Written by Massimo Carli
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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:
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
}
}
}
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}")
}
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) {
// ...
}
fun main() {
val id1 = Id.of(1)
val id2 = id1.copy()
println("${id1 == id2}") // 1
println("${id1 === id2}") // 2
}
true
false
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);
}
// ...
}
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.
Exercise 6.3 solution
To solve this problem, remember that:
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)
}
}
fun main() {
moveDisk(disks = 4, from = 1, to = 3, using = 2)
}
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
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)
}
fun noTailRecFactorial(n: Int, fact: Int = 1): Int = when (n) { // 2
1 -> fact
else -> noTailRecFactorial(n - 1, n * fact)
}
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
}
recursiveFactorial 92446751
tailRecFactorial 8587841
noTailRecFactorial 50125777
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)
}
fun noTailRecFib(n: Int): Int = when (n) {
0 -> 0
1 -> 1
else -> noTailRecFib(n - 1) + noTailRecFib(n - 2)
}
fun main() {
println(chrono {
noTailRecFib(40) // 1
})
println(chrono {
tailRecFib(40) // 2
})
}
527457813 // 1
12316 // 2