6
\$\begingroup\$

I solved Project Euler 4 using Clojure Lisp.

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

I'm not very experienced with Clojure yet. I tried to break the logic down into small, easy to understand functions. I added documentation and input type assertions to each function.

How can I improve this code? Is :pre a good method for asserting correct input types, or is there a better way of doing that?

(defn palindrome? [arg]
  "Returns true if arg is a palindrome, i.e., it reads the same both ways"
  (= (seq (str arg))
     (reverse (str arg))))

(defn pow [N X]
  "Returns N to the power of X"
  {:pre [(number? N) (number? X)]}
  (reduce * (repeat X N)))

(defn nums-with-n-digits [digits]
  "Return list of all numbers comprised of a certain number of digits"
  {:pre (number? digits)}
  (let [max (pow 10 digits)
        min (/ max 10)]
    (range min max)))

(defn products-of-nums-list [nums]
  "Returns a descending order list of distinct products of each of the numbers in nums"
  {:pre (list? nums)}
  (sort > (distinct (for [x nums y nums] (* x y)))))

(defn solve-pe4 [digits]
  "Returns list of solutions of largest palindrome products of all numbers with a certain number of digits"
  {:pre (number? digits)}
  (first (filter palindrome? (products-of-nums-list (nums-with-n-digits digits)))))

(defn -main []
  (println (solve-pe4 2)) ; 9009
  (println (solve-pe4 3))); correct answer
\$\endgroup\$
5
\$\begingroup\$

A function's docstring must go before its argument vector. You've written your docstrings after your argument vectors, which prevents your :preconditions from being recognized and doesn't work when you try to retrieve the docstring with tools like doc:

(doc palindrome?)
;; -------------------------
;; user/palindrome?
;; ([arg])
;;   nil

Rather than explicitly calling seq in your palindrome? function, you could use clojure.string/reverse and then just compare the two strings. Also, in Clojure code, if when you have something that could be anything, or something that could be any number, it's conventional to name it x:

(require '[clojure.string :as str])

(defn palindrome?
  "Returns true iff x reads the same both ways in base ten."
  [x]
  (let [s (str x)]
    (= s (str/reverse s))))

In most cases, it's conventional to use lowercase instead of uppercase for names. Following from the rule of x above, if you have two things, each of which could be any number, it's conventional to name the second one y:

(defn pow
  "Returns x to the power of y."
  [x y]
  (reduce * (repeat y x)))

It's essential that the collection of :preconditions you give in a defn be a collection of preconditions (such as the vector you have in your pow function), rather than just a single precondition (such as in your other three functions with preconditions). This is because, due to Clojure's homoiconicity, (number? digits) is, in fact, a collection (a list, to be precise) containing two elements: number? and digits. In this case, you can use {:pre [(number? digits)]} instead.

Your local max and min bindings shadow the existing max and min functions in clojure.core, which is generally a bad idea because it can lead to confusion and forces you to use namespace-qualified names for those functions if you want to use them. Also, since you already use the name n in your function name (nums-with-n-digits), using n as your parameter name would allow you to simplify your function's docstring and body without sacrificing clarity:

(defn nums-with-n-digits
  "Return a lazy sequence of all positive integers with n digits."
  [n]
  (let [end (pow 10 n)
        start (/ end 10)]
    (range start end)))

If you move the docstring for products-of-nums-list and replace the condition map with {:pre [(list? nums)]}, you'll see that calls like (products-of-nums-list (nums-with-n-digits 2)) will fail. This is because range (and therefore nums-with-n-digits) doesn't return a list; it returns a sequence. All lists are sequences, but not all sequences are lists. While (range Long/MAX_VALUE) returns instantly and uses negligible memory, (apply list (range Long/MAX_VALUE)) will use all your computer's memory before it returns.

Your products-of-nums-list function is pretty scary, actually. Your use of distinct and sort causes first a set and then an array containing all of the distinct elements in nums to be held in memory. Try evaluating (products-of-nums-list (nums-with-n-digits 4)) while watching your CPU and memory usage.

Rather than delegating the task of sorting (which is overkill anyway) to a products-of-nums-list function that isn't particularly general anyway, it would be better to just put the for directly into solve-pe4 and use max instead of sort to get the final result:

(defn solve-pe4
  "Returns the largest palindrome made from the product of two n-digit numbers."
  [n]
  (->> (let [nums (nums-with-n-digits n)]
         (for [x nums
               y nums]
           (* x y)))
       (filter palindrome?)
       (apply max)))

This function is already quite readable, so I don't see a need to decompose it further. It significantly improves the performance of (solve-pe4 3) and, given enough time, can find solutions to larger problems:

(solve-pe4 4)
;;=> 99000099

Your :preconditions are an OK way to assert correct input types. Clojure 1.9 will bring the spec library, which is a far more powerful way to solve that problem (and others):

(require '[clojure.spec :as s])

(s/fdef pow
  :args (s/cat :x number? :y nat-int?)
  :ret number?)

(s/fdef nums-with-n-digits
  :args (s/cat :n pos-int?)
  :ret (s/coll-of pos-int?))

(s/fdef solve-pe4
  :args (s/cat :n pos-int?)
  :ret pos-int?)

You can use instrument to enable spec validation:

(require '[clojure.spec.test :as stest])

(stest/instrument)

(nums-with-n-digits 0)
;; clojure.lang.ExceptionInfo: Call to #'user/nums-with-n-digits did not conform to spec:
;;                             In: [0] val: 0 fails at: [:args :n] predicate: pos-int?
;;                             :clojure.spec/args  (0)
;;                             :clojure.spec/failure  :instrument
\$\endgroup\$
  • \$\begingroup\$ Wow that's a great answer, thanks for all the improvements! \$\endgroup\$ – Phrancis Aug 18 '16 at 15:38
  • \$\begingroup\$ There is one slightly unexpected behavior (to me) on your version of palindrome? function, in that it returns true for (palindrome? nil) is that intentional? \$\endgroup\$ – Phrancis Aug 18 '16 at 16:41
  • \$\begingroup\$ @Phrancis I only really intended for palindrome? to work on nonnegative integers. Looking at it again, though, I think that having palindrome? accept integers is needlessly complex; it would be better to have it just work with strings: (s/fdef palindrome? :args (s/cat :s string?) :ret boolean?) This would remove the let in its definition: (defn palindrome? [s] (= s (str/reverse s))) Then, in solve-pe4, you can simply replace palindrome? with (comp palindrome? str). \$\endgroup\$ – Sam Estep Aug 18 '16 at 17:53
  • \$\begingroup\$ I made a change and added (cond (s/blank? s) false :else ... which makes it work great for non-negative ints and strings and eliminates empty/nil from returning true \$\endgroup\$ – Phrancis Aug 18 '16 at 18:16
  • \$\begingroup\$ @Phrancis Personally, I would say that "" is a palindrome because it reads the same both ways, but it's up to you. \$\endgroup\$ – Sam Estep Aug 18 '16 at 18:33

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.