32
\$\begingroup\$

A three-fruit pie is made of three different fruits. What is the most three-fruit pies you can make from the quantities of 5 fruits you have?

For example, with

1 apple
1 banana
4 mangoes 
2 nectarines
0 peaches

you can make 2 pies:

apple, mango, nectarine
banana, mango, nectarine

Input: Five non-negative integers, or a list of them.

Output: The maximum number of three-fruit pies you can make from those quantities of fruit. Fewest bytes wins.

Test cases:

1 1 4 2 0
2
2 2 2 2 2
3
0 6 0 6 0
0
12 5 3 2 1
5
1 14 14 3 2
6
0 0 1 0 50
0

Leaderboard:

var QUESTION_ID=59192,OVERRIDE_USER=20260;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>

\$\endgroup\$
  • \$\begingroup\$ I believe your example is missing two additional options: Apple, Banana, Mango and Apple, Banana, Nectarine. Thus the 1 1 4 2 0 test case should produce the output: 4. \$\endgroup\$ – cobaltduck Oct 1 '15 at 18:11
  • \$\begingroup\$ @cobaltduck But if you use the Apple and Banana in your first pie (Apple/Banana/Mango), you don't have the Apple or Banana to use in your second pie (Apple/Banana/Nectarine). \$\endgroup\$ – AdmBorkBork Oct 1 '15 at 18:29
  • 2
    \$\begingroup\$ @Timmy D: Ah, got it. It was not clear that the pies were being made simultaneously. \$\endgroup\$ – cobaltduck Oct 1 '15 at 18:49
  • \$\begingroup\$ @cobaltduck I believe they don't have to be made simultaneously, but you can't cheat by reusing the fruits you used for the first one. \$\endgroup\$ – Mr Lister Oct 3 '15 at 7:02
  • \$\begingroup\$ @Mr. Lister: Semantics. It is sufficient that there was a rule that was ambiguous (to at least one reader) and has since been clarified. \$\endgroup\$ – cobaltduck Oct 3 '15 at 12:23

11 Answers 11

34
\$\begingroup\$

Pyth, 19 18 14 bytes

-1 byte by @FryAmTheEggman

14-byte program by @isaacg

I claim that the number of pies that can be formed from an ascending list [x1,x2,x3,x4,x5] is:

floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3))

Or in code:

JSQhS/Ls~PJ_S3

[See revision history for TI-BASIC and APL programs]

Proof of correctness

Let

s3 = x1+x2+x3
s4 = x1+x2+x3+x4
s5 = x1+x2+x3+x4+x5

We want to show that P(X)=floor(min(s5/3,s4/2,s3)) is always the greatest number of pies for a list x1≤x2≤x3≤x4≤x5 of numbers of fruits 1~5.

First, we show that all three numbers are upper bounds.

  • Since there are s5 total fruits, and each pie has three fruits, ⌊s5/3⌋ is an upper bound.

  • Since there are s4 fruits that are not fruit 5, and at least two non-5 fruits are required in each pie, ⌊s4/2⌋ is an upper bound.

  • Since there are s3 fruits that are neither fruit 4 nor fruit 5, and at least one such fruit is required in each pie, s3 is an upper bound.

Second, we show that the method of taking fruits from the three largest piles always satisfies the bound. We do this by induction.

Base case: 0 pies can obviously be formed from any valid list with P(X)>=0.

Inductive step: Given any list X where P(X) > 0, we can bake one pie, leaving behind a list X' with P(X') >= P(X)-1. We do this by taking a fruit from the largest three piles 3,4,5, then resorting if needed. Bear with me; there's some casework.

  • If x2<x3, then we don't need to sort the list after removing fruits. We already have a valid X'. We know that P(X') = P(X)-1 because s5' is 3 less (because three fruits of type 1~5 were removed), s4' is 2 less, and s3' is 1 less. So P(X') is exactly one less than P(X).
  • If x3<x4, then we're similarly done.
  • Now we take the case where x2=x3=x4. We'll need to rearrange the list this time.

    • If x5>x4, then we rearrange the list by switching piles 4 and 2. s5' and s4' are still a decrease of 3 and 2 respectively, but s3'=s3-2. This isn't a problem, because if x2=x3=x4, then 2*x4<=s3->2*x4+s3 <= 2*s3 -> (x4 + s4)/2 <= s3. We have two subcases:
    • Equality, i.e. (x4,x3,x2,x1)=(1,1,1,0), in which case P(X) = 1 and we can clearly make a pie from piles 5,4,3, or:

    • (s4+1)/2 <= s3, in which case decreasing s4 by an extra 1 doesn't mean an extra decrease to P(X).

  • Now we're left with the case where x1<x2=x3=x4=x5. Now s3 will also be decreased by 1, so we need (s5/3+1) to be <=s4/2; that is, 8x5+2x1+2<=9x5+3x1, or x5+x1>=2. All cases smaller than this can be checked manually.

  • If every number is equal, it is clear that we can achieve the bound of ⌊s5/3⌋, which is always less than the other two—we simply go through the numbers in sequence.

Finally we're done. Please comment if I'm missing something, and I'll be giving a small bounty for a more elegant proof.

\$\endgroup\$
7
\$\begingroup\$

CJam, 34

q~L{J2be!\f{\.-_W#){j)7}|;}0+:e>}j

Try it online

Explanation:

q~          read and evaluate the input array
L{…}j       calculate with memoized recursion and no initial values
             using the input array as the argument
  J2b       convert 19 to base 2 (J=19), obtaining [1 0 0 1 1]
  e!        get permutations without duplicates
             these are all the combinations of three 1's and two 0's
             which represent the choices of fruit for one pie
  \         swap with the argument array
  f{…}      for each combination and the argument
    \       swap to bring the combination to the top
    .-      subtract from the argument array, item by item
    _       duplicate the resulting array
    W#)     does it contain the value -1? (calculate (index of W=-1) + 1)
    {…}|    if not
      j     recursively solve the problem for this array
      )7    increment the result, then push a dummy value
    ;       pop the last value (array containing -1 or dummy value)
  0+        add a 0 in case the resulting array is empty
             (if we couldn't make any pie from the argument)
  :e>       get the maximum value (best number of pies)
\$\endgroup\$
  • \$\begingroup\$ Does memoizing the recursion cost bytes? There's no run-time limit. \$\endgroup\$ – xnor Sep 30 '15 at 19:56
  • 2
    \$\begingroup\$ @xnor I think it actually saves 1 byte here :) \$\endgroup\$ – aditsu Sep 30 '15 at 19:57
7
\$\begingroup\$

Haskell, 62 bytes

f x=maximum$0:[1+f y|y<-mapM(\a->a:[a-1|a>0])x,sum y==sum x-3]

This defines a function f that takes in the fruit list x and returns the maximum number of pies.

Explanation

We compute the number of pies recursively. The part mapM(\a->a:[a-1|a>0])x evaluates to the list of all lists obtained from x by decrementing any positive entries. If x = [0,1,2], it results in

[[0,1,2],[0,1,1],[0,0,2],[0,0,1]]

The part between the outer [] is a list comprehension: we iterate through all y in the above list and filter out those whose sum is not equal to sum(x)-3, so we get all lists where 3 different fruits have been made into a pie. Then we recursively evaluate f on these lists, add 1 to each, and take the maximum of them and 0 (the base case, if we can't make any pies).

\$\endgroup\$
7
\$\begingroup\$

C#, 67

Recursively make one pie per iteration with fruits you have the most until you run out.

int f(List<int>p){p.Sort();p[3]--;p[4]--;return p[2]-->0?1+f(p):0;}

Test cases here

\$\endgroup\$
  • \$\begingroup\$ Not familiar with C#, but can you perhaps do p[2]-- at the same time as checking p[2]>-1? \$\endgroup\$ – xnor Oct 1 '15 at 0:58
  • \$\begingroup\$ good point, I will update the answer in a second. \$\endgroup\$ – AXMIM Oct 1 '15 at 1:04
6
\$\begingroup\$

Pyth, 29

Wtt=QS-Q0=Q+tPPQtM>3.<Q1=hZ;Z

Test suite

Sorts the input list and removes zeroes. Then, as long as you have 3 fruits, decrement the first and two last elements, and add the remaining elements to the list, before sorting it and removing zeroes again. Then increment a counter by 1.

This is actually rather quick so long as there are only 5 fruits, it can solve for very large bins of fruits, i.e. 1000,1000,1000,1000,1000 in under a second.

\$\endgroup\$
  • \$\begingroup\$ Can you prove that it's correct? \$\endgroup\$ – aditsu Sep 30 '15 at 20:33
  • \$\begingroup\$ @aditsu I haven't proved it, but I checked it against yours for several additional values. I haven't really written a proof for something like this before, but I'll try. For now, I'll say it makes sense that it should work because you always take only from the largest piles of fruit, until you exhaust the smaller ones. While greedy strategies are obviously not always inherently correct, I can't think of why it doesn't work here. \$\endgroup\$ – FryAmTheEggman Sep 30 '15 at 20:48
  • \$\begingroup\$ @FryAmTheEggman Do I understand right that you take the two most common fruits and the rarest fruit? \$\endgroup\$ – xnor Sep 30 '15 at 20:49
  • \$\begingroup\$ @xnor Yes, that is correct. Does that not work? \$\endgroup\$ – FryAmTheEggman Sep 30 '15 at 20:49
  • 1
    \$\begingroup\$ @TimmyD No, I don't (think I) have to, however it doesn't cost any bytes to remove this functionality (it actually costs more). That said, I expect Reto Koradi's solution is shorter in most languages, and obviously Thomas's is much more concise. I think the reason you don't have to re-sort is related to it not mattering which of the 3 smaller piles you take from. \$\endgroup\$ – FryAmTheEggman Oct 1 '15 at 18:20
6
+150
\$\begingroup\$

Python, general solution, 128 92 bytes

-36 bytes from @xnor, you da real mvp

g=lambda l,k:0if k>sum(l)else-(-1in l)or-~g(map(sum,zip(sorted(l),[0]*(len(l)-k)+[-1]*k)),k))

def g(a,k):b=[i for i in a if i];return 0if len(b)<k;c=sorted(b,reverse=True);return 1+g([c[i]-(k-1>i)for i in range(len(c))],k)

This works so long as my proof is correct. If it's not, let me know why so I can try to fix it. If it's uncomprehendable, let me know, and I'll attack it after a few cups of coffee.

\$\endgroup\$
  • \$\begingroup\$ Everything seems tight to me now. \$\endgroup\$ – lirtosiast Oct 10 '15 at 21:38
  • \$\begingroup\$ @Mego Thanks for working on this! Could you please include the proof in t the SE post? There's a general concern that someone reading this years later might find dead links. The LaTeX formatting should mostly just work in MathJax. \$\endgroup\$ – xnor Oct 11 '15 at 6:17
  • \$\begingroup\$ @Mego Oops, I forgot that MathJax isn't enabled here. Hmm, I'll ask what to do. \$\endgroup\$ – xnor Oct 11 '15 at 6:23
  • \$\begingroup\$ I'm awarding the bounty for this proof. Congrats! \$\endgroup\$ – xnor Oct 16 '15 at 5:43
  • \$\begingroup\$ @Mego Nope, I think your MathCloud link is the best we have. \$\endgroup\$ – xnor Oct 16 '15 at 7:57
5
\$\begingroup\$

Python 2, 78 bytes

Taking 5 numbers as input: 91 89 88 bytes

s=sorted([input()for x in[0]*5])
while s[2]:s[2]-=1;s[3]-=1;s[4]-=1;s.sort();x+=1
print x

Edit: Changing s=sorted([input()for x in[0]*5]) by s=sorted(map(input,['']*5));x=0 saves 1 byte.

Takes 5 numbers as input and prints the number of possible pies that can be made. It takes the same approach as Reto Koradi's answer -without improving byte count- but it felt like this question was missing an answer in Python.

Thanks @ThomasKwa and @xsot for your suggestion.

How it works

 s=sorted([input()for x in[0]*5]) takes 5 numbers as input, puts them in a list 
                                  and sorts it in ascending order. The result
                                  is then stored in s 

 while s[2]:                      While there are more than 3 types of fruit 
                                  we can still make pies. As the list is                     
                                  sorted this will not be true when s[2] is 0. 
                                  This takes advantage of 0 being equivalent to False.

 s[2]-=1;s[3]-=1;s[4]-=1          Decrement in one unit the types of fruit 
                                  that we have the most

 s.sort()                         Sort the resulting list

 x+=1                             Add one to the pie counter

 print x                          Print the result

Note that variable x is never defined, but the program takes advantge of some leakage python 2.7 has. When defining the list s with list comprehension the last value in the iterable ([0]*5 in this case) is stored in the variable used to iterate.

To make things clearer:

>>>[x for x in range(10)]
>>>x
9

Taking a list as input: 78 bytes

Thanks @xnor @xsot and @ThomasKwa for suggesting changing the input to a list.

s=sorted(input());x=0
while s[2]:s[2]-=1;s[3]-=1;s[4]-=1;s.sort();x+=1
print x

How it works

It works the same way the above code, but in this case the input is already a list so there is no need of creating it and variable x has to be defined.

Disclaimer: This is my first attempt at golfing and it feels it can still be golfed, so suggest any changes that could be made in order to reduce byte count.

\$\endgroup\$
  • 1
    \$\begingroup\$ You're allowed to have the input already in a list; s[2]>0-> s[2], since the number in the pile is always nonnegative. \$\endgroup\$ – lirtosiast Oct 1 '15 at 7:30
  • \$\begingroup\$ Thomas Kwa pointed out that you may assume the input is already given as a list, so you can just do s=sorted(input()). Also, your current byte count is 89; newlines count as a single char. \$\endgroup\$ – xnor Oct 1 '15 at 7:54
  • \$\begingroup\$ @ThomasKwa already pointed out that you could accept the input as a list, but if you insist on accepting multi-line input, replace the first line with the following to save a byte: s=sorted(map(input,['']*5));x=0. \$\endgroup\$ – xsot Oct 1 '15 at 7:57
4
\$\begingroup\$

CJam, 23 bytes

0l~{\)\$2/~+:(+_2=)}g;(

Try it online

This takes fruit from the 3 largest piles in each iteration, and counts the number of iterations.

I don't have a mathematical proof that this always gives the correct result. It does for the given test examples, and I'll believe that it works for all cases until somebody gives me a counter example.

The intuitive explanation I used to convince myself: To maximize the number of pies, you need to keep as many piles non-empty as you can. That's because you lose the ability to make more pies as soon as you have 3 or more empty piles.

This is achieve by always taking fruit from the largest piles. I can't think of a case where taking fruit from a smaller pile would lead to a better situation than taking fruit from a larger pile.

I have slightly more formal reasoning in my head. I'll try to think of a way to put it into words/formula.

\$\endgroup\$
  • \$\begingroup\$ I've been trying to use induction; maybe we can combine our ideas to find a formal proof. \$\endgroup\$ – lirtosiast Oct 1 '15 at 4:30
  • \$\begingroup\$ @ThomasKwa I haven't come up with anything clear enough that would sound convincing if I write it down. It all comes down to the fact that I see absolutely no reason why it would ever be better to take from a smaller stack over a larger stack. While there are clearly situations where taking from a smaller stack would be worse. I also entered some random moderately large numbers into both mine and aditsu's solutions, and they produced the same result. My solution is also consistent with your formula for the examples I tried. \$\endgroup\$ – Reto Koradi Oct 1 '15 at 6:52
3
\$\begingroup\$

><>, 76 bytes

0&4\/~}&?!/
@:@<\!?:}$-1@@$!?&+&:)@:@
,:&:@(?$n;/++:&+::2%-2,:&:@(?$&~+:3%-3

Turns out sorting in ><> isn't easy! This program relies on the proof put forward by Thomas Kwa to be true, which certainly looks to be the case with the test cases.

The 5 input numbers are expected to be present on the stack at the program's start.

The first two lines sort the numbers on the stack, and the third performs the calculation floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3)), taken from Thomas's answer.

\$\endgroup\$
  • \$\begingroup\$ Would it be shorter if you calculate all the sums of three/four elements, and the min of those? \$\endgroup\$ – lirtosiast Oct 1 '15 at 17:11
  • \$\begingroup\$ @ThomasKwa I looks like that would involve finding the permutations of the input set, summing the topmost 3 and 4 elements of each and taking the smallest of them? I don't think finding the permutations wouid be shorter than the sort/calculate approach I've used, especially in a stack-based language. If know of any handy algorithms for generating permutations in a stack-based language I'd be interested to see :o) \$\endgroup\$ – Sok Oct 5 '15 at 8:01
2
\$\begingroup\$

Python 2, 59 bytes

h=lambda l,k=3:k*'_'and min(h(sorted(l)[:-1],k-1),sum(l)/k)

A general method that works for any n and k. The k=3 makes the fruits per pie default to 3, but you can pass in a different value. The recursion uses the fact that strings are bigger than numbers in Python 2, letting the empty string represent the base case of infinity.

This method uses the fact that always taking the most common fruit is optimal, so we consider each possible rank of fruit as a limiting factor. I've reproven that fact below.


Mego's proof made me think of this more direct proof that repeatedly taking the most common fruits is optimal. This is stated with pies of k fruits.

Theorem: Repeatedly taking the k most common fruits gives the optimal number of pies.

Proof: We will show that if N pies are possible, then the most-common-fruit strategy produces at least N pies. We do this by switching fruits among the N pies to make them match the ones produced by this strategy, while keeping the pies valid.

Let's make it so the first pie (call it p) contain the most common fruits. If it doesn't yet, it must contain a fruit i, but not a more common fruit j. Then, the remaining pies have strictly more of fruit j than fruit i, and so some other pie q must contain j but not i. Then, we can swap fruit i from pie p with fruit j from pie q, which keeps N pies having distinct fruit.

Repeat this process until p has the k most common fruits.

Then, set pie p aside, and repeat this process for the next pie to make it have the most common remaining fruits. Keep doing this until the pies are the sequence produced by the most-common-fruit stategy.

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 92 Bytes

$a=($args|sort)-ne0;while($a.count-ge3){$a[0]--;$a[-1]--;$a[-2]--;$a=($a-ne0;$c++}($c,0)[!$c]

Uses the same greedy-based algorithm as FryAmTheEggman's answer ... just a lot wordier in PowerShell....

$a=($args|sort)-ne0  # Take input arguments, sort them, remove any 0's
while($a.count-ge3){ # So long as we have 3 or more fruit piles
  $a[0]--            # Remove one from the first element...
  $a[-1]--           # ... the last element ...
  $a[-2]--           # ... and the second-to-last.
  $a=$a-ne0          # Remove any 0's from our piles
  $c++               # Increment how many pies we've made
}                    #
($c,0)[!$c]          # Equivalent to if($c){$c}else{0}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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