Instantly share code, notes, and snippets.

# ericnormand/00 factors to string.md

Last active December 12, 2020 23:26
Star You must be signed in to star a gist

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"
(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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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" (factors->string [2 2 7]) ;; => "28 = 2^2 x 7" (factors->string []) ;; => nil
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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 ) "28 = 2^2 x 7" (factors->string [2 2 7]) "24 = 2^3 x 3" (factors->string [2 2 2 3])))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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" (factors->string [2 2 7]) ;=> "28 = 2^2 x 7"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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))))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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 )) (= "28 = 2^2 x 7" (factors->string [2 2 7])))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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 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 commented Aug 11, 2020 • edited

```(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 )))

(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 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 )))
(is (= "28 = 2^2 x 7"
(factors->string [2 2 7]))))```

### KingCode commented Dec 12, 2020 • edited

```(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))```