3
$\begingroup$

This is a problem from usaco, which I solved, but I don't know how to estimate the number of times you can pour milk among the jugs, my solutions just uses a big enough number.

Here's the problem statement:

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

For example, if the input is 8, 9, 10 then the output is 1, 2, 8, 9, 10.

Another example: if the input is 2, 5, 10 then the output is 5, 6, 7, 8, 9, 10.

My approach is to recursively try all possible move sequences, keeping track of the contents of bucket C each time bucket A is empty. Currently I stop the recursion at the arbitrary depth 200. What is the correct depth to stop the recursion at?

Improve this question
$\endgroup$
4
  • $\begingroup$ Please replace your code with pseudocode. If I understand correctly, you want to know whether there is an a priori bound on the length of solutions to this problem. If so, please make it clear. $\endgroup$
    – Yuval Filmus
    Mar 14, 2016 at 10:12
  • $\begingroup$ @YuvalFilmus this is my pseudocode. Where it is unclear what it does I wrote comments, such as TreeSet is a red black tree, I think everything else is pretty clear... I try to recursively find all possible distributions of milk in jugs, but I don't know how to estimate recursion depth of the recurse function. $\endgroup$
    – Pavel
    Mar 14, 2016 at 10:14
  • $\begingroup$ Maybe you shouldn't have taken out the code... There are many ways to solve this, including DP with 3 nested loops. And some other ways. $\endgroup$
    – Pavel
    Mar 14, 2016 at 10:18
  • 1
    $\begingroup$ We don't answer programming questions here. If your question requires code then it is out of scope here. Your question was about setting a bound on the depth for your particular algorithm, which can be summarized in one sentence instead of as code. If you're unhappy, try to explain your question better. $\endgroup$
    – Yuval Filmus
    Mar 14, 2016 at 10:20

1 Answer 1

Reset to default
2
$\begingroup$

Since the total amount of water is C liters (C being the capacity of bucket C), the number of possible states is at most the number of non-negative integer solutions of $x+y+z = C$, which is $\binom{C+2}{2}$. Any sequence of moves longer than that must repeat a state. Therefore it is enough to recurse up to level $\binom{C+2}{2}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you please tell me how you got C+2 choose 2? $\endgroup$
    – Pavel
    Mar 14, 2016 at 10:22
  • $\begingroup$ That's a standard result in combinatorics. More generally, the number of solutions of $x_1+\cdots+x_n=C$ is $\binom{C+n-1}{n-1}$. $\endgroup$
    – Yuval Filmus
    Mar 14, 2016 at 10:59
  • $\begingroup$ thanks, good upper bound. However I think it can be done better, because there are constraints on the numbers. $\endgroup$
    – Pavel
    Mar 14, 2016 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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