8
\$\begingroup\$

I was inspired by a certain recent question to try my hand at this challenge:

Project Euler #34: Digit factorials

\$19!\$ is a curious number, as \$1!+9!=1+362880=362881\$ is divisible by \$19\$.

Find the sum of all numbers below \$N\$ which divide the sum of the factorial of their digits. Note: as \$1!,2!,\cdots,9!\$ are not sums, so they are not included.

Input Format: Input contains an integer \$N\$

Output Format: Print the answer corresponding to the test case.

Constraints: \$10^1 \le N \le 10^5\$

Sample Input

20

Sample Output

19

The code works great, with the only unfortunate problem being outside of my control, but is preventing me from completing the "official" HackerRank challenge: STDIN doesn't work (yet) with . I Googled this and Stack Overflowed that, and seems everyone is having issues (even simple STDIN on HackerRank website using Clojure language errors out) so I know it's not just me. The function that directly addresses the challenge is sum-all-curious-numbers-up-to.

I wrote a whole bunch of tests to ensure that everything was working correctly. I also included some benchmark tests at the bottom of the post, as I am also interested in improving performance, if there is an idiomatic way to do so.

This is my first "real" challenge using FP and so I would like criticism on any and all aspects of the code, including algorithms/logic, style and tests. I also have a few specific areas of focus that I would like addressed in more general terms:

  1. Is it idiomatic FP to throw exceptions, such as IllegalArgumentException which I often do here, or would it make more sense to return a falsey value when functions are passed an argument they are not designed to handle?

  2. Specifically with explode-num-to-digits (and consequently test-explode-num-to-digits) is that function trying to handle too many edge cases? I thought it would be "neat" to be able to accept numbers as strings and parse those the same as a regular number, but does it even make sense for this function to handle such arguments?

Note: I added a ;` and ;' at the end of a line near the top of the files, these are to compensate for the fact the Lisp syntax highlighting on Code Prettify/SE is borked.

HackerRankProjectEuler34.clj

(ns
  ^{:author Phrancis}
  sandbox.HackerRankProjectEuler34)

;; HackerRank Project Euler #34: Digit factorials
;; https://www.hackerrank.com/contests/projecteuler/challenges/euler034

(defmacro throw-number-exc
  "Shortcut 'not a number' exception with optional argument"
  ([]
    `(throw (IllegalArgumentException. "Not a number"))) ;`
  ([arg]
    `(throw (IllegalArgumentException. (str "Not a number: " ~arg)))) ;`
  ([arg msg]
    `(throw (IllegalArgumentException. (str ~msg " " ~arg))))) ;`

(defn exponent
  "Given a number N, returns N^x (i.e. N to the power of x)"
  [N x]
  (if (and (number? N) (number? x))
    (cond
      (= N 0) 0
      (= x 0) 1
      (> x 0) (reduce * (repeat x N))
      (< x 0) (/ 1 (exponent N (- x))))
    (if (number? x)
      (throw-number-exc N)
      (throw-number-exc x))))

(defn factorial
  "Given a number N, returns N! (i.e., N factorial)"
  [N]
  (if (number? N)
    (cond
      (= N 0) 1
      (>= N 1) (* N (factorial (- N 1)))
      (<= N -1) (- (* (- N) (factorial (- (- N) 1)))))
    (throw-number-exc N)))

(defn explode-num-to-digits
  "Given a nmber N, returns a list of its separate digits."
  [N]
  (if (number? N)
    ;; Maps a lambda expr which converts a char to base-10 digit
    ;; to each char of a string representation of N.
    (if (>= N 0)
      (map #(Character/digit % 10) (str N))
      (map #(Character/digit % 10) (str (- N))))
    ;; Special cases where N is passed as a string, but would still be
    ;; a valid number otherwise, including leading zeroes
    ;; valid examples: "123", "01", "007", "-123"
    (if (and
          (string? N)
          (re-matches #"[0-9]+" (clojure.string/replace-first N #"-" "")))
      (map #(Character/digit % 10) (clojure.string/replace-first N #"-" ""))
      (throw-number-exc N))))

(defn sum-of-factorials-of-digits
  "Given a number N, returns the sum of the factorials of each digit of N.
  Example: N = 35 -> 3! + 5! = 6 + 120 = 126"
  [N]
  (if (number? N)
    (reduce + (map #(factorial %) (explode-num-to-digits N)))
    (throw-number-exc N)))

(defn is-curious-number
  "A 'Curious Number' is a number where the sum of the factorial of each of its digits
  is evenly divisible by the number itself.
  For example 19 is a 'Curious Number': 1! + 9! = 1 + 362880 = 362881, and 362881 % 19 = 0."
  [N]
  (if (number? N)
    (if (= (mod (sum-of-factorials-of-digits N) N) 0)
      N
      false)
    (throw-number-exc N)))

(defn list-all-curious-numbers-between
  "Given numbers min and max, return a list of all 'Curious Numbers' from min to max inclusive."
  [min max]
  (if (and (number? min) (number? max))
    (remove nil? (map #(when (is-curious-number %) %) (range min (+ max 1))))
  (if (number? max)
    (throw-number-exc min)
    (throw-number-exc max))))

(defn sum-all-curious-numbers-up-to
  "Given a number N between 10 and 10^5, return the sum of a list of all 'Curious Numbers' 10 to N inclusive.
  This is as per constraint: 10 ≤ N ≤ 10^5 "
  [N]
  (if (number? N)
    (if (and (>= N 10) (<= N (exponent 10 5)))
      (reduce + (list-all-curious-numbers-between 10 N))
      (throw-number-exc N "Number is not 10 <= N <= 10^5: "))
    (throw-number-exc N)))

HackerRankProjectEuler34Test.clj

(ns
  ^{:author Phrancis}
  sandbox.HackerRankProjectEuler34Test
  (:require [clojure.test :as t])
  (:require sandbox.HackerRankProjectEuler34Test)
  (:use sandbox.HackerRankProjectEuler34))

(t/run-tests 'sandbox.HackerRankProjectEuler34Test) ;'

(t/deftest test-throw-number-exc
  (t/is (thrown? IllegalArgumentException (throw-number-exc)))
  (t/is (thrown? IllegalArgumentException (throw-number-exc "foo")))
  (t/is (thrown? IllegalArgumentException (throw-number-exc "bar" "this is an error message: "))))

(t/deftest test-exponent
  (t/is (thrown? IllegalArgumentException (exponent 2 "foo")))
  (t/is (thrown? IllegalArgumentException (exponent "bar" 2)))
  (t/is (= 0 (exponent 0 0)))
  (t/is (= 0 (exponent 0 2)))
  (t/is (= 1 (exponent 2 0)))
  (t/is (= 2 (exponent 2 1)))
  (t/is (= 4 (exponent 2 2)))
  (t/is (= -2 (exponent -2 1)))
  (t/is (= 4 (exponent -2 2)))
  (t/is (= -8 (exponent -2 3)))
  (t/is (= 16 (exponent -2 4)))
  (t/is (= 1/2 (exponent 2 -1)))
  (t/is (= 1/4 (exponent 2 -2)))
  (t/is (= 1/125 (exponent 5 -3))))

(t/deftest test-factorial
  (t/is (thrown? IllegalArgumentException (factorial "foo")))
  (t/is (= 1 (factorial 0)))
  (t/is (= 1 (factorial 1)))
  (t/is (= 2 (factorial 2)))
  (t/is (= 6 (factorial 3)))
  (t/is (= 24 (factorial 4)))
  (t/is (= 120 (factorial 5)))
  (t/is (= 720 (factorial 6)))
  (t/is (= 5040 (factorial 7)))
  (t/is (= 40320 (factorial 8)))
  (t/is (= 362880 (factorial 9)))
  (t/is (= -1 (factorial -1)))
  (t/is (= -2 (factorial -2)))
  (t/is (= -6 (factorial -3)))
  (t/is (= -24 (factorial -4)))
  (t/is (= -120 (factorial -5)))
  (t/is (= -720 (factorial -6)))
  (t/is (= -5040 (factorial -7)))
  (t/is (= -40320 (factorial -8)))
  (t/is (= -362880 (factorial -9))))

(t/deftest test-explode-num-to-digits
  (t/is (thrown? IllegalArgumentException (explode-num-to-digits "foo")))
  ;; standard cases:
  (t/is (= (list 0) (explode-num-to-digits 0)))
  (t/is (= (list 0) (explode-num-to-digits 0000)))
  (t/is (= (list 1 2 3) (explode-num-to-digits 123)))
  (t/is (= (list 3 2 1) (explode-num-to-digits 321)))
  (t/is (= (list 1 2 3) (explode-num-to-digits -123)))
  ;; special case strings to be considered as numbers, including 1 or more leading zeroes:
  (t/is (= (list 1 2 3) (explode-num-to-digits "123")))
  (t/is (= (list 1 2 3) (explode-num-to-digits "-123")))
  (t/is (= (list 0 1) (explode-num-to-digits "01")))
  (t/is (= (list 0 0 7) (explode-num-to-digits "007")))
  (t/is (= (list 0 0 0 0 0 0 0) (explode-num-to-digits "0000000"))))

(t/deftest test-sum-of-factorials-of-digits
  (t/is (thrown? IllegalArgumentException (sum-of-factorials-of-digits "foo")))
  (t/is (= 1 (sum-of-factorials-of-digits 0)))
  (t/is (= 24 (sum-of-factorials-of-digits 4)))
  (t/is (= 9 (sum-of-factorials-of-digits 123)))
  (t/is (= 33 (sum-of-factorials-of-digits 1234))))

;; Curious Numbers to 10^5: (19 56 71 93 145 219 758 768 7584 7684 9696 10081 21993 40585)

(t/deftest test-is-curious-number
  (t/is (thrown? IllegalArgumentException (is-curious-number "foo")))
  (t/is (false? (is-curious-number 10)))
  (t/is (= 19 (is-curious-number 19)))
  (t/is (false? (is-curious-number 20)))
  (t/is (= 56 (is-curious-number 56)))
  (t/is (false? (is-curious-number 57))))

(t/deftest test-list-all-curious-numbers-between
  (t/is (thrown? IllegalArgumentException (list-all-curious-numbers-between "foo" 100)))
  (t/is (thrown? IllegalArgumentException (list-all-curious-numbers-between 10 "bar")))
  (t/is (=
          (list 19 56 71 93 145 219 758 768 7584 7684 9696 10081 21993 40585)
          (list-all-curious-numbers-between 10 (exponent 10 5)))))

(t/deftest test-sum-all-curious-numbers-up-to
  (t/is (thrown? IllegalArgumentException (sum-all-curious-numbers-up-to "foo")))
  ;; test challenge constraint: 10 ≤ N ≤ 10^5
  (t/is (thrown? IllegalArgumentException (sum-all-curious-numbers-up-to 9)))
  (t/is (thrown? IllegalArgumentException (sum-all-curious-numbers-up-to (exponent 11 5))))
  ;; test values
  (t/is (= 19 (sum-all-curious-numbers-up-to 55)))
  (t/is (= 75 (sum-all-curious-numbers-up-to 70)))
  (t/is (= 146 (sum-all-curious-numbers-up-to 92)))
  (t/is (= 239 (sum-all-curious-numbers-up-to 144))))

Benchark tests

(defn -main
  [& args]
  ;; benchmark tests
  (print "Curious Numbers to 10^2: ") (time (list-all-curious-numbers-between 10 (exponent 10 2)))
  (print "Curious Numbers to 10^3: ") (time (list-all-curious-numbers-between 10 (exponent 10 3)))
  (print "Curious Numbers to 10^4: ") (time (list-all-curious-numbers-between 10 (exponent 10 4)))
  (print "Curious Numbers to 10^5: ") (time (list-all-curious-numbers-between 10 (exponent 10 5)))
  (print "Sum Curious Numbers up to 10^2: " ) (time (sum-all-curious-numbers-up-to (exponent 10 2)))
  (print "Sum Curious Numbers up to 10^3: " ) (time (sum-all-curious-numbers-up-to (exponent 10 3)))
  (print "Sum Curious Numbers up to 10^4: " ) (time (sum-all-curious-numbers-up-to (exponent 10 4)))
  (print "Sum Curious Numbers up to 10^5: " ) (time (sum-all-curious-numbers-up-to (exponent 10 5))))

Results

There seems to be a big time increase (comparatively) going from \$10^4\$ to \$10^5\$, I realize it is a whole order of magnitude higher but the increase in computation time seems to not be proportional to the other increases in one order of magnitude.

Curious Numbers to 10^2: "Elapsed time: 0.481473 msecs"
Curious Numbers to 10^3: "Elapsed time: 0.055067 msecs"
Curious Numbers to 10^4: "Elapsed time: 0.05914 msecs"
Curious Numbers to 10^5: "Elapsed time: 1.444254 msecs"
Sum Curious Numbers up to 10^2: "Elapsed time: 40.795465 msecs"
Sum Curious Numbers up to 10^3: "Elapsed time: 141.380443 msecs"
Sum Curious Numbers up to 10^4: "Elapsed time: 859.525103 msecs"
Sum Curious Numbers up to 10^5: "Elapsed time: 5655.463085 msecs"
\$\endgroup\$
4
\$\begingroup\$

I don't really know Clojure, but I enjoyed reading this code. It's especially great that you've included unit tests. I have a few nitpicks though.


According to your tests, the exponent of 0 is 0:

  (t/is (= 0 (exponent 0 0)))

But by math, \$0^0\$ should be 1.


Somewhat similarly, factorial is usually not defined for negative numbers, but you define \$(-n)!\$ as \$-(n!)\$. Not a big deal though.


Something else that I find strange is that is-curious-number returns two kinds of types, boolean or numeric:

  (t/is (false? (is-curious-number 10)))
  (t/is (= 19 (is-curious-number 19)))

I'm wondering if this is common practice in Clojure for some reason, because normally it's not a great idea. It would seem to make sense to return boolean, as the function name implies.


  1. Specifically with explode-num-to-digits (and consequently test-explode-num-to-digits) is that function trying to handle too many edge cases? I thought it would be "neat" to be able to accept numbers as strings and parse those the same as a regular number, but does it even make sense for this function to handle such arguments?

I think it's a common trap when programmers try to do something "neat", that they don't really need, and then get into trouble for it. The challenge states that the input is a number \$N\$. It won't make much sense passing anything else, it only adds the tedious overhead of numeric validation. It's not necessary to support string inputs, so don't.

Of course, when reading from STDIN, you do need to convert strings to numbers at some point, but you should do that only once, as close to the point of input as possible, and let the inner layers of your solution safely assume that they will receive valid numeric values.

For example there's no need for exponent to handle non-numeric arguments. It's used at lower levels of your solution, and should be able to expect to be protected by the higher levels already.

  1. Is it idiomatic FP to throw exceptions, such as IllegalArgumentException which I often do here, or would it make more sense to return a falsey value when functions are passed an argument they are not designed to handle?

By my answer to your second question, this question simply vanishes (as far as this Project Euler example is concerned). In addition, input validation is generally redundant in online challenges. In real life applications the code needs to be robust and vigilant when handling any kind of untrusted input, but this is generally not the case in online challenges.

\$\endgroup\$
  • \$\begingroup\$ On the latter, I think you have a point; now that you mention it, usually is-foo? predicate functions return true or false, while is-foo (no ?) predicates either return a value (truthy) or nil (falsey). \$\endgroup\$ – Phrancis Mar 12 '16 at 17:34
  • \$\begingroup\$ Oh and thanks for pointing out the math errors/overlooks, I don't math very good yet :) \$\endgroup\$ – Phrancis Mar 12 '16 at 17:38
  • 1
    \$\begingroup\$ I added some more, actually addressing one of your main questions (and conveniently side-stepping the other) \$\endgroup\$ – janos Mar 12 '16 at 17:59
  • \$\begingroup\$ About 0^0 = 1, is that actually the case? I've seen/heard many arguments on whether it is actually 1 or 0. \$\endgroup\$ – SirPython Mar 13 '16 at 2:16
  • \$\begingroup\$ @SirPython I'm not aware of such dispute. The rule is simple: \$x^0\$ is always 1, whatever the value of x \$\endgroup\$ – janos Mar 13 '16 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.