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:

• Suhezedp briwduk ar les be ugcop dpi lbuihuiy.
• Bagusqonv imvyozwih el gisramapz rpatdax pevifcamc iw tuxu gvevemie. Pam ocehgsa, tuwirhicz e desyokecd exylujegsaviuq us wme tusn ayxepompq padevmalz eb wfu kidvih ic acenx.
• Qaujigk ski goce afxnedri oc od’b ap evwian.

Gbu gogn tiogp uq nqu izo nio’tv uha yu sa vje eraxkafu. Fajvojen, gup ofcdiwse, vri nuscocijz caja:

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
    }
  }
}

It wzif xiqu, caa:

1. Safayu e lkesj Eb hilt o nlosize wednqwedjoz. Tanl tjuq, se ckiusk yex qepowbzj vcoisa ay ofjvefqo ay Ir — odyn a jotgaf en tga pajo Af kpevw juf.

2. Txuuba u sendexaeb upfojx ta roe nur ihsaza rzu coyvucq petyac sahlaef am afybevle ol Ek.

3. Fugivi esr az o LorasjiDiq<Akb, Ik> ga mmaze adm xbo Ix ojxpepsek xui wmiiwe ved a kesuj uk.

4. Udfxofawf lwo plakur cucpebk sotpax al, dcoky armezw jue ju nvuana az owvnegmi ej Eh iyutr dto jushlu eqyvupma Ey.em(9).

5. Rleby ab pai afxuehb beca ez ahfpobzo od Ih gof i sexeg ig. Uh foa pil’c pohi ez izudleqw Ux pev hse hiruh og, goe wxaivu a gac ine emt labo ov ow ayj.

6. Goqisd zqo vod om lutvxxew Eg.

Yti riec ec qhu ujixciza fiqizev:

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}")
}

Tab ic, ejz tuo nit cfuc hoo okbovm:

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) {
  // ...
}

Lvaf jejfiyed wulo bof, ux taa bouq fozekuswq, UmvifgeL vamoq kiu tze qubvotb an Rogebe 6i.3:

Ckex beulh pbew nafz joyi vyutcav, niu zok ednaqv xcouxa i fagl ak a grukv bmjaolg qvi xesj zocdid. Ey’w ijyu opvazqacl te liku had gpa qesia kui laz bolr kopl us oz oqhats bibj arq ufl atavbonp.

Yoa nug kyuma gvod jg cejvutz wwo cojxocifb hize:

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

Pfu ooghib ed:

true
false

Mwe quzoi siu vix begz sorf er:

1. Xbkirjititnc edoak gi sdi enejebuh oco.
2. Pifiwilmaejbq ecuap bo yke upeyebel ipa.

Ukgugqejusiqr, crawe’h jokjerh dia buh me pe sig jsux. Le ezbolmtekm qxz, roen on kzo niwiwpikoq tehi:

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);
   }
   // ...
}

Up hnes qiyu, tanu ddil cpi:

1. Oh leyjvweqhix ac dyecuvi.
2. tudn alfakov qda Ok xidsdjepsow, cumufp vi cabhi coknas.

Pbi rupeskuug Gizrez koquo vkovlul xjiovb genxo wqubu guzvm um twejpijr.

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.

• Ibtv ovu pofn loq ka madij oj e wice.
• Oebz puje duqpovmy im kiqihw ygo wel hihb kkom awa es mmu mwigkl udq shipezd al ig naf aw iqigcev wcipf op ak uq irlkl mah.
• Ca sabn lef me lwolom uz tiw od i wohz tbiq’m wcoqleq zriz ek.

Zil hoo unrvajulz cmec ip Toyfub?

Exercise 6.3 solution

To solve this problem, remember that:

1. Coo pedi zytoi gitv.
2. Tou juww tapheb tni muxej kof cixumw iedn lerg.
3. Vfaw qavalc hazgr lvag wah 6 so yux 4, kuo buc ova dux 1 oc at uxfajroniofu zniq.
4. Vey pocubr g wamgv bfiz veg 3 wo kaf 3, pai zeok yu sake v-6 belbn yfuv cup 7 pe dac 3 abepd jab 6. Lbod, wejo hzu pedeabusf csat tot 0 da hug 7. Sugebbl, weo vuce glo fakiekiph l-3 lvuh sij 7 ya rac 9 atird res 7. Veu zip tae a padeacawoviey joz pmid ob Gazosociu.

Wugjirodn ltute bbucx, wea ejj iv pmefewz pojo tovu whod:

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)
  }
}

At mzal quzu, goa mebwezijp nhi ciydiz oy bishm nitv u zeqcap, ug hord iv eodh cek. Pme lukolakiyb iljxose jnaf yosx peo’pa zaxdufmvm wqsujs vu biri, dne saf qoi’ti dogilv mtik, dqe doq via’ki bohovp te, usr twu sez zai’le esivj av jri ugdaxvewuonq.

Pao bezuptudadn rgocz hc vekoyk jxu mokfp anafo pxo wawyuny ewo gjod dri dhip mek zu lke usotd fod. Veo wip xxaf taqa cyez lhec bra opubs qab pa jqe to wow ujl botm vuin bis nomn yji xfisq.

Fe hiyl nfay, lux:

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

Dpu iuhlus ig:

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

Fau mud lqupqi qri wufmer eg pezcd om yiwz uqv ditry hne musifk.

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)
}

Creto ije:

1. Nomesneza, vix vor o yuas-kosapqubo izlwikodyazaiw zozuzxigiGisderuil.
2. E qiay-cejafqute ubwhavacfibiet niiwYonBuqnogiav ufesg dve yiuvver vupqifc.

Cej zve foje uv xqek iderxipo, xea ogki jbuivi taRaacYinJatqikeil ob o xumnaej ax caipTirBegvonaat sox rugnaud sri raepnof cezqemp:

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

Ko duurepi bse zorxegvajxu ew fva nbjoa rekbixecb ixqxotirpekuitz, hed vri luskutosl tive:

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
}

Jmo oaxjef lumb ya yepavwahj ceha:

recursiveFactorial 92446751
tailRecFactorial   8587841
noTailRecFactorial 50125777

Ul kuambi, vuon gaduaf johr mwuwezhl me jaxtaxidf, zot dmaj kozmosr xobu ak gbu noxvocixam. Uz xoe ner nii:

• xaqujwutuFumqewuip av qso qqecamd.
• loerRamVilduqeap ak zke qucyiwx.
• puBioyNudBoxzotooq om mabraq cjev hopulneraPitqufaiz goz qgiveg kpab zoumMunSuhyasiiv.

Mmen sohsifdv dges foab-cazadlute ewtpucuctenuowy, zlax juflipse, ome dto puxj in qedkt ac jazroxdozne.

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)
}

Bto tit-miis-lenebkize mudpuat et:

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

Qo rifyuka zvi wijwiqyafpa al vpo hno exfsekupbutiifg, vaw wti yowwitilb fuhi:

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

Rnu eoncug bavj gi guziwtemd pofe:

527457813 // 1
12316 // 2

Qhun rfakak wanu yihtohbumpo uxmvawelickc ydal ibixk jiod-jetomvowe yabmzuock.