Bei N Dekantern (0 < N <10), die C ₀ ... C _N-1 Liter (0 < C <50) und ein Ziel G Liter enthalten können, stellen Sie bitte fest, ob es möglich ist, dieses Ziel nur mit der zu erreichen folgende Aktionen:

• Füllen Sie eine Karaffe
• Eine Karaffe leeren
• Von einer Karaffe in eine andere füllen, bis die, in die gegossen wird, voll ist oder die, aus der gegossen wird, leer ist

Die Zielmenge G muss die Wassermenge in einem der Behälter am Ende sein. Sie können keinen Ausgangsdekanter haben.

Beispiele

N : 2
C ₀ : 5
C ₁ : 12
G : 1
Ergebnis: Ja

N : 3
C ₀ : 6
C ₁ : 9
C ₂ : 21
G : 5
Ergebnis: Nr

Hinweis: Um zu berechnen, ob es möglich ist, überprüfen Sie, ob G durch die GCD der Kapazitäten teilbar ist. Stellen Sie außerdem sicher, dass es in einen Behälter passt.

Denken Sie daran, dass dies Codegolf ist , sodass der Code mit der niedrigsten Anzahl von Bytes gewinnt.

Bestenlisten

Hier ist ein Stapel Snippet sowohl eine regelmäßige Rangliste und einen Überblick über die Gewinner von Sprache zu erzeugen.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

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

Sie können den Namen der Sprache auch als Link festlegen, der dann im Leaderboard-Snippet angezeigt wird:

# [><>](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>

Jelly , 9 8 7 Bytes

-1 Byte dank @Dennis (verwenden Sie die Ganzzahldivision :, anstatt nicht weniger als, <¬)

Ṁ:a⁸g/ḍ

TryItOnline

Wie?

Ṁ: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 Bytes

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

Dieses Papier beweist ein Ergebnis, das das Problem erheblich vereinfacht. Prop 1 sagt das

Sie können ein Ziel genau dann erreichen, wenn es beides ist:

• Ein Vielfaches des größten gemeinsamen Divisors (gcd) der Kapazitäten,
• Höchstens die maximale Kapazität

Es ist klar, warum beides notwendig ist: Alle Beträge bleiben Vielfache des gcd, und das Ziel muss in einen Container passen. Der Schlüssel des Ergebnisses ist ein Algorithmus, um jeden Zielbetrag zu erzeugen, der diesen Bedingungen entspricht.

Rufen Sie den Operator %gerne an [3,6,12]%9.

Eine 37-Byte-Alternative:

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

05AB1E , 9 8 9 Bytes

Verwendet die CP-1252- Codierung

ZU¿%²X>‹‹

Erläuterung

          # 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

Probieren Sie es online!

1 Byte mit dem weniger als Trick aus Luis Mendos MATL-Antwort gespeichert

MATL , 10 Bytes

&Zd\&G<~a<

Probieren Sie es online!

Hierbei wird der @ xnor-Ansatz verwendet .

&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 Bytes

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

Probieren Sie es online !

So verwenden Sie:
Setzen Sie diese Formel überall außer A1-A10.
Geben Sie dann Ihr Dekantierungsvolumen in die Zellen A1: A9 (da die Anzahl der Dekantierungen festgelegt ist) und das Ziel in A10 ein. Zellen ohne Dekanter sollten leer bleiben. Wo auch immer Sie die Formel einfügen, sie enthält das Ergebnis. WAHR, wenn Sie das Ziel erreichen können, FALSCH, wenn Sie nicht können.

JavaScript (ES6), 58 Byte

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

Ein weiterer Port von @ xnors Antwort. Ja, ich kann es wieder benutzen reduce!

Netzhaut , 39 Bytes

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

Die Eingabe sollte eine durch Kommas getrennte Liste der Dekanter sein, gefolgt von einem Semikolon und dem Zielvolumen. Z.B:

6,9,21;5

Die Ausgabe ist 0(falsch) oder 1(wahr).

Probieren Sie es online! (Die erste Zeile aktiviert eine durch Zeilenvorschub getrennte Testsuite.)

Erläuterung

\d+
$*

Dadurch wird die Eingabe nur in unär umgewandelt. Danach ordnen wir einfach gültige Eingaben einem einzigen regulären Ausdruck zu:

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

Der innere Teil (?>...)findet den GCD. Wir finden dazu den größten Teilstring, 1+mit dem wir alle Dekanter abgleichen können (optional ,nur nach einer vollständigen Übereinstimmung der GCD). Die Atomgruppe ( (?>...)n) selbst, damit die Regex-Engine nicht zu Teilern der GCD zurückkehrt, wenn das Zielvolumen nicht erreicht werden kann (andernfalls wird die Gruppe 1irgendwann auf die Übereinstimmung mit einer einzelnen reduziert 1und alle Eingaben sind wahr). .

Sobald wir den GCD gefunden haben, versuchen wir, das Zielvolumen als Vielfaches mit einem einfachen Wert abzugleichen (\1+)$.

Schließlich überprüfen wir, ob das Zielvolumen nicht größer als die Kapazität des größten Dekanters ist, indem wir sicherstellen, dass das Volumen in jedem Dekanter mit diesem übereinstimmt (?<=\3.+).

Ruby, 35 Bytes

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

PARI / GP , 31 Bytes

Ziemlich unkompliziert. Das Überprüfen von max ( vecmax) ist sehr kostspielig und ich frage mich, ob es besser geht.

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

Perl, 47 Bytes

Beinhaltet +2 für -ap

Laufen Sie mit den Glasgrößen in der ersten Zeile von STDIN und dem Zielglas in der zweiten Zeile:

decanter.pl; echo
2 5 12
1
^D

decanter.pl:

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

Diese Lösung ist insofern ungewöhnlich, als sie die Eingabe zeilenweise verarbeitet und für jede Zeile etwas ausgibt. Die Ausgabe für die erste Zeile wurde sorgfältig so gestaltet, dass sie leer ist, während die zweite Zeile die Lösung druckt. Zwei Bytes verloren auf , ()weil <und >sind so konzipiert, dass nicht-assoziativ in Perl.

Die Regex-Lösung ist auch schön, aber 49 Bytes:

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

(einige Teile aus der Retina-Lösung gestohlen)

Geben Sie dazu STDIN als Jars ein, die durch Leerzeichen und Ziel nach a getrennt sind ::

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

Schwer zu übertreffende Sprachen mit einem eingebauten gcd(21 Bytes) und max(7 Bytes) für dieses ...

Scala, 90 53 Bytes

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

Funktioniert im Prinzip genauso wie die anderen Antworten, aber scala hat keine eingebaute gcd-Funktion. Scala hat eine eingebaute gcd-Funktion, aber nur für BigInt.