Instantly share code, notes, and snippets.

# ericnormand/00 Formatted prime factorization.md

Last active May 28, 2021 19:11
Show Gist options
• Save ericnormand/2d21bd06c44b37cd7ac34137ef46b249 to your computer and use it in GitHub Desktop.

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.

### KingCode commented May 24, 2021 • edited

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 commented May 24, 2021 • edited

```(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 commented May 24, 2021

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

### 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 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 commented May 24, 2021 • edited

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