Skip to content

Instantly share code, notes, and snippets.

@laurentpetit
Last active December 11, 2015 23:29
Show Gist options
  • Save laurentpetit/4677385 to your computer and use it in GitHub Desktop.
Save laurentpetit/4677385 to your computer and use it in GitHub Desktop.
Solution Clojure pour l'échoppe de monades de scalaskel - ALGORITHME COMMENTE
(defn- changes-envisageables
"Pour un montant amount, quelles quantites de pieces
de valeur faciale face pouvons-nous rendre.
Par exemple pour un montant de 21, et un pièce de valeur faciale 7,
la réponse sera (0, 1, 2, 3).
Tip: (quot amount face) renvoie le quotient entier de la division de amount
par face"
[montant valeur-faciale]
(range 0 (inc (quot montant valeur-faciale))))
(defn- reste-a-rendre
"Pour un montant amount, combien faut il rendre apres
avoir deja donne nb pieces de valeur faciale face?"
[montant nb-pieces valeur-faciale]
(- montant (* nb-pieces valeur-faciale)))
(defn changes
"A la base, on imagine un produit cartésien des combinaisons possibles.
Mais si on commence par les grosses pièces, alors on peut très exactement
générer uniquement autant de changes que de combinaisons possibles:
- il n'y a que 0.nb-baz.(montant/BAZ) possibilités d'avoir des pièces BAZ
- pour chaque valeur possible de nb-baz, le montant restant à échanger
est montant - (nb-baz * BAZ)
- pour la plus grosse pièce après BAZ, on répète l'opération ...
- .. et pour le nbre de pièces FOO, de montant 1, c'est fastoche, le reste =
le nombre de pièces !"
[montant]
(let [BAR 7, QIX 11, BAZ 21]
(for [nb-baz (changes-envisageables montant BAZ)
:let [reste (reste-a-rendre montant nb-baz BAZ)]
nb-qix (changes-envisageables reste QIX)
:let [reste (reste-a-rendre reste nb-qix QIX)]
nb-bar (changes-envisageables reste BAR)
:let [nb-foo (reste-a-rendre reste nb-bar BAR)]]
{:foo nb-foo, :bar nb-bar, :qix nb-qix, :baz nb-baz})))
@scientific-coder
Copy link

On pourrait pas éviter de se répéter avec une map { 21 :BAZ, 11 :QIX, 7 BAR} et une fonction récursive ? (je sais, je devrais le faire au lieu de poser la question /blush)

@cgrand
Copy link

cgrand commented Jan 31, 2013

@scientific-code oui ! Qqch comme ça https://gist.github.com/199482c74eb8034c147c

@laurentpetit
Copy link
Author

Oui, mais j'ai voulu faire un compromis lisibilité / puissance-généricité.

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