Écrivez un programme qui calcule si une valeur monétaire entrée, sous forme d'entier, peut être représentée par une combinaison unique de pièces et / ou de billets, ce qui signifie que la même pièce / billet ne peut pas être utilisé plus d'une fois.

Votre programme doit prendre une valeur en entrée et peut prendre une liste de valeurs de pièces / billets via une entrée ou via l'équivalent d'un tableau dans votre langue. La liste des pièces / billets devrait pouvoir changer, alors assurez-vous qu'il est clair où cela est défini si vous utilisez une constante.

Votre programme devrait afficher n'importe quelle valeur de vérité / fausse respectivement.

Veuillez noter que la sortie de la liste des pièces / billets qui composent la valeur n'est pas requise.

EXEMPLE

En utilisant la livre sterling, (1,00 £ = 100 et 420,69 £ = 42069)

coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000]

Les éléments suivants afficheront true:

6 (1, 5)
15 (10, 5)
88 (1, 2, 5, 10, 20, 50)
512 (500, 10, 2)
7003 (5000, 2000, 2, 1)

Les éléments suivants afficheront false:

4
209
8889
4242424242
[ANYTHING ABOVE 8888]

DONNÉES DE TEST ALTERNATIVES (dollar américain)

coins = [1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000]

Bonne chance!

Brachylog 2 (TIO Nexus), 2 octets

⊇+

Essayez-le en ligne!

Prend la liste des pièces soit via une entrée standard, soit en la ajoutant au début du programme sous la forme d'un littéral de tableau (l'une ou l'autre fonctionnera, donc c'est à vous de décider ce que vous pensez être "plus légitime"; la première est autorisée par défaut Règles PPCG, cette dernière étant expressément autorisée par la question); et prend la valeur à produire comme argument de ligne de commande.

Explication

Ce programme utilise les détails d'implémentation de la façon dont le wrapper de TIO Nexus pour les fonctions Brachylog; en particulier, il vous permet de donner un argument de ligne de commande pour fournir une entrée via la sortie. (Cela n'était pas envisagé dans la conception originale de Brachylog; cependant, les langues sont définies par leur implémentation sur PPCG, et si une implémentation arrive qui fait ce dont j'ai besoin, je peux donc en profiter.) Cela signifie que le programme ressemble à ceci:

⊇+
⊇   Some subset of {standard input}
 +  sums to {the first command-line argument}

En tant que programme complet, il renvoie une valeur booléenne; true.si toutes les affirmations du programme peuvent être satisfaites simultanément, ou false.si elles ne le peuvent pas.

(Un rappel, ou pour les personnes qui ne le savent pas déjà: Brachylog 2 utilise son propre encodage de caractères dans lequel ⊇est un seul octet de long.)

05AB1E , 4 octets

æOså

Explication:

æ      Calculate the powerset of the first input
 O     Sum each element
  s    Put the second input at the top of the stack
   å   Check whether the input is in the powerset sum.

Essayez-le en ligne!

Mathematica, 25 octets

!FreeQ[Tr/@Subsets@#,#2]&

Fonction pure prenant un tableau de valeurs de pièces comme premier argument et l'entier cible comme deuxième argument, et renvoyant Trueou False.

Gelée, 6 octets

ŒPS€e@

Essayez-le en ligne!

-2 octets grâce à Leaky Nun
-13 octets grâce à Leaky Nun (longue histoire)

Rétine , 52 31 octets

\d+
$*
^((1+) |1+ )+(?<-2>\2)+$

Essayez-le en ligne! Prend la saisie sous forme de liste de pièces et de billets séparés par des espaces, suivie de la valeur souhaitée. Edit: 18 octets enregistrés grâce à @Kobi qui a débogué mon code. Explication: les deux premières lignes sont simplement converties de décimales en unaires. La troisième ligne capture alors la liste des pièces et billets. L'alternance permet au moteur de revenir en arrière et de choisir de ne pas capturer des pièces / billets spécifiques. Le groupe d'équilibrage compare ensuite la valeur à tous les suffixes de la liste de capture (inutile mais golfeur).

Brachylog , 7 octets

tT&h⊇+T

Essayez-le en ligne!

Comment ça marche

tT&h⊇+T
tT      the second input is T
  &     and
   h    the first input
    ⊇   is a superset of a set
     +  that sums up to
      T T

Y compris la combinaison, 9 octets

tT&h⊇.+T∧

Essayez-le en ligne!

Java (OpenJDK 8) , 125 octets

boolean f(int[]c,int n){int l=c.length;if(l<1)return n==0;int[]a=java.util.Arrays.copyOf(c,l-1);return f(a,n-c[l-1])|f(a,n);}

Essayez-le en ligne!

Prolog (SWI) , 46 octets

a([],0).
a([H|T],X):-Y is X-H,(a(T,Y);a(T,X)).

Essayez-le en ligne!

Fork de ma réponse Python .

JavaScript (ES6), 81 69 67 64 octets

Prend la liste des pièces cet le montant cible adans la syntaxe de curry (c)(a). Renvoie 0ou true.

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

Cas de test

let f =

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

const pound = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000];

console.log(f(pound)(6))
console.log(f(pound)(15))
console.log(f(pound)(88))
console.log(f(pound)(512))
console.log(f(pound)(7003))

console.log(f(pound)(4))
console.log(f(pound)(209))
console.log(f(pound)(8889))
console.log(f(pound)(4242424242))

Haskell , 28 octets

La fonction d'opérateur (#)prend un entier et une liste d'entiers (ou, plus généralement, n'importe quel Traversableconteneur de nombres) et renvoie a Bool.

Utiliser comme 6#[1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000].

c#l=elem c$sum<$>mapM(:[0])l

Essayez-le en ligne!

Comment ça marche

• cest la valeur souhaitée et lla liste des valeurs des pièces.
• mapM(:[0])lLes cartes de (:[0])plus l, l' appariement avec chaque valeur 0, puis construit le produit cartésien, ce qui donne la liste où chaque élément est soit la valeur correspondante l, ou 0.
• sum<$>additionne chaque combinaison et elem c$vérifie si elle cfigure dans la liste résultante.

R, 88 83 octets

-5 octets grâce à @Jarko Dubbeldam

renvoie une fonction anonyme. Il génère toutes les combinaisons possibles de pièces (à utiliser expand.gridsur des paires de T,F) et vérifie si la ou les valeurs sont présentes. kis coins puisque cest un mot réservé dans R. Peut vérifier plusieurs valeurs à la fois.

function(k,v)v%in%apply(expand.grid(Map(function(x)!0:1,k)),1,function(x)sum(k[x]))

Essayez-le en ligne!

Japt , 7 octets

à mx èN

Essayez-le en ligne! Sorties 0pour la fausse, un entier positif pour la vérité.

Explication

à mx èN
          // Implicit: U = input array, V = input integer, N = array of all inputs
à         // Take all combinations of U.
  mx      // Map each combination to its sum.
     è    // Count the number of items in the result which also exist in
      N   //   the array of inputs.
          // This returns 0 if no combination sums to V, a positive integer otherwise.
          // Implicit: output result of last expression

Python 3 , 52 octets

5 octets grâce aux ovs.

f=lambda c,n:c and f(c[1:],n-c[0])|f(c[1:],n)or n==0

Essayez-le en ligne!

Rubis , 39 octets

Renvoie nilla valeur falsifiée et la plus petite valeur de pièce dans la liste qui compose le nombre comme véridique (tous les nombres sont véridiques en Ruby).

f=->c,n{n!=0?c.find{|i|f[c-[i],n-i]}:1}

Attention cependant, cet algorithme est incroyablement lent, avec une O(C!)complexité temporelle, où Cest la longueur de la liste des pièces. Il se termine finalement, mais la plupart des cas de test expireront même sur la plupart des interprètes en ligne f(UK_POUND, 5).

Voici une version de 41 octets qui se termine beaucoup plus rapidement en ajoutant une condition de fin supplémentaire et est beaucoup plus difficile à expirer

f=->c,n{n>0?c.find{|i|f[c-[i],n-i]}:n==0}

Essayez-le en ligne!

Utilitaires Bash + GNU, 56 39

printf %$2s|egrep "^ {${1//,/\}? {}}?$"

La liste des dénominations d'entrée (non triées) est donnée sous forme de liste séparée par des virgules. La liste et la valeur d'entrée sont données sous forme de paramètres de ligne de commande.

Sortie donnée sous forme de code retour shell. Inspectez echo $?après avoir exécuté le script. 0signifie véridique, 1signifie fausseté.

Essayez-le en ligne .

• printf %$2sgénère une chaîne d' valueespaces
• "^ {${1//,/\}? {}}?$"est une extension de shell qui étend la liste des dénominations à une expression rationnelle comme ^ {1}? {2}? {5}? {10}? ... $. Il s'avère que le egrepmoteur d'expression régulière est suffisamment intelligent pour correspondre correctement à cela, quel que soit l'ordre dans lequel les dénominations sont
• egrep vérifie si la chaîne d'espaces correspond à l'expression régulière

C, 66 octets

m;v;f(n){for(m=1e5;m/=10;)for(v=5;n-=n<v*m?0:v*m,v/=2;);return!n;}

Voyez-le fonctionner ici .

C, 53 octets

g(c,w,n)int*c;{for(;n-=n<c[--w]?0:c[w],w;);return!n;}

Cette variante prend le tableau de pièces, ce qui va à l'encontre de l'objectif de ce problème, car il s'agit d'une simple soustraction.

Le premier argument est le tableau de pièces, le second est le nombre de pièces et le troisième est la valeur.

C, 48 octets

g(c,n)int*c;{for(;n-=n<*c?0:*c,*++c;);return!n;}

Une alternative à la variante précédente. Il suppose que le réseau de pièces peut être inversé et terminé par zéro.

Pyth , 6 octets

/sMtyE

Suite de tests.

CJam , 18 17 octets

q~_,2\m*\f.*::+#)

Essayez-le en ligne!

Explication

q~                  e# Read and eval input.
  _,                e# Duplicate the money list and take its length.
    2\m*            e# Take the (length)th Cartesian power of [0 1].
        \f.*        e# Element-wise multiplication of each set of 0's and 1's with the money
                    e#   list. This is essentially the powerset, but with 0s instead of 
                    e#   missing elements.
            ::+     e# Sum each set.
               #    e# Find the index of the desired amount in the list. (-1 if not found)
                )   e# Increment. -1 => 0 (falsy), anything else => nonzero (truthy)

C (gcc) , 91 octets

i,j,c[]={1,2,5};f(n){for(i=1000;i;i/=10)for(j=2;j>=0;j--)n-=n<i*c[j]?0:i*c[j];return n==0;}

Essayez-le en ligne!

PHP, 70 octets

imprime 1 pour vrai et rien pour faux

<?foreach($_GET[1]as$v)$i-=$v*$r[]=($i=&$_GET[0])/$v^0;echo max($r)<2;

Essayez-le en ligne!

Octave, 39 octets

 @(L,n)any(cellfun(@sum,powerset(L))==n)

Une fonction anonyme qui prend un tableau de valeurs de pièces comme premier argument et l'entier cible comme deuxième argument, et renvoie vrai ou faux.

Essayez-le en ligne!

Mathematica, 42 octets

ListQ@NumberDecompose[#,Sort[#2,Greater]]&

contribution

[15, {10,5}]