September 9, 2018

Perfect Numbers

This blog posts a lot of exercises and solutions (in Clojure) for some well known challenges aroung the web. I read the post about Perfect Numbers and happened to be the same exercise that I had finished to 4clojure, so I decided to share my solution here too.

Specially because after studying the juxt solution I got intrigued by how different both of our code were.

Let's take a look.

My solution is a little but shorter and concise.

Proposed solution from blog:

(ns live.test
  (:require [cljs.test :refer-macros [deftest is testing run-tests]]))

(defn perfect-nums [x]
  (apply =
       ((juxt (comp (partial reduce +)
                    (partial apply filter)
                    (juxt (partial partial
                                   (comp zero? rem))
                      (partial range 1)))
          identity) x)))

(deftest perfect-nums-test
  (is (= (perfect-nums 6) true))
  (is (= (perfect-nums 7) false))
  (is (= (perfect-nums 496) true))
  (is (= (perfect-nums 500) false))
  (is (= (perfect-nums 8128) true)))

(run-tests)

My solution:

(ns demo.core
  (:require [clojure.test :refer :all]))

(defn perfect-number? [n]
  (= n (reduce + (map #(if (= (mod n %) 0) % 0) (range 1 n)))))

(deftest perfect-number?-test
  (is (= (perfect-number? 6) true))
  (is (= (perfect-number? 7) false))
  (is (= (perfect-number? 496) true))
  (is (= (perfect-number? 500) false))
  (is (= (perfect-number? 8128) true)))

(run-tests)

However, don't fool yourself. I time the two solutions for the perfect number 33550336 and the juxt solution took half the time to perform the validation. For larger numbers, both performed badly.

I managed to compact a little bit more my previous solution by only using the reduce operator.

(defn perfect-number? [n]
  (= n (reduce #(if (= (rem n %2) 0)
                  (+ %1 %2)
                  %1) (range 1 n))))

With the second version I got the same amount of time as the juxt solution. Uuurrraaayyy!! The two big improvements was removing the map operation that was not necessary, change mod to rem. If you look at the mod implementation below, it has more branches to satisfy than the rem implementation which is calling the Java method right away. They are not the same operations.

(defn mod
  "Modulus of num and div. Truncates toward negative infinity."
  {:added "1.0"
   :static true}
  [num div]
  (let [m (rem num div)]
    (if (or (zero? m) (= (pos? num) (pos? div)))
      m
      (+ m div))))
(defn rem
  "remainder of dividing numerator by denominator."
  {:added "1.0"
   :static true
   :inline (fn [x y] `(. clojure.lang.Numbers (remainder ~x ~y)))}
  [num div]
    (. clojure.lang.Numbers (remainder num div)))

Good exercise though.

Best

Tags: clojure functions