3
\$\begingroup\$

Once upon a time long long ago... when there was no money or stocks yet, people were trading sheep. Even before (but close to) the invention of abacus, the great-grandfather of Warren Buffet decided it was hard to keep track of sheep. He wanted to collect all his belongings and clear all his debt, so that he could invest in a new counting machine he heard that his friend, great-grandfather of Bill Gates was building from sticks and beads. All his trades were atomic i.e. he was either supposed to give exactly one sheep to someone or get exactly one sheep. Of course Grandpa Buffet has more sheep to get then to give. Actually he exactly had 749 sheep to collect and he owed 250 sheep, so he was up by 499 sheep. Because of that he built a barn exactly for 499 sheep beforehand. Then he called all 999 people and told them to get into a queue. The very first man, wanted his sheep but there was no sheep in the barn yet. He didn't like this order and wanted everyone to get in order again but first the givers and then the collectors now. At the 500th men there were no space for new sheep in the barn but there were still 250 to collect before starting to give. He gave all the collected sheep back and make them get in a queue again and went to Grandpa Gates to help him ordering. Somehow they figured out and with the help of 499 sheep, they built a lot of Abacus and lived happily ever after.

Years later, yesterday Bill Gates and Warren Buffet met in a Giving Pledge meeting. They told this story and laughed a lot. Then Gates told Buffet: "You know what, I don't know how my great-grandpa ordered 999 people but I know there are so many ways. Actually I can tell you how many if you let me...". Then he went to his room to write a code to calculate the number of possible orderings that always guarantee there is always sheep or space in the barn until the queue is empty. And he did so but being Bill Gates he has written a recursive function which solves the problem correctly but slowly. So everybody still waits for his answer. Buffet is bored, can you write a better and faster function?

p = 749
n = 250
orderings(p,n) = ?

Shortest code wins, but it must finish in minutes, not hours or days.

\$\endgroup\$

closed as unclear what you're asking by Xcali, caird coinheringaahing, Sriotchilism O'Zaic, Nissa, Toto Nov 17 '17 at 16:29

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ Thanks for the challenge. For questions on this site, an objective winning conditions is required. It seems like some combination of short code and low runtime is required, but you should make it specific. \$\endgroup\$ – isaacg May 16 '15 at 8:19
  • \$\begingroup\$ Any code that can solve this problem for given values should be good as it is calculating instead of counting. Otherwise, an algorithm that tries to count would never end for combination(999,250) = 361713029387773775435372891749922395099728363852766445058516124309371608811061565063360358477711651559664410648010377363865113901777290418162699620613880083274233922126850199373014270598629359178877646230097380575431434538474979162651084932896 number of trials, I guess. So objective for code is to give a result for 749 and 250 \$\endgroup\$ – Riddly May 16 '15 at 8:50
  • 2
    \$\begingroup\$ Alright, how about putting that in the problem statement. Something like Shortest code wins, but it must finish in minutes, not hours or days. \$\endgroup\$ – isaacg May 16 '15 at 8:55
  • \$\begingroup\$ Wouldn't the easiest ordering be 499p 250n 250p? \$\endgroup\$ – Jerry Jeremiah May 17 '15 at 21:33
  • \$\begingroup\$ @JerryJeremiah Sure, that would be one of the different ways (it's the easiest). This question asks about the number of different ways. You could also do 400p 250n 349p or even 1p 1n 1p 1n ... 1n 499p. How many such ways are there? \$\endgroup\$ – Jakube May 17 '15 at 21:36
1
\$\begingroup\$

Pyth, 33 bytes

M?+&<HGgtGH&+-499GHgGtHH1g749 250

Try it online: Pyth Compiler/Executor. Takes about 3 seconds on my laptop. The online compiler is a bit slower, but also computes the answer in about 15 seconds.

The answer is:

160547283350099323317963999889002394629262478407796913030854915361460989263675794524349914992326520887556329626280682363011590724268659750627030457440692447081328860242720905181098211539560301455338502543318855115593179999323115473879753632000

Explanation:

First some pseudo-code of the recursive function. This is quite easy to write.

function g(p, n):
   if (p > 0 and n > 0):
      count = 0
      if (occupied_places_in_barn < 499):
         count += g(p-1, n)
      if (occupied_places_in_barn > 0):
         count += g(p, n-1)
      return count
   else:
      return 1 # only one way possible

And the Pyth translation:

M                                  def g(G,H): return _
    <HG                               H < G
   &   gtGH                                 and g(G-1,H)
            +-499GH                   499-G+H
           &       gGtH                       and g(G,H-1)
  +                                   return sum of these two numbers
 ?                     H1             if H else 1
                         g749 250  call g(749,250) and print

Why is this recursive code so fast? Doesn't the function g iterate over all 1.6*10^199 possibilities?

No it doesn't. The key here is dynamic programming. We store known results in a cache and lookup the results, when we call the function with the same parameters again. One really cool feature of Python is the @lru_cache decorator, which does all the work for you. No need to manually generate such a cache and handle stuff like lookup, storing results, ... And in Pyth it's even simpler, since each function automatically uses such a cache. So in total the function g gets executed only 125499 times. Way less than 1.6*10^199 times.

\$\endgroup\$

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