Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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.

(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}])))
(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"
(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)))
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))))
(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é"
(defn choose-wine [wines]
(or (:name (second (sort-by :price wines)))
(:name (first wines))))
;; 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)))))
(defn choose-wine [wines]
(->> wines (sort-by :price) (take 2) last :name))
(defn choose-wine [wines]
(->> wines (sort-by :price) (take 2) last :name))
(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))
@ninjure
Copy link

ninjure commented Aug 3, 2020

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

@jtlocsei
Copy link

jtlocsei commented Aug 3, 2020

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

@werenall
Copy link

werenall commented Aug 4, 2020

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"

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