Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

Factors to string

Any integer can be written as a product of prime numbers. This is called the number's prime factorization. For instance, 24's prime factorization is 24 = 2 x 2 x 2 x 3 or even better 24 = 2 ^ 3 x 3. For this exercise, we are given the prime factorization. We have to construct the string representation.

Examples:

(factors->string [2 2 2 3]) ;=> "24 = 2^3 x 3"
(factors->string [7]) ;=> "7 = 7"
(factors->string [2 2 7]) ;=> "28 = 2^2 x 7"

Just for clarity, here are the rules:

  • If the prime factor appears only once, just use the number by itself (i.e., "2")
  • If the prime factor appears more than once, use the exponent notation (i.e., "2^3")
  • If there is more than one prime factor, separate them with an "x" for multiplication (i.e., "3 x 7")
  • Start the string with "n =" where n is the number that has been factorized. You can calculate this by multiplying all the factors together.

Thanks to this site for the challenge idea where it is considered Hard level in Ruby.

Email submissions to eric@purelyfunctional.tv before August 29, 2020. You can discuss the submissions in the comments below.

(defn factors->string [factors]
(let [number (reduce * 1 factors)
groups (partition-by identity factors)
exprs (map (fn [[n :as group]]
(let [exp (count group)]
(if (= 1 exp)
n
(str n "^" exp))))
groups)]
(str number " = " (clojure.string/join " x " exprs))))
(defn factors->string
[coll]
(when (seq coll)
(str (reduce * coll) " = " (clojure.string/join " x "
(for [[k v] (frequencies coll)]
(if (> v 1) (str k "^" v) k))))))
(factors->string [2 2 2 3])
;; => "24 = 2^3 x 3"
(factors->string [7])
;; => "7 = 7"
(factors->string [2 2 7])
;; => "28 = 2^2 x 7"
(factors->string [])
;; => nil
(require '[net.cgrand.xforms :as x])
(defn- factor->str [[b :as coll]]
(let [e (count coll)]
(if (= e 1)
(str b)
(str b \^ e))))
(defn- lhs [factors]
(reduce * factors))
(defn- rhs [factors]
(let [xf (comp (partition-by identity)
(map factor->str)
(interpose " x "))]
(x/str xf factors)))
(defn factors->string [factors]
(if (empty? factors) ""
(str (lhs factors) " = " (rhs factors))))
(deftest factors->string-test
(are [out in] (= out in)
"" (factors->string [])
"" (factors->string [])
"7 = 7" (factors->string [7])
"28 = 2^2 x 7" (factors->string [2 2 7])
"24 = 2^3 x 3" (factors->string [2 2 2 3])))
(defn factors->strings
"Given a number's prime factors returns a string representation of the number and it's factorization such as:
[2 2 2 3] => \"24 = 2^3 * 3\"."
[prime-factors]
(let [n (apply * prime-factors)
factors-string (->> (frequencies prime-factors)
;; using sorted map to make sure we start with the lowest factor
(into (sorted-map))
(map (fn [[factor freq]]
(str factor (when (> freq 1) (str "^" freq)))))
(string/join " x "))]
(format "%d = %s" n factors-string)))
(defn factors->string
[factors]
(let [product (reduce * 1 factors)]
(->> factors
(partition-by identity)
(map
(fn [[factor :as repeats]]
(let [n (count repeats)]
(if (= n 1)
factor
(str factor "^" n)))))
(str/join " x ")
(str product " = "))))
(factors->string [2 2 2 3]) ;=> "24 = 2^3 x 3"
(factors->string [7]) ;=> "7 = 7"
(factors->string [2 2 7]) ;=> "28 = 2^2 x 7"
(defn factors->string [s]
(letfn [(rtp [c] (if (= (count c) 1) (str (first c))
(apply str ((juxt first (constantly "^") count) c))))]
(str (apply * s) " = " (str/join " X " (map rtp (partition-by identity s))))))
(ns pftv.factors-to-string
(:require [clojure.pprint :as pprint]))
(defn factors->string
[pfs]
(let [n (apply * pfs)
base-exponent-pairs (seq (frequencies pfs))]
(pprint/cl-format nil "~d = ~{~{~d~[~;~:;~:*^~d~]~}~^ x ~}" n base-exponent-pairs)))
(comment
;; Progressively developing with cl-format
(pprint/cl-format nil "~d = ~{~d~^ x ~}" 24 [2 2 2 3])
(map #(pprint/cl-format nil "~{~d~[~;~:;~:*^~d~]~}" [2 %]) (range 1 4)))
(comment
(= "24 = 2^3 x 3" (factors->string [2 2 2 3]))
(= "7 = 7" (factors->string [7]))
(= "28 = 2^2 x 7" (factors->string [2 2 7])))
(defn factors->string [factors]
(->> (frequencies factors)
(map (fn [[n exp]]
(if (= 1 exp) (str n) (str n "^" exp))))
(interpose " x ")
(cons (str (apply * factors) " = "))
(apply str)))
(defn factors->string [factors]
(let [freqs (into (sorted-map) (frequencies factors))
term (fn [[x power]] (apply str (if (= 1 power) [x] [x "^" power])))
terms (clojure.string/join " x " (map term freqs))]
(str (reduce * factors) " = " terms)))
(defn- count-elements [xs]
(reduce #(assoc % %2 (inc (get %1 %2 0))) {} xs))
(defn- format-prime [[prime count]]
(if (= count 1) (str prime) (str prime "^" count)))
(defn factors->string [primes]
(let [i (reduce * primes)
formatted (->> primes
count-elements
(map format-prime)
(interpose " x ")
(apply str))]
(str i " = " formatted)))
@ninjure
Copy link

ninjure commented Aug 10, 2020

(defn factors->string [factors]
  (letfn [(prn-pow [[num pow]] (str num (when-not (= pow 1) (str \^ pow))))]
    (when (seq factors)
      (apply str (reduce * factors) " = "
             (->> factors frequencies sort (map prn-pow) (interpose " x "))))))

@jeroenvanwijgerden
Copy link

jeroenvanwijgerden commented Aug 11, 2020

(defn factors->string
  [factors]
  (let [factorized (reduce * factors)
        factor+frequency (frequencies factors)
        ->str (fn [[factor frequency]]
                (if (= 1 frequency)
                  (str factor)
                  (str factor \^ frequency)))
        factors-as-str (apply str (->> factor+frequency
                                       (sort-by first)
                                       (map ->str)
                                       (interpose " x ")))]
    (str factorized " = " factors-as-str)))


(assert (= "2 = 2"
           (factors->string [2])))

(assert (= "4 = 2^2"
           (factors->string [2 2])))

(assert (= "6 = 2 x 3"
           (factors->string [2 3])))

(assert (= "6 = 2 x 3"
           (factors->string [3 2])))

(assert (= "24000 = 2^2 x 3 x 4^2 x 5^3"
           (factors->string [5 2 3 2 5 4 4 5])))

Some thoughts:

In this case I like to bind (frequencies factors) to the name factor+frequency. (frequencies factors) has multiple meanings: a function of factor to frequency and also a collection of [factor frequency] tuples. In this case only the collection of tuple aspect is relevant, which I signal with the name factor+frequency. I allow the reader to forget about the function aspect of (frequencies factors), freeing up his mind. In the same sense, the reader can choose to keep his mind as empty as possible by not even reading the right hand side of the let binding at all. Small optimisations perhaps not worth the overhead (although the more I look at it, the more I like it), but definitely nice to contemplate as an exercise.

Lately I've been playing around some with Uncle Bob's (Robert Martin's) rule of thumb to keep the implementation of a function exactly one level of abstraction lower than the name of that function. If something is not exactly one level lower, it should ("should"; rule of thumb) be extracted into a function that is one level lower. The goal of this is to make the function 'polite'; the function provides only minimal information needed to understand what this function is doing. If the reader wants to know more, he can look up the implementations of the functions called as part of the implementation of this function.

From what I've seen, Martin talks only about extracting to a function. An additional benefit of extraction to a named function is that that named function can now be tested. (However, as Martin also points out, not all functions need to be explicitly tested: if the function results from a refactoring step, then it will already be tested, provided the pre-refactor code was tested.) The cost of extracting to named functions is extra overhead (more defn forms) and a worse overview (related code becomes less spatially local). I find instead extracting functions and calculations to let binding a nice way to obtain the benefits of 'politeness' while maintaining overview (locality) at a small cost of extra code. Instead of naming a function, I can just name the data resulting from a function call or thread.

In that sense, you could see the form (str factorized " = " factors-as-str) as the true body of the function, with the let binding providing the 'politeness' menu in case the reader wants more detail. That made me think: the bindings are not so polite, because factor+frequency and ->str are not directly related to the 'true body' of the function! This inspired me to do something I have never done before: put a let binding inside a let binding:

(defn factors->string
  [factors]
  (let [factorized (reduce * factors)
        factors-as-str (let [factor+frequency (frequencies factors)
                             ->str (fn [[factor frequency]]
                                     (if (= 1 frequency)
                                       (str factor)
                                       (str factor \^ frequency)))]
                         (apply str (->> factor+frequency
                                         (sort-by first)
                                         (map ->str)
                                         (interpose " x "))))]
    (str factorized " = " factors-as-str)))

Now there is a 'polite' layering. To understand the final (str ... form, the reader can look up factorized and factors-as-str in the top level let binding. To try and understand factors-as-str, the reader can read

(apply str (->> factor+frequency
                (sort-by first)
                (map ->str)
                (interpose " x ")))

If that is not sufficient still, the reader can look at the bindings of the inner let. Perhaps much overdone, but interesting to contemplate as an exercise.

@camsaul
Copy link

camsaul commented Aug 11, 2020

(ns factors
  (:require [clojure
             [string :as str]
             [test :refer :all]]))

(defn factors->string [factors]
  (format "%d = %s"
          (reduce * factors)
          (str/join " x "
                    (for [[n :as group] (partition-by identity (sort factors))]
                      (if (= (count group) 1)
                        n
                        (format "%d^%d" n (count group)))))))

(deftest factors->string-test
  (is (= "24 = 2^3 x 3"
         (factors->string [2 2 2 3])
         (factors->string [2 2 3 2])))
  (is (= "7 = 7"
         (factors->string [7])))
  (is (= "28 = 2^2 x 7"
         (factors->string [2 2 7]))))

@KingCode
Copy link

KingCode commented Dec 12, 2020

(defn factors->string [factors]
  (transduce 
   (comp (partition-by identity)
         (map (fn [xs]
                [(apply * xs), (first xs), (count xs)]))),

   (completing (fn [[acc, fact-strs] [factor, base, exp]]
                 [(* acc factor), 
                  (conj fact-strs 
                        (str base (if (= 1 exp) 
                                    "" 
                                    (str "^" exp))))]) 
               (fn [[product fact-strs]]
                 (str product " = " (clojure.string/join " x " fact-strs)))),

   [1 []],
   factors))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment