Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
428 PurelyFunctional.tv Newsletter

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/

@KingCode
Copy link

KingCode commented May 24, 2021

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])))

@alex-gerdom
Copy link

alex-gerdom commented May 24, 2021

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

@miner
Copy link

miner commented May 24, 2021

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

@miner
Copy link

miner commented May 24, 2021

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

@steffan-westcott
Copy link

steffan-westcott commented May 24, 2021

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

@Folcon
Copy link

Folcon commented May 24, 2021

(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
=)...

@diavoletto76
Copy link

diavoletto76 commented May 24, 2021

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

@vpetruchok
Copy link

vpetruchok commented May 25, 2021

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

@mchampine
Copy link

mchampine commented May 25, 2021

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

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

@jaihindhreddy
Copy link

jaihindhreddy commented May 26, 2021

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

@miner
Copy link

miner commented May 28, 2021

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

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