The Decanting Problem

Question

Given N decanters (0 < N < 10) with that can hold C₀ ... C_N-1 liters (0 < C < 50) and a goal G liters, please determine if it is possible to reach that goal using only the following actions:

• Fill a decanter
• Empty a decanter
• Pour from one decanter to another until the one being poured to is full or the one being poured from is empty

The goal amount G must be the amount of water in one of the containers at the end. You cannot have a 'output decanter'.

Examples

N: 2
C₀: 5
C₁: 12
G: 1
Result: Yes

N: 3
C₀: 6
C₁: 9
C₂: 21
G: 5
Result: No

Hint: To calculate if it is possible, check to see if G is divisible by the GCD of the capacities. Also, make sure it will fit in a container.

Remember, this is code-golf, so the code with the lowest number of bytes wins.

Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

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

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

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

You can also make the language name a link which will then show up in the leaderboard snippet:

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

Answer 1

Haskell, 35 bytes

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

This paper proves a result that vastly simplifies the problem. Prop 1 says that

You can achieve a goal exactly when it's both:

• A multiple of the greatest common divisor (gcd) of the capacities,
• At most the maximum capacity

It's clear why both of these are necessary: all amounts remain multiples of the gcd, and the goal must fit in a container. The key of the result is an algorithm to produce any goal amount that fits these conditions.

Call the operator % like [3,6,12]%9.

A 37-byte alternative:

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

Answer 2

05AB1E, 9 8 9 bytes

Uses the CP-1252 encoding

ZU¿%²X>‹‹

Explanation

          # 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

Try it online!

Saved 1 byte utilizing the less than trick from Luis Mendo's MATL answer

Answer 3

Jelly, 9 8 7 bytes

-1 byte thanks to @Dennis (use integer division, :, rather than not less than, <¬)

Ṁ:a⁸g/ḍ

TryItOnline

How?

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

Answer 4

MATL, 10 bytes

&Zd\&G<~a<

Try it online!

This uses @xnor's approach.

&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

Answer 5

Excel: 43 bytes

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

Try it online!

How to use:
Put this formula anywhere Except A1-A10.
Then input your Decant holding volumes in cells A1:A9 (because the number of decants is fixed) and the goal in A10. cells without decants should be left blank. Wherever you put the formula will contain the result. TRUE if you can achieve the goal, FALSE if you cannot.

Answer 6

JavaScript (ES6), 58 bytes

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

Another port of @xnor's answer. Yes, I get to use reduce again!

Answer 7

Retina, 39 bytes

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

Input should be a comma-separated list of the decanters, followed by a semicolon, followed by the target volume. E.g.:

6,9,21;5

Output is 0 (falsy) or 1 (truthy).

Try it online! (The first line enables a linefeed-separated test suite.)

Explanation

\d+
$*

This just converts the input to unary. Afterwards we simply match valid inputs with a single regex:

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

The part inside (?>...) finds the GCD. We do this by finding the largest substring 1+ with which we can match all the decanters (allowing an optional , only after a full match of the GCD). The atomic group (the (?>...)) itself so that the regex engine doesn't backtrack to divisors of the GCD if the target volume can't be matched (otherwise group 1 will at some point be reduced to matching a single 1 and all inputs will be truthy).

Once we've found the GCD, we try to match the target volume as a multiple of it with a simple (\1+)$.

Finally, we check that the target volume not greater than the largest decanter's capacity, by ensuring that the volume can be matched inside any decanter with (?<=\3.+).

Answer 8

Ruby, 35 bytes

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

Answer 9

PARI/GP, 31 bytes

Pretty much straightforward. Checking the max (vecmax) is very costly, I wonder if it can be done better.

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

Answer 10

Perl, 47 bytes

Includes +2 for -ap

Run with the jar sizes on the first line of STDIN and the target jar on the second line:

decanter.pl; echo
2 5 12
1
^D

decanter.pl:

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

This solution is unusual in that it processes the input line by line and outputs something for each of them. The output for the first line was carefully designed to be empty while the second line prints the solution. Two bytes are lost on () because < and > are designed to be non-associative in perl.

The regex solution is also nice but 49 bytes:

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

(some parts stolen from the Retina solution)

For this one give input on STDIN as jars separated by spaces and target after a ::

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

Hard to beat languages with a builtin gcd (21 bytes) and max (7 bytes) for this one...

Answer 11

Scala, 90 53 bytes

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

Works basically the same as the other answers, but scala doesn't have a built-in gcd function. Scala has a built.in gcd function, but only for BigInt.