Skip to content

Instantly share code, notes, and snippets.

Created August 23, 2021 12:00
Show Gist options
  • Save ericnormand/435e5e03c4160e92366fbc9e70b7cb9b to your computer and use it in GitHub Desktop.
Save ericnormand/435e5e03c4160e92366fbc9e70b7cb9b to your computer and use it in GitHub Desktop.
440 Newsletter

Dealing elements

There's a function in clojure.core called partition-all. It creates subsequences of a given maximum size.

(partition-all 3 [1 2 3 4 5 6 7 8]);=> [[1 2 3] [4 5 6] [7 8]]

Notice that the first sequence gets the first three elements, the second sequence gets the second three elements, etc. We could get the original sequence again by concatenating the sequences back together.

Your task is to write a function that deals out the cards more evenly. That is, the first element goes into the first sequence, the second element goes into the second sequence, etc. We're going to write two versions of this function.

Version one takes the maximum size of the subsequence. That means the number of subsequences will depend on the size of the given sequence.

;; at most 3 elements in each subsequence
(deal-max 3 [1 2 3 4 5 6 7 8]) ;=> [[1 4 7] [2 5 8] [3 6]]

Note that we can put these sequences back together with interleave (except for the behavior when you have a short sequence).

Version two takes the number of subsequences. It is variable in the size of the subsequence.

;; deal out 4 subsequences
(deal-out 4 [1 2 3 4 5 6 7 8]) ;=> [[1 5] [2 6] [3 7] [4 8]]

Note that this also can be put back together with interleave.

Write deal-max and deal-out. How do the implementations compare? Which is easier to write?

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

Please submit your solutions as comments on this gist.

To subscribe:

Copy link

kolstae commented Aug 23, 2021

(defn deal-out [n xs]
    (fn [vs ps] (concat (map conj vs ps) (drop (count ps) vs)))
    (repeat n [])
    (partition-all n xs)))

(defn deal-max [n xs]
  (deal-out (quot (+ (count xs) (dec n)) n) xs))

Copy link

(defn deal-out [n xs]
  (map #(take-nth n (drop % xs)) (range (min n (count xs)))))

(defn deal-max [n xs]
  (deal-out (quot (+ (count xs) n -1) n) xs))

Copy link

werand commented Aug 23, 2021

(defn deal-out [n s]
  (loop [i 0 s s acc []]
    (if (seq s)
      (recur (mod (inc i) n)
             (rest s)
             (assoc acc i (conj (nth acc i []) (first s))))

(defn deal-max [n s]
  (let [m (int (Math/ceil (/ (count s) n)))]
    (deal-out m s)))

Copy link

jonasseglare commented Aug 23, 2021

(defn deal-out [n cards]
  (->> cards
       (iterate rest)
       (take n)
       (map #(take-nth n %))))

(defn deal-max [n cards]
  (-> cards
      (+ n -1)
      (quot n)
      (deal-out cards)))

Copy link

KubqoA commented Aug 24, 2021

(defn deal-out [parititons-count coll]
  (->> (range parititons-count)
       (mapv #(vec (take-nth parititons-count (drop % coll))))))

(defn deal-max [n coll]
 (deal-out (Math/ceil (/ (count coll) n)) coll))

Copy link

(defn fill-in [s e]
  (let [min-size (reduce min (map count s))]
      (reduce (fn [{:keys [applied] :as acc} s1]
                (if (and (not applied) (= min-size (count s1)))
                  (-> acc
                      (update :result conj (conj s1 e))
                      (assoc :applied true))
                  (update acc :result conj s1)))
              {:result [] :applied false} s)

(defn deal-max [n s]
  (reduce fill-in (take n (repeat [])) s))

(defn deal-out [n s]
   (map (fn [i v] [i v]) (range (count s)) s) ; create pairs [index value]
   (group-by (fn [[i]] (mod i n)))
   (mapv (fn [s1] (mapv second s1)))))        ; remove index from pairs [index value]

Copy link

miner commented Aug 25, 2021

(defn deal-out [n coll]
  (for [cs (take n (iterate rest coll))]
    (take-nth n cs)))

(defn ceil [^long n ^long d]
  (if (zero? (rem n d))
    (quot n d)
    (inc (quot n d))))

(defn deal-max [mx coll]
  (deal-out (ceil (count coll) mx) coll))

Copy link

bnii commented Sep 2, 2021

(defn deal-out [partition-num ns]
  (let [indexed (map-indexed (fn [i v] [(mod i partition-num) v]) ns)
        grouped (group-by (fn [[i _]] i) indexed)]
      (fn [p] (map (fn [[_ v]] v) p))
      (vals grouped))))

(defn deal-max [partition-size ns]
  (let [partition-num (mod
                        (inc (count ns)))]
    (deal-out partition-num ns)))

Copy link

KingCode commented Oct 1, 2021

(defn ->composite-index [i div]
  [(rem i div), (quot i div)])

(defn deal [n coll init-f]
  (->> coll
       (reduce (fn [[parts rank] x]
                 [(assoc-in parts
                            (->composite-index rank n)
                  (inc rank)])
               [(init-f n coll) 0])

(defn init-from-maxsize [maxsiz coll]
  (-> coll count (/ maxsiz) Math/ceil int
      (repeat [])

(defn init-from-numparts [numparts coll]
  (-> numparts (repeat []) vec))

(defn deal-max [n coll]
  (deal n coll init-from-maxsize))

(defn deal-out [n coll]
  (deal n coll init-from-numparts))

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