Étant donné N carafes (0 < N <10) pouvant contenir C ₀ ... C _N-1 litres (0 < C <50) et un objectif G litres, veuillez déterminer s'il est possible d'atteindre cet objectif en utilisant uniquement le actions suivantes:

• Remplissez une carafe
• Vider une carafe
• Versez d'une carafe à l'autre jusqu'à ce que celle versée soit pleine ou que celle versée soit vide

La quantité cible G doit être la quantité d'eau dans l'un des conteneurs à la fin. Vous ne pouvez pas avoir de «carafe de sortie».

Exemples

N : 2
C ₀ : 5
C ₁ : 12
G : 1
Résultat: Oui

N : 3
C ₀ : 6
C ₁ : 9
C ₂ : 21
G : 5
Résultat: Non

Astuce: Pour calculer si c'est possible, vérifiez si G est divisible par le GCD des capacités. Assurez-vous également qu'il tiendra dans un récipient.

N'oubliez pas qu'il s'agit de code-golf , donc le code avec le plus petit nombre d'octets gagne.

Classements

Voici un extrait de pile pour générer à la fois un classement régulier et un aperçu des gagnants par langue.

Pour vous assurer que votre réponse s'affiche, veuillez commencer votre réponse avec un titre, en utilisant le modèle Markdown suivant:

# Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les rayant. Par exemple:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Si vous souhaitez inclure plusieurs nombres dans votre en-tête (par exemple, parce que votre score est la somme de deux fichiers ou que vous souhaitez répertorier les pénalités de drapeau d'interprète séparément), assurez-vous que le score réel est le dernier numéro de l'en-tête:

# Perl, 43 + 2 (-p flag) = 45 bytes

Vous pouvez également faire du nom de la langue un lien qui apparaîtra ensuite dans l'extrait de classement:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

var QUESTION_ID=94202,OVERRIDE_USER=12537;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Gelée , 9 8 7 octets

-1 octet grâce à @Dennis (utilisez une division entière :, plutôt que pas moins de, <¬)

Ṁ:a⁸g/ḍ

TryItOnline

Comment?

Ṁ:a⁸g/ḍ - Main link: capacities, goal
Ṁ       - maximum capacity
 :      - integer division with goal (effectively not less than goal since non-0 is True)
  a     - and
   ⁸    - left argument (capacities)
    g/  - gcd reduce over list (gcd of capacities)
      ḍ - divides

Haskell, 35 octets

l%n=n`mod`foldr1 gcd l<1&&any(>=n)l

Ce document prouve un résultat qui simplifie considérablement le problème. Prop 1 dit que

Vous pouvez atteindre un objectif exactement quand il est à la fois:

• Un multiple du plus grand commun diviseur (pgcd) des capacités,
• Tout au plus la capacité maximale

Il est clair pourquoi les deux sont nécessaires: tous les montants restent des multiples du pgcd, et l'objectif doit tenir dans un récipient. La clé du résultat est un algorithme pour produire n'importe quel montant d'objectif qui correspond à ces conditions.

Appelez l'opérateur %comme [3,6,12]%9.

Une alternative à 37 octets:

l%n=elem n[0,foldr1 gcd l..maximum l]

05AB1E , 9 8 9 octets

Utilise l' encodage CP-1252

ZU¿%²X>‹‹

Explication

          # true if
   %      # target size modulo
ZU¿       # gcd of decanter sizes
        ‹ # is smaller than
    ²X>‹  # target size is less than or equal to max decanter size

Essayez-le en ligne!

1 octet enregistré en utilisant l'astuce moins que la réponse MATL de Luis Mendo

MATL , 10 octets

&Zd\&G<~a<

Essayez-le en ligne!

Cela utilise l'approche de @ xnor .

&Zd    % Take array C as input. Compute the gcd of its elements
\      % Take number G as input. Compute that number modulo the above. Call this A
&G     % Push the two inputs again: C, then G
<~a    % Gives 1 if some element of C is at least G; 0 otherwise. Call this B
<      % Gives true if A is 0 and B is 1; otherwise gives false

Excel: 43 octets

=AND(MOD(A10,GCD(A1:A9))=0,A10<=MAX(A1:A9))

Essayez-le en ligne !

Comment utiliser:
Mettez cette formule n'importe où sauf A1-A10.
Saisissez ensuite vos volumes de décantation dans les cellules A1: A9 (car le nombre de décantes est fixe) et l'objectif dans A10. les cellules sans décantation doivent être laissées en blanc. Partout où vous mettez la formule contiendra le résultat. VRAI si vous pouvez atteindre l'objectif, FAUX si vous ne le pouvez pas.

JavaScript (ES6), 58 octets

(n,a)=>a.some(e=>n<=e)&n%a.reduce(g=(d,e)=>d?g(e%d,d):e)<1

Un autre port de la réponse de @ xnor. Oui, je peux reduceréutiliser!

Rétine , 39 octets

\d+
$*
^(?>(1+)(,?\1)*;)(\1+)$(?<=\3.+)

L'entrée doit être une liste séparée par des virgules des carafes, suivie d'un point-virgule, suivi du volume cible. Par exemple:

6,9,21;5

La sortie est 0(fausse) ou 1(véridique).

Essayez-le en ligne! (La première ligne active une suite de tests séparés par un saut de ligne.)

Explication

\d+
$*

Cela convertit simplement l'entrée en unaire. Ensuite, nous faisons simplement correspondre les entrées valides avec une seule expression régulière:

^(?>(1+)(,?\1)*;)(\1+)$(?<=\3.+)

La partie à l'intérieur (?>...)trouve le GCD. Nous le faisons en trouvant la plus grande sous-chaîne 1+avec laquelle nous pouvons faire correspondre toutes les carafes (permettant une option ,uniquement après une correspondance complète du GCD). Le groupe atomique (le (?>...)) lui-même afin que le moteur d'expression régulière ne revienne pas aux diviseurs du GCD si le volume cible ne peut pas être mis en correspondance (sinon le groupe 1sera à un moment donné réduit à correspondre à un seul 1et toutes les entrées seront véridiques) .

Une fois que nous avons trouvé le GCD, nous essayons de faire correspondre le volume cible en tant que multiple avec un simple (\1+)$.

Enfin, nous vérifions que le volume cible n'est pas supérieur à la plus grande capacité de la carafe, en veillant à ce que le volume puisse être adapté à l'intérieur de n'importe quelle carafe (?<=\3.+).

Rubis, 35 octets

->n,g{g<=n.max&&1>g%n.reduce(:gcd)}

PARI / GP , 31 octets

Assez simple. Vérifier le max ( vecmax) est très coûteux, je me demande si cela peut être mieux fait.

f(c,g)=g%gcd(c)<1&&vecmax(c)>=g

Perl, 47 octets

Comprend +2 pour -ap

Exécutez avec les tailles de pot sur la première ligne de STDIN et le pot cible sur la deuxième ligne:

decanter.pl; echo
2 5 12
1
^D

decanter.pl:

#!/usr/bin/perl -p
$_=($_<@G)>$_%$=;$=--while@G[@F]=grep$_%$=,@F

Cette solution est inhabituelle en ce qu'elle traite l'entrée ligne par ligne et produit quelque chose pour chacun d'eux. La sortie de la première ligne a été soigneusement conçue pour être vide pendant que la deuxième ligne imprime la solution. Deux octets sont perdus sur ()car <et >sont conçus pour être non associatif en Perl.

La solution regex est également sympa mais 49 octets:

#!/usr/bin/perl -p
s/\d+/1x$&/eg;$_=/^(?>(1+)( |\1)*:)(\1+)$/&/$3./

(certaines parties volées de la solution Retina)

Pour celui-ci, donnez une entrée sur STDIN sous forme de pots séparés par des espaces et ciblez après un : :

decanter.pl <<< "2 5 12:1"

Langues difficiles à battre avec un intégré gcd(21 octets) et max(7 octets) pour celui-ci ...

Scala, 90 53 octets

def h(g:Int,a:BigInt*)=a.max>g&&a.reduce(_ gcd _)%g<1

Fonctionne essentiellement de la même manière que les autres réponses, mais scala n'a pas de fonction gcd intégrée. Scala a une fonction gcd intégrée, mais uniquement pour BigInt.