Skip to content

Instantly share code, notes, and snippets.

@cgrand

cgrand/answer.clj

Forked from laurentpetit/gist:4538379
Last active December 11, 2015 06:09
Show Gist options
  • Save cgrand/4557332 to your computer and use it in GitHub Desktop.
Save cgrand/4557332 to your computer and use it in GitHub Desktop.
Download ZIP
Optimisons sans trahir
Raw
answer.clj
; original
(defn best-plan [bids]
(first (vals (reduce (fn [plans {:keys [DEPART VOL DUREE PRIX]}]
(assoc plans DEPART
(max-key #(:gain % 0) (first (vals plans))
(let [[[_ {:keys [gain path] :or {gain 0}}]]
(subseq plans >= (+ DEPART DUREE))]
{:gain (+ gain PRIX) :path (cons VOL path)}))))
(sorted-map) (sort-by :DEPART > bids)))))
; avec une TreeMap en lieu et place de la sorted-map
(defn cbest-plan [bids]
(first (vals (reduce (fn [^java.util.NavigableMap plans {:keys [DEPART VOL DUREE PRIX]}]
(doto plans
(.put DEPART
(max-key #(:gain % 0) (some-> plans .firstEntry .getValue)
(let [{:keys [gain path] :or {gain 0}}
(some-> plans (.ceilingEntry (+ DEPART DUREE)) .getValue)]
{:gain (+ gain PRIX) :path (cons VOL path)})))))
(java.util.TreeMap. ^java.util.Comparator <)
(sort-by :DEPART > bids)))))
; version avec un tableau comme base de l'itération
(defn acbest-plan [bids]
(first (vals (reduce (fn [^java.util.NavigableMap plans {:keys [DEPART VOL DUREE PRIX]}]
(doto plans
(.put DEPART
(max-key #(:gain % 0) (some-> plans .firstEntry .getValue)
(let [{:keys [gain path] :or {gain 0}}
(some-> plans (.ceilingEntry (+ DEPART DUREE)) .getValue)]
{:gain (+ gain PRIX) :path (cons VOL path)})))))
(java.util.TreeMap. ^java.util.Comparator <)
(doto (to-array bids)
(java.util.Arrays/sort #(> (:DEPART %1) (:DEPART %2))))))))
; générateur de bids:
(defn bids [n h]
(vec (repeatedly n #(let [s (rand-int h)
d (inc (rand-int (- h s)))
p (inc (rand-int 100))]
{:DEPART s
:DUREE d
:PRIX p
:VOL (format "VOL%d-%d@%d" s d p)}))))
; bench
=> (let [b (bids 1e5 1e5)]
(dotimes [_ 5]
(prn)
(print "-\t") (time (best-plan b))
(print "C\t") (time (cbest-plan b))
(print "AC\t") (time (acbest-plan b)))
nil)
- "Elapsed time: 1627.093 msecs"
C "Elapsed time: 966.251 msecs"
AC "Elapsed time: 927.041 msecs"
- "Elapsed time: 1695.288 msecs"
C "Elapsed time: 946.826 msecs"
AC "Elapsed time: 970.123 msecs"
- "Elapsed time: 1706.223 msecs"
C "Elapsed time: 1194.535 msecs"
AC "Elapsed time: 946.505 msecs"
- "Elapsed time: 1589.901 msecs"
C "Elapsed time: 995.11 msecs"
AC "Elapsed time: 857.839 msecs"
- "Elapsed time: 1771.825 msecs"
C "Elapsed time: 1000.038 msecs"
AC "Elapsed time: 858.883 msecs"
nil
Raw
gistfile1.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 !

@scientific-coder
Copy link

Bravo !
C'est très instructif. (même je trouve que le "vector destructuring" en answer.clj:6 pour un elt fait un peu glof au détriment de la lisiblité pa rapport à un first )

@cgrand
Copy link
Author

cgrand commented Jan 29, 2013

@scientific-coder oh oui answer.clj:6 c'est du pur golf pour être une ligne plus court que Laurent

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