How many three-fruit pies can you make?

Question

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>

Answer 1

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.

Answer 2

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)

Answer 3

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).

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

><>, 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.

Answer 10

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.

Answer 11

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}