466 Eric Normand Newsletter

00 custom sort order.md

Custom sort order

The sort function sorts a collection based on its "natural ordering." sort-by allows you to sort a collection based on the natural ordering of the result of some function applied to the elements. Your task is to write a function sort-with which takes a sequence of elements that define the sort order.

Example

           ; define ordering               ; collection to sort
(sort-with [:breakfast :lunch :dinner]     #{:lunch :breakfast :dinner}) ;=> (:breakfast :lunch :dinner)
(sort-with [2 3 4 :jack :queen :king :ace] [4 2 4 :king 2]) ;=> [2 2 4 4 :king]

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

Please submit your solutions as comments on this gist.

To subscribe: https://ericnormand.me/newsletter

Here is my solution with mapped indices (Clojure beginner):

(defn sort-with [order-seq coll]
  (let [item->index (into {} (map-indexed #(vector %2 %1) order-seq))]
    (->> coll
         (map #(vector (item->index %) %))
         (sort-by first compare)
         (map second))))

Elements that are not in order-seq will appear at the beginning of the sorted result, since their index will be nil.
@jonasseglare s solution seems much more efficient and elegant though, would have never occurred to me!

Using the built-in sort-by function. Elements not in the ordered sequence will show in the beginning of the result:

(defn sort-with [oxs ys]
  (let [keyfn (zipmap oxs (range))]
    (sort-by keyfn ys)))

(comment
  
  (sort-with [:breakfast :lunch :dinner] #{:lunch :breakfast :dinner})
  ;; => (:breakfast :lunch :dinner)

  (sort-with [2 3 4 :jack :queen :king :ace] [4 2 4 :king 2])
  ;; => (2 2 4 4 :king)

  (sort-with [:red :orange :yellow :green :blue :indigo :violet] [:blue 1 2 :red])
  ;; => (1 2 :red :blue)
  
  )

A minor variant of @dfuenzalida's answer that keeps only the ordered elements in the result:

(defn sort-with [order xs]
  (let [m (zipmap order (range))]
    (sort-by m (filter m xs))))

(defn sort-with [order xs]
  (let [order-map (into {} (map-indexed (fn [idx v] [v idx]) order))]
    (sort-by order-map xs)))

(defn sort-with [ordering coll]
  (transduce identity
             (fn ([res x] (assoc! res x (count res)))
                 ([res] (sort-by res coll)))
             (transient {})
             ordering))

Here's a more conventional version of the same idea without transducers.

(defn sort-with [ordering coll]
  (sort-by (reduce (fn [res x] (assoc! res x (count res))) (transient {}) ordering) coll))

The original problem asks for the unmatched elements to be appended to the result, in natural sort order. Just for fun, I came up with a solution for this variant:

(defn sort-with-original [order xs]
  (let [m (zipmap order (range))]
    (sort-by #(if-let [i (m %)]
                [i]
                [nil %])
             xs)))

(apply str (sort-with-original "edc" "abcdefzyx"))   ; => "edcabfxyz"

(defn sort-with
  "Sort `xs` according to the order defined by `template`.
  See https://edabit.com/challenge/5cefoardyvgEb52JB for full instructions.

   Note: the original exercise suggests that if the character isn't in the template,
  then sort it alphabetically - Eric doesn't mention this because he tries to make it work on more generic items.
  Thus we don't implement this requirement either."
  [template xs]
  ;; I'd like to use sort-by and just found proper 'key-fn'
  ;; So I think it could be something that returns an index of the element in the template?
  (sort-by (fn [item] (.indexOf (vec template) item))
           xs))

(defn sort-with [order xs]
  (sort-by (->> order (into {} (map-indexed (fn [i x] [x i]))))
           xs))