Pigeon and grain problem: find time until all the grain is eaten

Question

Problem:

There are \$n\$ pigeons and \$m\$ grains. Pigeon \$i\$ eats a single grain every \$x_i\$ seconds. Find the time until all the grain is eaten.

Input:

A line with the integer \$m\$ giving the number of grains, followed by a line with \$n\$ integers \$x_1, x_2, \ldots, x_n\$ giving the time taken by each pigeon to eat one grain.

Currently I am doing a loop over each second and finding how many grains in that seconds are eaten. This with numpy I am able to get a good performance but for large inputs (\$m=10^{25}\$ and \$n=300000\$) the program runs forever.

What can I do mathematically to solve this?

import numpy

def melt(grains,birdTimes):
    counter=0
    counts = numpy.zeros(len(birdTimes,),dtype=numpy.int) 
    birdTimes = numpy.array(birdTimes)
    while (grains>0):
        counts=counts+1
        temp=birdTimes-counts       
        zeroA = numpy.where(temp==0)[0] 
        grains = grains - len(zeroA)
        counts[zeroA] =0
        counter+=1
    return counter

Answer 1

Basically we're looking for the smallest value of \$T\$ which satisfies the discrete equation

$$ \left\lfloor {T \over x_1} \right\rfloor + \left\lfloor {T \over x_2} \right\rfloor + \dots + \left\lfloor {T \over x_n} \right\rfloor \ge m $$

where \$\lfloor {x \over y} \rfloor\$ is the floor division operation (// in Python). So we know the regular division operation (/ in Python) will also be a valid solution to this, albeit not necessarily with the smallest possible \$T\$:

$$ {T \over x_1} + {T \over x_2} + \dots + {T \over x_n} \ge m $$

If we factor out the \$T\$ time value, we see this is just an inequality of the form:

$$ \mathrm{Time} × \mathrm{Rate\ of\ consumption} \ge \mathrm{Amount\ consumed} $$

and thus

$$ \mathrm{Time} \ge {\mathrm{Amount\ consumed} \over \mathrm{Rate\ of\ consumption}}$$

We know the rate of consumption and amount consumed, and so by refactoring the earlier inequality we get this:

$$ T\left( {1 \over x_1} + {1 \over x_2} + \dots + {1 \over x_n} \right) \ge m $$

and thus

$$ T \ge {m \over \left( {1 \over x_1} + {1 \over x_2} + \dots + {1 \over x_n} \right)} $$

You can use this as a heuristic which will get you close to your desired value of \$T\$, now your search space just needs to check values greater than the above result. Start by

T = int(M / ((1. / xs).sum()))

Then iterate upwards to the correct value using your method of choice. How about filling the smallest available remainder to the next multiple? Like so:

while True:
    v = (T // xs).sum()
    if v >= M:
        break
    T += (xs - T % xs).min()
return T

I'm sure there's a closer-to-closed-form solution to this.

Answer 2

Calculate the rate the grains are eaten and just divide to get the result? If a pigeon eats 1 grain in t seconds, then it eats 1/t grains per second, and the rates sum. Though this will result in a rounding error at the end, after there are less grains than the number of pigeons (since they don't actually consume partial grains), so you'll have to fix that if you care about the exact result.

Another way would be to find the least common multiple of the time intervals, and iterate over time slots of that length (you know they'll eat a whole number of grains in that time). Though with a large number of pigeons or large intervals that will be unwieldy.

Just so there's at least something about code review here, I'll just note that technically your code lets the number of grains get smaller than zero, if multiple pigeon try to eat the last grain. Doesn't matter though, since it happens on a single second, but some of the pigeons could mind.

Often intervals are also counted downward, it saves one subtraction on every iteration.

Answer 3

You can quickly compute the exact total number of grains that could be eaten over a given time span by multiplying the time separately by each consumption rate (== truncating division by seconds per grain) and adding up the results. Having such a function in hand, you can avoid simulating the entire course of the process by instead searching the space of possible times. For example:

1. Compute an upper bound on the time required as m * max(x_i).

2. Perform a binary search over the times between zero and the upper bound to find the least time after which all the grains have been consumed.

Complexity analysis:

• Computing the upper bound is O(n) for n pigeons, because it requires finding the maximum of an unsorted list of n elements.
• Computing total grains consumed over a specific time requires O(n) divisions and O(n) additions, so it is also O(n).
• For bounded x_i, the value of the initial upper bound on the time is O(m).
• A binary search over x elements tests O(log x) elements, and the cost of each step in this particular search is O(n), so the overall cost is O(n log m).
• Compare to complexity O(n * m) for your direct simulation approach, and note especially that your stated concern was with performance as m becomes large.