11
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Do you have some example inputs and expected outputs? \$\endgroup\$ – DeepSpace Aug 22 '16 at 6:24
  • 1
    \$\begingroup\$ Maybe I'm missing something, but 300.000 pigeons means 300.000 grains eaten every X seconds, so can't you just divide 10^25 by 300.000 / X and maybe check if there is any remainder? But again, maybe I'm missing something. \$\endgroup\$ – ChatterOne Aug 22 '16 at 6:51
  • 1
    \$\begingroup\$ @ChatterOne Not from his description but from the code I realized there's a different x value for each bird. \$\endgroup\$ – machine yearning Aug 22 '16 at 6:54
  • \$\begingroup\$ @DeepSpace its too large to post here. I am experiencing some error accessing pastebin. any other site where I can post input and link here. \$\endgroup\$ – Rohit Srivastava Aug 22 '16 at 9:37
  • 1
    \$\begingroup\$ @GarethRees I modified the analogy of problem. Basically I am working with an API which consumes lots of resources, I am trying to figure out the max time the infra can sustain. \$\endgroup\$ – Rohit Srivastava Aug 22 '16 at 9:46
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @GarethRees What about min(x - T % x for x in xs), does that make sense? \$\endgroup\$ – machine yearning Aug 22 '16 at 9:43
  • 1
    \$\begingroup\$ I turned all the operations over the array into numpy operations, according to my best google-guess. Again feel free to edit if I messed it up. \$\endgroup\$ – machine yearning Aug 22 '16 at 9:53
  • \$\begingroup\$ That looks good to me. \$\endgroup\$ – Gareth Rees Aug 22 '16 at 10:00
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I tried LCM, but the LCM was larger than the number of grains so chose not to go that path. I shall try the first approach. \$\endgroup\$ – Rohit Srivastava Aug 22 '16 at 9:52
2
\$\begingroup\$

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

  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 xi, 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.
\$\endgroup\$
  • \$\begingroup\$ I think that the upper bound = m/(max(xi)). i.e the m grains eaten by the pigeon who eats at largest interval. \$\endgroup\$ – Rohit Srivastava Aug 23 '16 at 6:39
  • 1
    \$\begingroup\$ @RohitSrivastava, the xi are the times taken for each pigeon to eat one grain. If there is only one pigeon, and he must eat m grains, then the time required is m * x1, not m / x1. But this is largely beside the point, as the asymptotic complexity is the same either way. \$\endgroup\$ – PellMel Aug 23 '16 at 19:04

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.