current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 17 down vote favorite
1

Given N decanters (0 < N < 10) with capacities C0 ... CN-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
C0: 5
C1: 12
G: 1
Result: Yes

N: 3
C0: 6
C1: 9
C2: 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 , 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>

share|improve this question
    
Related. – Martin Ender♦ 12 hours ago
    
Is there a "output decanter"? Aka, if I have a decanter of size 1, is any capacity possible? – Nathan Merrill 12 hours ago
    
@MartinEnder Ahh. Fixed. – Oliver Ni 12 hours ago
    
@NathanMerrill There is no "output decanter." You need to be able to get it in one of the decanters given. – Oliver Ni 12 hours ago
7  
This same challenge was being Sandboxed. – xnor 11 hours ago
up vote 9 down vote

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]
share|improve this answer
    
I believe the goal has to fit in one of the decanters, it should be less than the largest decanter's volume (based on @Oliver's comment "You need to be able to get it in one of the decanters given."). – m-chrzan 11 hours ago
    
Conveniently, that's actually the definition used in the paper and I misread, so that's an easy fix. – xnor 11 hours ago
up vote 4 down vote

05AB1E, 9 8 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 max decanter size

Try it online!

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

share|improve this answer
1  
utilizing the less than trick ... which I learned from Dennis :-) – Luis Mendo 10 hours ago
    
The actual answer is still 9 bytes ;-) – ETHproductions 9 hours ago
    
@ETHproductions Oops! Seems I only updated the explanation and TIO link, not the actual code. Thanks :) – Emigna 9 hours ago
    
I think you need to test with less than or equal (or not greater than). For example [6,6,6], 6 returns 0. – Jonathan Allan 2 hours ago
up vote 3 down vote

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
share|improve this answer
up vote 3 down vote

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.

share|improve this answer
up vote 2 down vote

Ruby, 35 bytes

->n,g{g<=n.max&&1>g%n.reduce(:gcd)}
share|improve this answer
up vote 2 down vote

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!

share|improve this answer
3  
Alternate sub-function: e=>n<=e is a visual palindrome ;) – ETHproductions 10 hours ago
up vote 2 down vote

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
share|improve this answer
up vote 1 down vote

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.