428 PurelyFunctional.tv Newsletter

00 Formatted prime factorization.md

Formatted prime factorization

Prime factorization means representing an integer as a product of primes. A function that factorizes a number will return a vector of primes, like so: [2 2 3 5]. Your job is to take such a vector and create a nice string that shows the mathematical notation of the product.

Examples

(format-product [2 2 3 5]) ;=> "2^2 x 3 x 5"
(format-product [2 3 3 3 11 11]) ;=> "2 x 3^2 x 11^2"
(format-product [7]) ;=> "7"

Use x to indicate multiplication and ^ to indicate exponentiation.

Thanks to this site for the problem idea, where it is rated Hard in Ruby. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

Some implementations using both high and low-level. The first three offload the formatting logic to append, but the last one uses destructuring and iterate instead:

;; plumbing
(defn append [acc [p e]]
  (str acc 
       (or (and (seq acc) " x ") "")
       p
       (or (and (< 1 e) (str "^" e)) "")))

(defn format-product [primes]
  (->> primes frequencies sort
       (reduce append "")))

(defn format-product-2 [primes]
  (->> primes (partition-by identity)
       (reduce (fn [expr [p & _ :as repeated]]
                 (append expr [p (count repeated)]))
               "")))

;; Recursive, low level
(defn format-product-3 [primes]
  (let [fmt (fn [expr [p e :as pe] [p' & ps]]
              (cond 
                (not p')
                (append expr pe)
                (= p p')
                (recur expr [p (inc e)] ps)
                :else
                (recur (append expr pe) [p' 1] ps)))]
    (fmt "" [(first primes) 1] (rest primes))))

;; Low level, avoids formatting logic 
(defn format-product-4 [primes]
  (let [[part & parts] (->> primes (partition-by identity))
        ->factor-exp (fn [[x & xs :as repeated]]
                       (->> [x "" nil]
                            (iterate (fn [[base _ e]]
                                       [base "^" (inc (or e 1))]))
                            (#(nth % (dec (count repeated))))
                            (apply str)))]
    (->> parts
         (reduce (fn [expr part]
                   (str expr " x "(->factor-exp part)))
                 (->factor-exp part)))))

(let [feature-1 [2] feature-2 [2 3 3 5] feature-3 [2 3 3 3 11 11]
      sol-1 "2" sol-2 "2 x 3^2 x 5" sol-3 "2 x 3^3 x 11^2"]
  (assert (every? 
           #(every? identity
                    (map (fn [ftr sol] (= sol (% ftr)))
                         [feature-1 feature-2 feature-3]
                         [sol-1 sol-2 sol-3]))
           [format-product
            format-product-2
            format-product-3
            format-product-4])))

(defn format-product [xs]
  (let [format-factor (fn [xs]
                        (if (= 1 (count xs))
                          (str (first xs))
                          (str (first xs) "^" (count xs))))]
    (->> xs sort
         (partition-by identity)
         (map format-factor)
         (clojure.string/join " x "))))

Example correction: (format-product [2 3 3 3 11 11]) ;=> "2 x 3^3 x 11^2" -- three threes

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

(defn format-product [factors]
  (->> factors
       frequencies
       sort
       (map (fn [[f n]] (if (= n 1) f (str f "^" n))))
       (str/join " x ")))

(defn format-product [primes]
  (->> primes
       frequencies
       sort
       (map (fn [[n pow]] (apply str n (when (< 1 pow) ["^" pow]))))
       (clojure.string/join " x ")))

(require '[clojure.string :as str])
(defn format-product [xs]
  (->> xs
    (frequencies)
    (into (sorted-map))
    (reduce-kv
      (fn [vx k v]
        (conj vx (if (> v 1) (str k "^" v) k)))
      [])
    (str/join " x ")))

I'm assuming there was a bug in the question as:
2 x 3 x 3 x 3 x 11 x 11 = 6,534
2 x 3^2 x 11^2 = 2,178
2 x 3^3 x 11^2 = 6,534
=)...

(defn format-product [xs]
  (->> xs
       (frequencies)
       (into (sorted-map))
       (seq)
       (map (fn [[k v]] (if (= 1 v) (str k) (format "%s^%s" k v))))
       (clojure.string/join " x ")))

(defn format-product [xs]
  (->> (frequencies xs)
       (sort-by first)
       (reduce (fn [res [n cnt]]
                 (str
                  res
                  (if (empty? res) "" " x ")
                  (if (= cnt 1) n (str n "^" cnt))))
               "")))

(defn ffact [[fk fv]] (if (= fv 1) (str fk) (str fk "^" fv)))

(defn format-product [pf]
  (apply str (interpose " x " (map ffact (frequencies pf)))))

(defn format-product [nums]
  (->> (into (sorted-map) (frequencies nums))
       (map (fn [[x n]] (if (= n 1) x (str x \^ n))))
       (clojure.string/join " x ")))

The into call can be skipped if we don't care about order.

(defn string-builder
  ([] (StringBuilder.))
  ([sb] (str sb))
  ([sb x] (.append ^StringBuilder sb (str x))))

(defn format-product [factors]
  (transduce (comp (map (fn [[f cnt]] (if (= cnt 1) f (str f "^" cnt))))
                   (interpose " x "))
             string-builder
             (sort (frequencies factors))))