 # hsmak's solution

## to Collatz Conjecture in the Scala Track

Published at Nov 18 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.

Please see the learning and installation pages if you need any help.

## 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)
}
}``````
``````object CollatzConjecture {

def even(n: Int) = n % 2 == 0

def odd(n: Int) = !even(n)

def steps(n: Int): Option[Int] = {
def loop(n: Int, acc: Int): Option[Int] = n match {
case 1 => Some(acc)
case n if n <= 0 => None
case n if even(n) => loop(n / 2, acc + 1)
case n if odd(n) => loop(n * 3 + 1, acc + 1)
}

loop(n, 0)
}

/*------------------- Another version via LazyList/Stream ---------------*/

def nextOp(n: Int): Int = if (even(n)) n / 2 else n * 3 + 1

def steps2(n: Int): Option[Int] = n match {
case n if n > 0 => Some(LazyList.iterate(n)(nextOp).takeWhile(_ != 1).length)
case _ => None
}
}``````