389 - PurelyFunctional.tv Newsletter https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-389-repl-withdrawal/

00 frugal gentleman.md

The Frugal Gentleman

George likes to appear generous, but he's also very frugal, especially when he buys wine. Here's his strategy: if there are two or more wines to choose from, he buys the second cheapest. That way, he doesn't appear to buy the cheapest, but he avoid buying the more expensive options. Write a function that takes a collection of wines and returns the name of George's choice.

Examples

(choose-wine [{:name "White" :price 10.99}
              {:name "Red"   :price 8.74}
              {:name "Rosé"  :price 12.22}]) ;=> "White"

(choose-wine [{:name "White" :price 10.99}]) ;=> "White"

(choose-wine [{:name "White" :price 10.99}
              {:name "Rosé"  :price 12.22}]) ;=> "Rosé"

Thanks to this site for the challenge idea where it is considered Hard level in Ruby.

Email submissions to eric@purelyfunctional.tv before August 09, 2020. You can discuss the submissions in the comments below.

Alan Thompson.clj

(ns tst.demo.core
  (:use tupelo.core tupelo.test)
  (:require
    [schema.core :as s]
    [tupelo.schema :as tsk]))

(s/defn choose-wine :- s/Str
  [wines :- [tsk/KeyMap]]
  (let [wines-sorted (sort-by :price wines)
        wine         (if (<= 2 (count wines-sorted))
                       (second wines-sorted)
                       (first wines-sorted))
        wine-name    (:name wine)]
    wine-name))

(dotest
  (is= "White" (choose-wine [{:name "White" :price 10.99}
                             {:name "Red" :price 8.74}
                             {:name "Rosé" :price 12.22}]))

  (is= "White" (choose-wine [{:name "White" :price 10.99}]))

  (is= "Rosé" (choose-wine [{:name "White" :price 10.99}
                            {:name "Rosé" :price 12.22}])))

Damian Hryniewicz.clj

(defn choose-wine [wines]
  (->>
    (reduce
      (fn [[{lowest-price :price :as cheapest}
            {second-lowest-price :price}
            :as agg]
           {:keys [price] :as wine}]
        (cond
          (< price (or lowest-price ##Inf))
          [wine cheapest]

          (< price (or second-lowest-price ##Inf))
          [cheapest wine]
          
          :else agg))
      []
      wines)
    (last)
    (:name)))
=> #'dev/choose-wine
(let [coll (repeatedly 1000000 (fn []
                            {:name (util/uuid)
                             :price (rand-int 1000)}))]
  (time (choose-wine coll)))
"Elapsed time: 13634.7513 msecs"
=> #uuid"dca9d019-7453-49e7-9303-7ae23b626b88"

Eric.clj

(ns wine
  (:require [clojure.test :refer [deftest are]]))

(defn choose-wine
  "Chooses the best wine to gift that is not the cheapest of all wines."
  [wines]
  (let [ordered (->> wines
                     (sort-by :price)
                     (reverse))]
    (or (:name (cond
                 (<= (count ordered) 2) (first ordered)
                 :else (second ordered)))
        "")))

(deftest choose-wine-test
  (are [x y] (= x y)
             "White" (choose-wine [{:name "White" :price 10.99}
                                   {:name "Red"   :price 8.74}
                                   {:name "Rosé"  :price 12.22}])
             "White" (choose-wine [{:name "White" :price 10.99}])
             "Rosé"  (choose-wine [{:name "White" :price 10.99}
                                   {:name "Rosé"  :price 12.22}])
             "" (choose-wine [])
             "" (choose-wine nil)))

Jaihindh Reddy.clj

Of course the first cut is to simply sort the whole thing:
(defn choose-wine [wines]
  (->> (sort-by :price wines)
       (take 2)
       last
       :name))

If we have lots of wines, this starts to become quite inefficient, considering it's superlinear. From here, I have two approaches. We can either do two passes to get the second-cheapest:
(defn choose-wine [wines]
  (let [min-price (apply min (map :price wines))
        {[cheapest] true,
         others false} (group-by #(= min-price (:price %)) wines)]
    (if (seq others)
      (:name (apply min-key :price others))
      (:name cheapest))))

While this is technically linear-time, the constant-factor is probably not too good, considering the fact that we're looping over the wines thrice, once to get min-price, once in group-by, and once in min-key. With more care, we can do it only once:
(defn- minmax [keyfn x y]
  (if (<= (keyfn x) (keyfn y))
    [x y]
    [y x]))

(defn- insert-pair
  "inserts z into [x y] sorted pair using keyfn
  returning the sorted pair after insertion"
  [keyfn [x y] z]
  (let [x' (keyfn x), y' (keyfn y), z' (keyfn z)]
    (if (<= y' z') [x y]
      (if (<= z' x') [z x] [x z]))))

(defn choose-wine [wines]
  (let [rst (nthnext wines 2)]
    (if-not rst
      (:name (apply max-key :price wines))
      (->> rst
           (reduce #(insert-pair :price % %2)
                   (minmax :price
                           (first wines)
                           (second wines)))
           last
           :name))))

Levi.clj

(defn choose-wine [winelist]
  (let [wine-prices (->> winelist (map :price) distinct sort)
        second-cheapest-price (->> wine-prices (take 2) last)
        second-cheapest-wine (->> winelist (filter (fn [wine] (= (:price wine) second-cheapest-price))) first)]
    (:name second-cheapest-wine)))

(choose-wine [{:name "White" :price 10.99}
              {:name "Red"   :price 8.74}
              {:name "Rosé"  :price 12.22}]) ;=> "White"

(choose-wine [{:name "White" :price 10.99}]) ;=> "White"

(choose-wine [{:name "White" :price 10.99}
              {:name "Rosé"  :price 12.22}]) ;=> "Rosé"

In Ruby:

def choose_wine(winelist)
  wine_prices = winelist.map{|wine| wine[:price]}.uniq.sort
  second_cheapest_price = wine_prices.take(2).last
  second_cheapest_wine = winelist.filter{|wine| wine[:price] == second_cheapest_price}.first
  second_cheapest_wine[:name]
end

choose_wine [{:name => "White", :price  => 10.99},
             {:name => "Red"  , :price  => 8.74},
             {:name => "Rosé" , :price  => 12.22},] # => "White"

choose_wine [{:name => "White", :price => 10.99}] # => "White"

choose_wine [{:name => "White", :price => 10.99},
             {:name => "Rosé" , :price => 12.22},] # => "Rosé"

Mark Champine.clj

(defn choose-wine [wines]
  (or (:name (second (sort-by :price wines)))
      (:name (first wines))))

Neil McCallum.clj

;; the only thing here is to realize that cheapest is not necessarily a unique value

(defn choose-wine
  "using price grouping"
  [wines]
  (let [price-seq (sort (group-by :price wines))
        right-priced (if (second price-seq)
                       (second  price-seq)
                       (first price-seq))]
    (when right-priced ;; guards nil input
      (:name (first (val right-priced))))))

(defn choose-wine
  "using recursion"
  [wines]
  (loop [[cheapest & rest] (sort-by :price wines)]
    (if (empty? rest)
      (:name cheapest)
      (if (> (:price (first rest)) (:price cheapest))
        (:name (first rest))
        (recur rest)))))

ninjure.clj

(defn choose-wine [wines]
  (->> wines (sort-by :price) (take 2) last :name))

Steffan Westcott.clj

(defn choose-wine [wines]
  (->> wines (sort-by :price) (take 2) last :name))

Tamas Szabo.clj

(defn select-georges-wine [wines]
  (condp = (count wines)
    0 nil
    1 (first wines)
    (second (sort-by :price wines))))

(def choose-wine (comp :name select-georges-wine))

We are not interested in sorting the more expensive than the second cheapest wine. Hence my proposal:

(defn choose-wine [wines]
  (->>
    (reduce
      (fn [agg wine]
        (take 2 (sort-by :price (conj agg wine))))
      []
      wines)
    (last)
    (:name)))

EDIT:
But apparently it's underperformant compared to @ninjure's proposal.

EDIT2:
Now that's better:

(defn choose-wine3 [wines]
  (->>
    (reduce
      (fn [[{lowest-price :price :as cheapest}
            {second-lowest-price :price}
            :as agg]
           {:keys [price] :as wine}]
        (cond
          (< price (or lowest-price ##Inf))
          [wine cheapest]

          (< price (or second-lowest-price ##Inf))
          [cheapest wine]
          
          :else agg))
      []
      wines)
    (last)
    (:name)))
=> #'dev/choose-wine3
(let [coll (repeatedly 1000000 (fn []
                            {:name (util/uuid)
                             :price (rand-int 1000)}))]
  (time (choose-wine3 coll)))
"Elapsed time: 13634.7513 msecs"
=> #uuid"dca9d019-7453-49e7-9303-7ae23b626b88"