Contexte

La monnaie officielle de la nation imaginaire du Golfenistan est le foo , et il n'y a que trois types de pièces en circulation: 3 foos, 7 foos et 8 foos. On peut voir qu'il n'est pas possible de payer certains montants, comme 4 foos, en utilisant ces pièces. Néanmoins, toutes les quantités suffisamment importantes peuvent être formées. Votre travail consiste à trouver le plus grand montant qui ne peut pas être formé avec les pièces (5 foos dans ce cas), ce qui est connu comme le problème des pièces .

Contribution

Votre entrée est une liste d'entiers positifs, représentant les valeurs des pièces en circulation. Deux choses sont garanties à ce sujet:L = [n1, n2, ..., nk]

• Le GCD des éléments de Lest 1.
• L ne contient pas le chiffre 1.

Il peut ne pas être trié et / ou contenir des doublons (pensez aux pièces en édition spéciale).

Production

Puisque le GCD Lest de 1, chaque entier suffisamment grand mpeut être exprimé comme une combinaison linéaire non négative de ses éléments; en d'autres termes, nous avons

 m = a1*n1 + a2*n2 + ... + ak*nk 

pour certains entiers . Votre sortie est le plus grand entier qui ne peut pas être exprimé sous cette forme. À titre indicatif, il est connu que la sortie est toujours inférieure à , si et sont les éléments maximal et minimal de ( référence ).ai ≥ 0(n1 - 1)*(nk - 1)n1nkL

Règles

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites. Si votre langue a une opération intégrée pour cela, vous ne pouvez pas l'utiliser. Il n'y a aucune exigence en termes de temps ou d'efficacité de la mémoire, sauf que vous devriez être en mesure d'évaluer les cas de test avant de publier votre réponse.

Après avoir posté ce défi, l'utilisateur @vihan a souligné que Stack Overflow a un doublon exact . Sur la base de cette discussion Meta , ce défi ne sera pas supprimé en tant que doublon; cependant, je demande que toutes les réponses basées sur celles de la version SO doivent citer les originaux, avoir le statut de wiki communautaire et être supprimées si l'auteur original souhaite poster sa réponse ici.

Cas de test

[3, 7, 8] -> 5
[25, 10, 16] -> 79
[11, 12, 13, 14, 13, 14] -> 43
[101, 10] -> 899
[101, 10, 899] -> 889
[101, 10, 11] -> 89
[30, 105, 70, 42] -> 383
[2, 51, 6] -> 49

Pyth, 23 octets

ef!fqTs.b*NYQY^UTlQS*FQ

C'est très lent, car il vérifie toutes les valeurs jusqu'au produit de toutes les pièces. Voici une version presque identique, mais 1) réduit l'ensemble des pièces à celles qui ne sont pas divisibles les unes par les autres et 2) vérifie uniquement les valeurs jusqu'à (max(coins) - 1) * (min(coins) - 1)(47 octets):

=Qu?.A<LiHdG+GHGQYef!fqTs.b*NYQY^UTlQS*thSQteSQ

Explication

                   S            range 1 to
                    *FQ         product of input
 f                             filter by
               UT                range 0 to T 
              ^  lQ              cartesian power by number of coins
   f                            filter by
      s.b*NYQY                   sum of coin values * amounts
    qT                           equals desired number T
  !                             nothing matching that filter
e                             take last (highest) element

Perl, 60 54 51 octets

Code de 50 octets + ligne de commande de 1 octet

$.*=$_,$r.=1x$_."|"}{$_=$.while(1x$.--)=~/^($r)+$/

Poursuivra le golf et publiera une explication plus tard. L'approche de base consiste à laisser le moteur d'expression régulière effectuer le travail difficile avec la correspondance de chaînes. Par exemple, il construira une expression rationnelle similaire à ^(.{3})*(.{7})*(.{8})*$une chaîne de longueur nqui ndescend du produit des entrées et correspondra à cette chaîne jusqu'à ce qu'elle ne parvienne pas à correspondre.

Notez que cela deviendra exponentiellement lent à mesure que le nombre d'arguments augmente.

Utilisation: Les arguments sont lus depuis STDIN (nouvelle ligne séparée), par exemple:

printf "101\n10" | perl -p entry.pl

R , 84 78 octets

$a_1, a_2,\ldots$

a=scan();max((1:(b<-min(a)*max(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])

Essayez-le en ligne!

$a_i$outercolSums

Une version plus rapide mais plus longue (de deux octets) ne prend en compte que max(a):

a=scan();max((1:(min(a)*(b<-max(a))))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

Une version légèrement plus courte (78 octets) qui prend le plus souvent trop de journal ou trop d'espace pour s'exécuter Essayez en ligne est

a=scan();max((1:(b<-prod(a)))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

Python2, 188 187 octets

def g(L):
 M=max(L);i=r=0;s=[0]*M;l=[1]+s[1:]
 while 1:
    if any(all((l+l)[o:o+min(L)])for o in range(M)):return~-s[r]*M+r
    if any(l[(i-a)%M]for a in L):l[i]=1
    else:r=i
    s[i]+=1;i=(i+1)%M

La deuxième indentation est rendue comme 4 espaces sur SO, ceux-ci devraient être des tabulations.

En fait, une solution «rapide», et non bruteforce, utilise la «méthode de Wilf» comme décrit ici .

Javascript ES6, 120 130 126 128 127 125 caractères

f=a=>`${r=[1|a.sort((a,b)=>a-b)]}`.repeat(a[0]*a[a.length-1]).replace(/./g,(x,q)=>r[q]|a.map(x=>r[q+x]|=r[q])).lastIndexOf(0)

Version alternative à 126 caractères:

f=a=>{r=[1];a.sort((a,b)=>a-b);for(q=0;q<a[0]*a[a.length-1];++q)r[q]?a.map(x=>r[q+x]=1):r[q]=0;return r.join``.lastIndexOf(0)}

Tester:

"[3, 7, 8] -> 5\n\
[25, 10, 16] -> 79\n\
[11, 12, 13, 14, 13, 14] -> 43\n\
[101, 10] -> 899\n\
[101, 10, 899] -> 889\n\
[101, 10, 11] -> 89\n\
[30, 105, 70, 42] -> 383\n\
[2, 51, 6] -> 49".replace(/(\[.*?\]) -> (\d+)/g, function (m, t, r) {
  return f(JSON.parse(t)) == r
})