Collatz Conjecture

I find it interesting how how the language I write code in shapes the solution I gravitate towards. The other day I realized that I had solved the same problem Collatz Conjecture from exercism.io in three different languages.

From exercism the assignment text is as follows:

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.

Haskell

In haskell guards | are readily available and it is very easy to create recursive functions using guards with base cases. My solution ended up like this:

collatz :: Integer -> Maybe Integer
collatz n | n <= 0    = Nothing
          | n == 1    = Just 0
          | even n    = fmap (+1) $ collatz $ div n 2
          | otherwise = fmap (+1) $ collatz $ n * 3 + 1

Clojure

With clojure having iterators in the root namespace they are always at the forefront of my mind when coding clojure. its easy to create a pattern with where we have an infinite sequence of next-collatz that we take form until we reach our predicate:

(defn next-collatz
  [n]
  (if (even? n)
    (/ n 2)
    (+ 1 (* 3 n))))

(defn collatz [n]
  (->> (iterate next-collatz n)
       (take-while #(not= % 1))

Scala

I write scala in my day job currently. Normally I would not think to use iterators for this so perhaps this is a bad example in the context of this post.

When writing this in Scala I was colored by remembering how I solved this in Clojure. I am however happy with how it ended up and I think I will try to reach for iterators more often in Scala also.

private def isEven(i: Int): Boolean = i % 2 == 0
private def nextCollatz(n: Int): Int =
  if (isEven(n)) n / 2
  else n * 3 + 1

// The solution in exercism requires that you use `Option`
def steps(n: Int): Option[Int] =
   Option(n)
     .filter(_ > 0)
     .map(Iterator.iterate(_)(nextCollatz).indexWhere(_ == 1))