# Ric0chet's solution

## to Collatz Conjecture in the Scala Track

Published at Sep 20 2019 · 0 comments
Instructions
Test suite
Solution

The Collatz Conjecture or 3x+1 problem can be summarized as follows:

Take any positive integer n. If n is even, divide n by 2 to get n / 2. If n is odd, multiply n by 3 and add 1 to get 3n + 1. Repeat the process indefinitely. The conjecture states that no matter which number you start with, you will always reach 1 eventually.

Given a number n, return the number of steps required to reach 1.

## Examples

Starting with n = 12, the steps would be as follows:

1. 12
2. 6
3. 3
4. 10
5. 5
6. 16
7. 8
8. 4
9. 2
10. 1

Resulting in 9 steps. So for input n = 12, the return value would be 9.

The Scala exercises assume an SBT project scheme. The exercise solution source should be placed within the exercise directory/src/main/scala. The exercise unit tests can be found within the exercise directory/src/test/scala.

To run the tests simply run the command `sbt test` in the exercise directory.

For more detailed info about the Scala track see the help page.

## Source

An unsolved problem in mathematics named after mathematician Lothar Collatz https://en.wikipedia.org/wiki/3x_%2B_1_problem

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### CollatzConjectureTest.scala

``````import org.scalatest.{Matchers, FunSuite}

/** @version 1.2.0 */
class CollatzConjectureTest extends FunSuite with Matchers {

test("zero steps for one") {
CollatzConjecture.steps(1) should be (Some(0))
}

test("divide if even") {
pending
CollatzConjecture.steps(16) should be (Some(4))
}

test("even and odd steps") {
pending
CollatzConjecture.steps(12) should be (Some(9))
}

test("Large number of even and odd steps") {
pending
CollatzConjecture.steps(1000000) should be (Some(152))
}

test("zero is an error") {
pending
CollatzConjecture.steps(0) should be (None)
}

test("negative value is an error") {
pending
CollatzConjecture.steps(-15) should be (None)
}
}``````
``````import scala.annotation.tailrec
//  09-19-19

object CollatzConjecture {
// 28 ms -- FASTEST using tail recursion
@tailrec
def steps(start: Int, count: Int = 0): Option[Int] = start match {
case i if i < 1 => None
case 1 => Some(count)
case _ => steps(if (start % 2 == 0) start / 2 else start * 3 + 1,
count + 1)
}

// 38 ms -- FAST using recursion
def steps2(start: Int, count: Int = 0): Option[Int] = start match {
case i if i < 1 => None
case 1 => Some(count)
case _ => steps2(if (start % 2 == 0) start / 2 else start * 3 + 1,
count + 1)
}

// 69 ms -- SLOWER Lambda using (lazy) stream generator
def steps3(start: Int): Option[Int] =
if (start < 1) None
else Some(Stream.iterate(start) { i =>
if (i % 2 == 0) i / 2 else i * 3 + 1
}.indexOf(1))

// 67 ms -- SLOWER using lazy val to generate stream on-demand
def steps4(start: Int): Option[Int] = {
if (start < 1) return None

lazy val st: Stream[Int] = start #:: st.map { i =>
if (i % 2 == 0) i / 2 else i * 3 + 1 }

Some(st.indexOf(1))
// also works:  Some(st.takeWhile(_ > 1).size)
}

// 38 ms -- FAST using brute-force while
def steps5(start: Int): Option[Int] = {
if (start < 1) return None
var num = start
var count = 0

while (num > 1) {
num = if (num % 2 == 0) num / 2 else num * 3 + 1
count += 1
}
Some(count)
}

}``````