1-answer-laurent.clj

(defn optimize [bids]
  (letfn [(plan-at [plans h] (val (first (subseq plans >= h))))
          (step [plans [h bids]] 
            (assoc plans h (apply max-key :gain (val (first plans))
                             (for [{:keys [vol depart prix]} bids
                                   :let [{:keys [gain path]} (plan-at plans depart)]]
                               {:gain (+ gain prix) :path (conj path vol)}))))]
    (val (first (reduce step (sorted-map-by > 0 {:gain 0 :path []})
                  (sort-by key (group-by #(+ (:duree %) (:depart %)) bids)))))))

2-perf-tests.clj

;; (perf-test nombre-d-encheres heures-dans-une-journee)
=> (perf-test 50000 24)
"Elapsed time: 148.271 msecs"
nil
=> (perf-test 50000 5000)
"Elapsed time: 214.796 msecs"
nil
=> (perf-test 50000 50000)
"Elapsed time: 364.353 msecs"
nil
=> (perf-test 50000 100000)
"Elapsed time: 444.732 msecs"
nil

=> (perf-test 500000 24)
"Elapsed time: 1445.655 msecs"
nil
=> (perf-test 500000 5000)
"Elapsed time: 2024.673 msecs"
nil
=> (perf-test 500000 50000)
"Elapsed time: 2498.489 msecs"
nil
=> (perf-test 500000 500000)
"Elapsed time: 4518.129 msecs"
nil
=> (perf-test 500000 5000000)
"Elapsed time: 6411.039 msecs"
nil

=> (perf-test 1000000 24)
"Elapsed time: 2699.989 msecs"
nil
=> (perf-test 1000000 1000000)
"Elapsed time: 9937.694 msecs"
nil

;; temps pour resoudre 100.000 situations de 4 vols répartis sur 24h
=> (let [bids (doall (repeatedly 100000 #(generate-rand-vols 4 24)))]
     (time (reduce #(optimize %2) bids)))
"Elapsed time: 3077.237 msecs"

3-enonce.md

Location d'astronef sur Jajascript

Votre cousin par alliance, Martin O. sur la planète Jajascript vient de monter sa petite entreprise de vol spatial privée: Jajascript Flight Rental. Il loue aux grosses corporations son astronef lorsqu'elles ont de fortes charges ou un pépin avec leurs propres appareils. Il s'occupe de la maintenance et de l'entretien de son petit astronef. Il ne pouvait s'en payer qu'un pour démarrer.

Ces grosses corporations envoient des commandes de location qui consistent en un intervalle de temps, et le prix qu'ils sont prêts à payer pour louer l'astronef durant cet intervalle.

Les commandes de tous les clients sont connues plusieurs jours à l'avance. Ce qui permet de faire un planning pour une journée. Les commandes viennent de plusieurs sociétés différentes et parfois elles se chevauchent. On ne peut donc pas toutes les honorer.

Idéalement, il faut donc être capable de prendre les plus rentables, histoire de maximiser les gains de sa petite entreprise, et de s'acheter d'autres astronefs. Votre cousin passe des heures à trouver le planning idéal et vous demande pour un planning donné de calculer une solution qui maximise son gain.

Exemple

Considérez par exemple le cas où la JajaScript Flight Rental a 4 commandes :

MONAD42 : heure de départ 0, durée 5, prix 10
META18 : heure de départ 3, durée 7, prix 14
LEGACY01 : heure de départ 5, durée 9, prix 8
YAGNI17 : heure de départ 5, durée 9, prix 7

La solution optimale consiste à accepter MONAD42 et LEGACY01, et le revenu est de 10 + 8 = 18. Remarquez qu'une solution à partir de MONAD42 et YAGNI17 est faisable (l'avion serait loué sans interruption de 0 à 14) mais non optimale car le bénéfice serait que de 17.

Précisions

L'identifiant d'un vol ne dépasse jamais 50 caractères, les heures de départs, durée et prix sont des entiers positifs raisonnablement grands.

Serveur

Votre serveur doit répondre aux requêtes http POST de la forme http://serveur/jajascript/optimize avec un payload de la forme :

[
	{ \"VOL\": \"NOM_VOL\", \"DEPART\": HEURE, \"DUREE\": DUREE, \"PRIX\": PRIX },
	...
]

En reprenant l'exemple ci dessus :

[
	{ \"VOL\": \"MONAD42\", \"DEPART\": 0, \"DUREE\": 5, \"PRIX\": 10 },
	{ \"VOL\": \"META18\", \"DEPART\": 3, \"DUREE\": 7, \"PRIX\": 14 },
	{ \"VOL\": \"LEGACY01\", \"DEPART\": 5, \"DUREE\": 9, \"PRIX\": 8 },
	{ \"VOL\": \"YAGNI17\", \"DEPART\": 5, \"DUREE\": 9, \"PRIX\": 7 }
]

Vous devrez répondre le résultat suivant :

{
	\"gain\" : 18,
	\"path\" : [\"MONAD42\",\"LEGACY01\"]
}

Le gain représentant la somme optimale, path représentant l'ordre des vols.

Bons calculs !

TIL : subseq
Thx ! ☺