Player Selection

constrained-knapsack.clj

;; 100 ms
({:players
  [{:position :pg,
    :name "Toney Douglas",
    :salary 3800,
    :game-info "Atl@NO 08:00PM ET",
    :avg-points-per-game 26.625,
    :team-abbrev "NO",
    :avg-point-cost 142.72300469483568,
    :id 126}
   {:position :sf,
    :name "Otto Porter",
    :salary 4800,
    :game-info "Was@Bos 07:30PM ET",
    :avg-points-per-game 26.438,
    :team-abbrev "Was",
    :avg-point-cost 181.5568518748044,
    :id 79}
   {:position :sg,
    :name "Avery Bradley",
    :salary 4400,
    :game-info "Was@Bos 07:30PM ET",
    :avg-points-per-game 25.313,
    :team-abbrev "Bos",
    :avg-point-cost 173.82372882479805,
    :id 103}
   {:position :c,
    :name "Andre Drummond",
    :salary 8900,
    :game-info "Det@Pho 09:30PM ET",
    :avg-points-per-game 53.125,
    :team-abbrev "Det",
    :avg-point-cost 167.52941176470588,
    :id 6}
   {:position :sg,
    :name "Bradley Beal",
    :salary 6600,
    :game-info "Was@Bos 07:30PM ET",
    :avg-points-per-game 36.75,
    :team-abbrev "Was",
    :avg-point-cost 179.59183673469389,
    :id 34}
   {:position :pg,
    :name "George Hill",
    :salary 6100,
    :game-info "Mia@Ind 08:00PM ET",
    :avg-points-per-game 31.0,
    :team-abbrev "Ind",
    :avg-point-cost 196.7741935483871,
    :id 46}
   {:position :pf,
    :name "Kevin Love",
    :salary 7600,
    :game-info "Phi@Cle 07:30PM ET",
    :avg-points-per-game 37.55,
    :team-abbrev "Cle",
    :avg-point-cost 202.39680837327592,
    :id 14}
   {:position :c,
    :name "Al Horford",
    :salary 7400,
    :game-info "Atl@NO 08:00PM ET",
    :avg-points-per-game 38.417,
    :team-abbrev "Atl",
    :avg-point-cost 192.62305841867754,
    :id 19}],
  :total-salary 49600,
  :total-points 275.218})

;; 1 m
({:players
  [{:position :pg,
    :name "Kyle Lowry",
    :salary 7900,
    :game-info "Tor@Orl 07:00PM ET",
    :avg-points-per-game 41.8,
    :team-abbrev "Tor",
    :avg-point-cost 188.995218760572,
    :id 10}
   {:position :pg,
    :name "Jeff Teague",
    :salary 6500,
    :game-info "Atl@NO 08:00PM ET",
    :avg-points-per-game 33.75,
    :team-abbrev "Atl",
    :avg-point-cost 192.59259259259258,
    :id 36}
   {:position :pg,
    :name "Toney Douglas",
    :salary 3800,
    :game-info "Atl@NO 08:00PM ET",
    :avg-points-per-game 26.625,
    :team-abbrev "NO",
    :avg-point-cost 142.72300469483568,
    :id 126}
   {:position :pf,
    :name "Luis Scola",
    :salary 3800,
    :game-info "Tor@Orl 07:00PM ET",
    :avg-points-per-game 21.15,
    :team-abbrev "Tor",
    :avg-point-cost 179.66903397344194,
    :id 125}
   {:position :sf,
    :name "Otto Porter",
    :salary 4800,
    :game-info "Was@Bos 07:30PM ET",
    :avg-points-per-game 26.438,
    :team-abbrev "Was",
    :avg-point-cost 181.5568518748044,
    :id 79}
   {:position :c,
    :name "Andre Drummond",
    :salary 8900,
    :game-info "Det@Pho 09:30PM ET",
    :avg-points-per-game 53.125,
    :team-abbrev "Det",
    :avg-point-cost 167.52941176470588,
    :id 6}
   {:position :sg,
    :name "Bradley Beal",
    :salary 6600,
    :game-info "Was@Bos 07:30PM ET",
    :avg-points-per-game 36.75,
    :team-abbrev "Was",
    :avg-point-cost 179.59183673469389,
    :id 34}
   {:position :c,
    :name "Al Horford",
    :salary 7400,
    :game-info "Atl@NO 08:00PM ET",
    :avg-points-per-game 38.417,
    :team-abbrev "Atl",
    :avg-point-cost 192.62305841867754,
    :id 19}],
  :total-salary 49700,
  :total-points 278.055})

;; 10 m
({:players
  [{:position :pg,
    :name "T.J. McConnell",
    :salary 4000,
    :game-info "Phi@Cle 07:30PM ET",
    :avg-points-per-game 25.438,
    :team-abbrev "Phi",
    :avg-point-cost 157.24506813384102,
    :id 115}
   {:position :pg,
    :name "Stephen Curry",
    :salary 10300,
    :game-info "Den@GS 10:30PM ET",
    :avg-points-per-game 57.55,
    :team-abbrev "GS",
    :avg-point-cost 178.97480689047683,
    :id 1}
   {:position :sg,
    :name "Marcus Thornton",
    :salary 4000,
    :game-info "Hou@Sac 10:30PM ET",
    :avg-points-per-game 27.167,
    :team-abbrev "Hou",
    :avg-point-cost 147.23745820149387,
    :id 112}
   {:position :pf,
    :name "Kyle O'Quinn",
    :salary 3900,
    :game-info "Mil@NY 07:30PM ET",
    :avg-points-per-game 22.85,
    :team-abbrev "NY",
    :avg-point-cost 170.6783341309139,
    :id 123}
   {:position :pg,
    :name "Toney Douglas",
    :salary 3800,
    :game-info "Atl@NO 08:00PM ET",
    :avg-points-per-game 26.625,
    :team-abbrev "NO",
    :avg-point-cost 142.72300469483568,
    :id 126}
   {:position :sf,
    :name "Carmelo Anthony",
    :salary 8400,
    :game-info "Mil@NY 07:30PM ET",
    :avg-points-per-game 41.35,
    :team-abbrev "NY",
    :avg-point-cost 203.14390108761773,
    :id 8}
   {:position :c,
    :name "Andre Drummond",
    :salary 8900,
    :game-info "Det@Pho 09:30PM ET",
    :avg-points-per-game 53.125,
    :team-abbrev "Det",
    :avg-point-cost 167.52941176470588,
    :id 6}
   {:position :sg,
    :name "Bradley Beal",
    :salary 6600,
    :game-info "Was@Bos 07:30PM ET",
    :avg-points-per-game 36.75,
    :team-abbrev "Was",
    :avg-point-cost 179.59183673469389,
    :id 34}],
  :total-salary 49900,
  :total-points 290.855})

;; 30 m
({:players
  [{:position :sf,
    :name "Evan Fournier",
    :salary 5200,
    :game-info "Tor@Orl 07:00PM ET",
    :avg-points-per-game 34.25,
    :team-abbrev "Orl",
    :avg-point-cost 151.82481751824818,
    :id 69}
   {:position :pf,
    :name "Nerlens Noel",
    :salary 7000,
    :game-info "Phi@Cle 07:30PM ET",
    :avg-points-per-game 35.063,
    :team-abbrev "Phi",
    :avg-point-cost 199.6406483995363,
    :id 25}
   {:position :pg,
    :name "T.J. McConnell",
    :salary 4000,
    :game-info "Phi@Cle 07:30PM ET",
    :avg-points-per-game 25.438,
    :team-abbrev "Phi",
    :avg-point-cost 157.24506813384102,
    :id 115}
   {:position :pg,
    :name "Stephen Curry",
    :salary 10300,
    :game-info "Den@GS 10:30PM ET",
    :avg-points-per-game 57.55,
    :team-abbrev "GS",
    :avg-point-cost 178.97480689047683,
    :id 1}
   {:position :sg,
    :name "Marcus Thornton",
    :salary 4000,
    :game-info "Hou@Sac 10:30PM ET",
    :avg-points-per-game 27.167,
    :team-abbrev "Hou",
    :avg-point-cost 147.23745820149387,
    :id 112}
   {:position :pg,
    :name "Toney Douglas",
    :salary 3800,
    :game-info "Atl@NO 08:00PM ET",
    :avg-points-per-game 26.625,
    :team-abbrev "NO",
    :avg-point-cost 142.72300469483568,
    :id 126}
   {:position :c,
    :name "Andre Drummond",
    :salary 8900,
    :game-info "Det@Pho 09:30PM ET",
    :avg-points-per-game 53.125,
    :team-abbrev "Det",
    :avg-point-cost 167.52941176470588,
    :id 6}
   {:position :sg,
    :name "Bradley Beal",
    :salary 6600,
    :game-info "Was@Bos 07:30PM ET",
    :avg-points-per-game 36.75,
    :team-abbrev "Was",
    :avg-point-cost 179.59183673469389,
    :id 34}],
  :total-salary 49800,
  :total-points 295.968})

core.clj

(ns select-team.core
  (:require [camel-snake-kebab.core :as case]
            [clojure.data
             [csv :as csv]
             [int-map :as i]]
            [clojure.java.io :as io]
            [loco
             [constraints :as c]
             [core :as s]])
  (:import [java.lang Float Integer]))

(def ^:const point-scale 1000.0)

(defn s->int [s]
  (Integer/parseInt s))

(defn s->float [s]
  (Float/parseFloat s))

(defn parse-header [header]
  (sequence (comp (map case/->kebab-case)
                  (map keyword))
            header))

(defn point-cost [{:keys [salary avg-points-per-game]}]
  (if (zero? avg-points-per-game)
    Double/POSITIVE_INFINITY
    (/ salary avg-points-per-game)))

(defn parse-data [header data]
  (sequence (comp (map (partial zipmap header))
                  (map #(-> (update % :position (comp keyword case/->kebab-case))
                            (update :salary s->int)
                            (update :avg-points-per-game s->float)))
                  (map #(assoc % :avg-point-cost (point-cost %)))
                  (map-indexed #(assoc %2 :id %1)))
            data))

(defn load-players [path]
  (let [[head & tail] (with-open [in-file (io/reader path)]
                        (doall (csv/read-csv in-file)))
        header (parse-header head)]
    (parse-data header tail)))

(defn index-ids [players]
  (reduce (fn [m p] (assoc m (:id p) p)) (i/int-map) players))

(defn index-positions [players]
  (let [positions #{:pg :sg :sf :pf :c}]
    (reduce (fn [m {:keys [position id] :as player}]
              (if (contains? positions position)
                (update m position conj id)
                m))
            (zipmap positions (repeat (i/dense-int-set)))
            players)))

(defn slots [{:keys [pg sg sf pf c] :as positions}]
  (assoc positions
         :g (i/union pg sg)
         :f (i/union sf pf)
         :util (reduce i/union [pg sg sf pf c])))

(defn initialize-problem [{:keys [players] :as config}]
  (let [positions (index-positions players)]
    (-> config
        (assoc :ids (index-ids players)
               :positions positions
               :slots (slots positions))
        (update :min-points #(Math/round (* % point-scale))))))

(defn id->var [id]
  [:player id])

(defn ids->vars [ids]
  (map id->var ids))

(defn player-constraints [{:keys [slots ids]}]
  (let [variables (ids->vars (keys ids))]
    (conj (map #(c/$in % 0 1) variables)
          (c/$= (apply c/$+ variables) (count (keys slots))))))

(defn slot-constraints [{:keys [ids slots]} slot]
  (let [slot-ids (slot slots)
        variables (ids->vars slot-ids)]
    [(c/$>= (apply c/$+ variables) 1)]))

(defn scaled-points [{:keys [avg-points-per-game]}]
  (Math/round (* avg-points-per-game point-scale)))

(defn global-constraints [{:keys [slots players min-salary max-salary min-points]}]
  (let [variables (ids->vars (map :id players))
        salaries (map :salary players)
        points (map scaled-points players)]
    [(c/$in :total-salary min-salary max-salary)
     (c/$in :total-points min-points (->> (into (sorted-set-by >) points)
                                          (take (count (keys slots)))
                                          (reduce +)))
     (c/$knapsack salaries points variables :total-salary :total-points)]))

(defn model [{:keys [slots] :as p}]
  (concat (player-constraints p)
          (mapcat (partial slot-constraints p) (keys slots))
          (global-constraints p)))

(defn extract-players [{:keys [ids]} {:keys [total-salary total-points]
                                      :as vars}]
  {:players (->> (dissoc vars :total-salary :total-points)
                 (reduce-kv (fn [result [_ id] v]
                              (if (pos? v) (conj result (ids id)) result))
                            []))
   :total-salary total-salary
   :total-points (/ total-points point-scale)})

(defn find-best [problem time]
  (->> (s/solution (model problem)
                   :maximize :total-points
                   :timeout time)
       (extract-players problem)))

(defn find-many [problem time n]
  (->> (s/solutions (model problem)
                    :timeout time)
       (take n)
       (map (partial extract-players problem))))

(defn solve-problem [path {:keys [max-salary min-salary min-points time n]
                           :or {max-salary 50000
                                min-salary 0
                                min-points 275
                                time 1000
                                n 1}}]
  (let [problem (initialize-problem {:players (load-players path)
                                     :max-salary max-salary
                                     :min-salary min-salary
                                     :min-points min-points})]
    (if (== n 1)
      (list (find-best problem time))
      (find-many problem time n))))

optimal.clj

;; 1.06 hr
({:players
  [{:position :c,
    :name "Andrew Bogut",
    :salary 4800,
    :game-info "Den@GS 10:30PM ET",
    :avg-points-per-game 29.75,
    :team-abbrev "GS",
    :avg-point-cost 161.34453781512605,
    :id 76}
   {:position :sf,
    :name "Evan Fournier",
    :salary 5200,
    :game-info "Tor@Orl 07:00PM ET",
    :avg-points-per-game 34.25,
    :team-abbrev "Orl",
    :avg-point-cost 151.82481751824818,
    :id 69}
   {:position :pf,
    :name "Kristaps Porzingis",
    :salary 5000,
    :game-info "Mil@NY 07:30PM ET",
    :avg-points-per-game 27.85,
    :team-abbrev "NY",
    :avg-point-cost 179.5332111854045,
    :id 73}
   {:position :pg,
    :name "Stephen Curry",
    :salary 10300,
    :game-info "Den@GS 10:30PM ET",
    :avg-points-per-game 57.55,
    :team-abbrev "GS",
    :avg-point-cost 178.97480689047683,
    :id 1}
   {:position :sg,
    :name "Marcus Thornton",
    :salary 4000,
    :game-info "Hou@Sac 10:30PM ET",
    :avg-points-per-game 27.167,
    :team-abbrev "Hou",
    :avg-point-cost 147.23745820149387,
    :id 112}
   {:position :pg,
    :name "Kyle Lowry",
    :salary 7900,
    :game-info "Tor@Orl 07:00PM ET",
    :avg-points-per-game 41.8,
    :team-abbrev "Tor",
    :avg-point-cost 188.995218760572,
    :id 10}
   {:position :pg,
    :name "Toney Douglas",
    :salary 3800,
    :game-info "Atl@NO 08:00PM ET",
    :avg-points-per-game 26.625,
    :team-abbrev "NO",
    :avg-point-cost 142.72300469483568,
    :id 126}
   {:position :c,
    :name "Andre Drummond",
    :salary 8900,
    :game-info "Det@Pho 09:30PM ET",
    :avg-points-per-game 53.125,
    :team-abbrev "Det",
    :avg-point-cost 167.52941176470588,
    :id 6}],
  :total-salary 49900,
  :total-points 298.117})

project.clj

(defproject select-team "0.1.0-SNAPSHOT"
  :dependencies [[camel-snake-kebab "0.3.2"]
                 [loco "0.3.0"]
                 [org.clojure/clojure "1.7.0"]
                 [org.clojure/data.csv "0.1.3"]
                 [org.clojure/data.int-map "0.2.1"]])

unconstrained-knapsack.clj

;; 100 ms
{:players
 [{:position :pg,
   :name "Jameer Nelson",
   :salary 3900,
   :game-info "Den@GS 10:30PM ET",
   :avg-points-per-game 19.15,
   :team-abbrev "Den",
   :avg-point-cost 203.6553565372508,
   :id 118}
  {:position :sf,
   :name "Otto Porter",
   :salary 4800,
   :game-info "Was@Bos 07:30PM ET",
   :avg-points-per-game 26.438,
   :team-abbrev "Was",
   :avg-point-cost 181.5568518748044,
   :id 79}
  {:position :sg,
   :name "Avery Bradley",
   :salary 4400,
   :game-info "Was@Bos 07:30PM ET",
   :avg-points-per-game 25.313,
   :team-abbrev "Bos",
   :avg-point-cost 173.82372882479805,
   :id 103}
  {:position :c,
   :name "Andre Drummond",
   :salary 8900,
   :game-info "Det@Pho 09:30PM ET",
   :avg-points-per-game 53.125,
   :team-abbrev "Det",
   :avg-point-cost 167.52941176470588,
   :id 6}
  {:position :sg,
   :name "Bradley Beal",
   :salary 6600,
   :game-info "Was@Bos 07:30PM ET",
   :avg-points-per-game 36.75,
   :team-abbrev "Was",
   :avg-point-cost 179.59183673469389,
   :id 34}
  {:position :pg,
   :name "George Hill",
   :salary 6100,
   :game-info "Mia@Ind 08:00PM ET",
   :avg-points-per-game 31.0,
   :team-abbrev "Ind",
   :avg-point-cost 196.7741935483871,
   :id 46}
  {:position :pf,
   :name "Kevin Love",
   :salary 7600,
   :game-info "Phi@Cle 07:30PM ET",
   :avg-points-per-game 37.55,
   :team-abbrev "Cle",
   :avg-point-cost 202.39680837327592,
   :id 14}
  {:position :c,
   :name "Al Horford",
   :salary 7400,
   :game-info "Atl@NO 08:00PM ET",
   :avg-points-per-game 38.417,
   :team-abbrev "Atl",
   :avg-point-cost 192.62305841867754,
   :id 19}],
 :total-salary 49700,
 :total-points 267.743}
 
 ;; 1 m
 {:players
 [{:position :sg,
   :name "Victor Oladipo",
   :salary 7700,
   :game-info "Tor@Orl 07:00PM ET",
   :avg-points-per-game 40.05,
   :team-abbrev "Orl",
   :avg-point-cost 192.2596790682271,
   :id 13}
  {:position :pf,
   :name "Kyle O'Quinn",
   :salary 3900,
   :game-info "Mil@NY 07:30PM ET",
   :avg-points-per-game 22.85,
   :team-abbrev "NY",
   :avg-point-cost 170.6783341309139,
   :id 123}
  {:position :sf,
   :name "Marcus Morris",
   :salary 6100,
   :game-info "Det@Pho 09:30PM ET",
   :avg-points-per-game 31.25,
   :team-abbrev "Det",
   :avg-point-cost 195.2,
   :id 48}
  {:position :pg,
   :name "Lou Williams",
   :salary 4900,
   :game-info "LAL@Bkn 07:30PM ET",
   :avg-points-per-game 27.313,
   :team-abbrev "LAL",
   :avg-point-cost 179.40175188643366,
   :id 74}
  {:position :pg,
   :name "Kyle Lowry",
   :salary 7900,
   :game-info "Tor@Orl 07:00PM ET",
   :avg-points-per-game 41.8,
   :team-abbrev "Tor",
   :avg-point-cost 188.995218760572,
   :id 10}
  {:position :pg,
   :name "Toney Douglas",
   :salary 3800,
   :game-info "Atl@NO 08:00PM ET",
   :avg-points-per-game 26.625,
   :team-abbrev "NO",
   :avg-point-cost 142.72300469483568,
   :id 126}
  {:position :c,
   :name "Andre Drummond",
   :salary 8900,
   :game-info "Det@Pho 09:30PM ET",
   :avg-points-per-game 53.125,
   :team-abbrev "Det",
   :avg-point-cost 167.52941176470588,
   :id 6}
  {:position :sg,
   :name "Bradley Beal",
   :salary 6600,
   :game-info "Was@Bos 07:30PM ET",
   :avg-points-per-game 36.75,
   :team-abbrev "Was",
   :avg-point-cost 179.59183673469389,
   :id 34}],
 :total-salary 49800,
 :total-points 279.763}
 
 ;; 10 m
 {:players
 [{:position :pg,
   :name "T.J. McConnell",
   :salary 4000,
   :game-info "Phi@Cle 07:30PM ET",
   :avg-points-per-game 25.438,
   :team-abbrev "Phi",
   :avg-point-cost 157.24506813384102,
   :id 115}
  {:position :pg,
   :name "Stephen Curry",
   :salary 10300,
   :game-info "Den@GS 10:30PM ET",
   :avg-points-per-game 57.55,
   :team-abbrev "GS",
   :avg-point-cost 178.97480689047683,
   :id 1}
  {:position :sg,
   :name "Marcus Thornton",
   :salary 4000,
   :game-info "Hou@Sac 10:30PM ET",
   :avg-points-per-game 27.167,
   :team-abbrev "Hou",
   :avg-point-cost 147.23745820149387,
   :id 112}
  {:position :pf,
   :name "Kyle O'Quinn",
   :salary 3900,
   :game-info "Mil@NY 07:30PM ET",
   :avg-points-per-game 22.85,
   :team-abbrev "NY",
   :avg-point-cost 170.6783341309139,
   :id 123}
  {:position :pg,
   :name "Toney Douglas",
   :salary 3800,
   :game-info "Atl@NO 08:00PM ET",
   :avg-points-per-game 26.625,
   :team-abbrev "NO",
   :avg-point-cost 142.72300469483568,
   :id 126}
  {:position :sf,
   :name "Carmelo Anthony",
   :salary 8400,
   :game-info "Mil@NY 07:30PM ET",
   :avg-points-per-game 41.35,
   :team-abbrev "NY",
   :avg-point-cost 203.14390108761773,
   :id 8}
  {:position :c,
   :name "Andre Drummond",
   :salary 8900,
   :game-info "Det@Pho 09:30PM ET",
   :avg-points-per-game 53.125,
   :team-abbrev "Det",
   :avg-point-cost 167.52941176470588,
   :id 6}
  {:position :sg,
   :name "Bradley Beal",
   :salary 6600,
   :game-info "Was@Bos 07:30PM ET",
   :avg-points-per-game 36.75,
   :team-abbrev "Was",
   :avg-point-cost 179.59183673469389,
   :id 34}],
 :total-salary 49900,
 :total-points 290.855}

;; 30 m
{:players
 [{:position :sf,
   :name "Evan Fournier",
   :salary 5200,
   :game-info "Tor@Orl 07:00PM ET",
   :avg-points-per-game 34.25,
   :team-abbrev "Orl",
   :avg-point-cost 151.82481751824818,
   :id 69}
  {:position :pf,
   :name "Nerlens Noel",
   :salary 7000,
   :game-info "Phi@Cle 07:30PM ET",
   :avg-points-per-game 35.063,
   :team-abbrev "Phi",
   :avg-point-cost 199.6406483995363,
   :id 25}
  {:position :pg,
   :name "T.J. McConnell",
   :salary 4000,
   :game-info "Phi@Cle 07:30PM ET",
   :avg-points-per-game 25.438,
   :team-abbrev "Phi",
   :avg-point-cost 157.24506813384102,
   :id 115}
  {:position :pg,
   :name "Stephen Curry",
   :salary 10300,
   :game-info "Den@GS 10:30PM ET",
   :avg-points-per-game 57.55,
   :team-abbrev "GS",
   :avg-point-cost 178.97480689047683,
   :id 1}
  {:position :sg,
   :name "Marcus Thornton",
   :salary 4000,
   :game-info "Hou@Sac 10:30PM ET",
   :avg-points-per-game 27.167,
   :team-abbrev "Hou",
   :avg-point-cost 147.23745820149387,
   :id 112}
  {:position :pg,
   :name "Toney Douglas",
   :salary 3800,
   :game-info "Atl@NO 08:00PM ET",
   :avg-points-per-game 26.625,
   :team-abbrev "NO",
   :avg-point-cost 142.72300469483568,
   :id 126}
  {:position :c,
   :name "Andre Drummond",
   :salary 8900,
   :game-info "Det@Pho 09:30PM ET",
   :avg-points-per-game 53.125,
   :team-abbrev "Det",
   :avg-point-cost 167.52941176470588,
   :id 6}
  {:position :sg,
   :name "Bradley Beal",
   :salary 6600,
   :game-info "Was@Bos 07:30PM ET",
   :avg-points-per-game 36.75,
   :team-abbrev "Was",
   :avg-point-cost 179.59183673469389,
   :id 34}],
 :total-salary 49800,
 :total-points 295.968}