August 27, 2018

Exercism - Collatz Conjecture


I've been having a lot of fun doing the Exercism Clojure Track, and since I recently completed all 11 core exercises, have become a mentor.

The following problem is interesting, because right now I'm going to attempt to mentor my own mentor's solution. It turns out that he took a very different approach than I did, and I think this could be a great opportunity to dive in and learn some stuff.

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.

We begin with 2 placeholder functions and test suite. This code (and cljs.test framework) is live and interactive if you want to try it out.

(ns collatz-conjecture
  (:require [cljs.test :refer-macros [deftest testing is run-tests]]))
(defn collatz-step [num step]

(defn collatz [num]
(deftest steps-for-1
  (testing "zero steps for one"
    (is (= 0 (collatz 1)))))

(deftest steps-for-16
  (testing "divide if even"
    (is (= 4 (collatz 16)))))

(deftest steps-for-12
  (testing "even and odd steps"
    (is (= 9 (collatz 12)))))

(deftest steps-for-1000000
  (testing "Large number of even and odd steps"
    (is (= 152 (collatz 1000000)))))

This was my answer:

(defn collatz-step [num step]
   (= num 1) step
   (even? num) (collatz-step (/ num 2) (inc step))
   (odd? num) (collatz-step (inc (* num 3)) (inc step))))

(defn collatz [num]
  (collatz-step num 0))

The program works fine, all of the tests pass. I think it's actually rather clever the way it counts each time it calls itself.

However, I have obscured the whole intent of having a step function, which should only be doing one thing:

  • Generating the next step of the Collatz sequence given an existing element.

Then we would apply the function repeatedly until we reach one, and then count how many we've got.

If we take a look at my mentor's solution, we can see that these issues have been addressed and the concerns have been made explicit, producing a much more readable program:

(defn- collatz-step [num]
  (if (even? num) (/ num 2)
      (inc (* 3 num))))

(defn collatz [num]
  {:pre [(pos? num)]}
  (->> (iterate collatz-step num)
       (take-while (partial < 1))
Tags: coding exercises KLIPSE Exercism Clojure