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 clojure. 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:
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?Specifically with
explode-num-to-digits
(and consequentlytest-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"