clojure refactor code from recursion

Question

I have the following bit of code that produces the correct results:

(ns scratch.core
  (require [clojure.string :as str :only (split-lines join split)]))

(defn numberify [str]
  (vec (map read-string (str/split str #" "))))

(defn process [acc sticks]
  (let [smallest (apply min sticks)
        cuts (filter #(> % 0) (map #(- % smallest) sticks))]

    (if (empty? cuts)
      acc
      (process (conj acc (count cuts)) cuts))))

(defn print-result [[x & xs]]
  (prn x)
  (if (seq xs)
    (recur xs)))

(let [input "8\n1 2 3 4 3 3 2 1"
      lines (str/split-lines input)
      length (read-string (first lines))
      inputs (first (rest lines))]
  (print-result (process [length] (numberify inputs))))

The process function above recursively calls itself until the sequence sticks is empty?.

I am curious to know if I could have used something like take-while or some other technique to make the code more succinct?

If ever I need to do some work on a sequence until it is empty then I use recursion but I can't help thinking there is a better way.

Leon Grapenthin · Accepted Answer · 2015-06-15 20:12:32Z

2

Your core problem can be described as

stop if count of sticks is zero
accumulate count of sticks
subtract the smallest stick from each of sticks
filter positive sticks
go back to 1.

Identify the smallest sub-problem as steps 3 and 4 and put a box around it

(defn cuts [sticks]
  (let [smallest (apply min sticks)]
    (filter pos? (map #(- % smallest) sticks))))

Notice that sticks don't change between steps 5 and 3, that cuts is a fn sticks->sticks, so use iterate to put a box around that:

(defn process [sticks]
  (->> (iterate cuts sticks)
;; ----- 8< -------------------

This gives an infinite seq of sticks, (cuts sticks), (cuts (cuts sticks)) and so on

Incorporate step 1 and 2

(defn process [sticks]
  (->> (iterate cuts sticks)
       (map count)         ;; count each sticks
       (take-while pos?))) ;; accumulate while counts are positive

(process [1 2 3 4 3 3 2 1])
;-> (8 6 4 1)

Behind the scene this algorithm hardly differs from the one you posted, since lazy seqs are a delayed implementation of recursion. It is more idiomatic though, more modular, uses take-while for cancellation which adds to its expressiveness. Also it doesn't require one to pass the initial count and does the right thing if sticks is empty. I hope it is what you were looking for.

edited Jun 15, 2015 at 20:12

answered Jun 15, 2015 at 19:58

Leon Grapenthin

9,29626 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mark Fisher Over a year ago

nice. must remember iterate, this is much nicer than my reduce.

dagda1 Over a year ago

exactly what I was looking for. I have learned something today.

Mark Fisher · Accepted Answer · 2015-06-16 09:57:42Z

I think the way your code is written is a very lispy way of doing it. Certainly there are many many examples in The Little Schema that follow this format of reduction/recursion.

To replace recursion, I usually look for a solution that involves using higher order functions, in this case reduce. It replaces the min calls each iteration with a single sort at the start.

(defn process [sticks]
  (drop-last (reduce (fn [a i]
                       (let [n (- (last a) (count i))]
                         (conj a n)))
                     [(count sticks)]
                     (partition-by identity (sort sticks)))))

(process [1 2 3 4 3 3 2 1])
=> (8 6 4 1)

I've changed the algorithm to fit reduce by grouping the same numbers after sorting, and then counting each group and reducing the count size.

Collectives™ on Stack Overflow

clojure refactor code from recursion

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related