9
\$\begingroup\$

In this task you are given an odd number of white balls and the same number of black balls. The task is to count all the ways of putting the balls into bins so that in each bin there is an odd number of each color.

For example, say we have 3 white balls. The different ways are:

(wwwbbb)
(wb)(wb)(wb)

for the two different possibilities.

If we have 5 white balls the different ways are:

(wwwwwbbbbb)
(wwwbbb)(wb)(wb)
(wwwb)(wbbb)(wb)
(wb)(wb)(wb)(wb)(wb)

You can take the input, which is a single integer, in any way you like. The output is just a single integer.

Your code must be fast enough so that you have seen it complete for 11 white balls.

You can use any language or library that you like.

\$\endgroup\$
  • \$\begingroup\$ Please clarify, can our output be just the number of different ways? That is, a single number as output? \$\endgroup\$ – orlp Apr 14 '18 at 19:10
  • 5
    \$\begingroup\$ I assume this is from math.stackexchange.com/questions/2736933/… You should cite it @Lembik \$\endgroup\$ – qwr Apr 14 '18 at 19:21
  • 3
    \$\begingroup\$ I think you should take out the speed criterion or make it more specific. "Fast enough" is too vague. \$\endgroup\$ – dylnan Apr 14 '18 at 19:56
  • 1
    \$\begingroup\$ You know that PPCG users are crazy enough that they would rather spending money on using a supercomputer to compute it for 11 than taking 1 more byte? So why wasting their money? :) \$\endgroup\$ – user202729 Apr 15 '18 at 2:48
  • 1
    \$\begingroup\$ (remark: It's possible to calculate P function efficiently with a complicated formula. It may be possible to calculate this function too, with a suitable formula.) \$\endgroup\$ – user202729 Apr 18 '18 at 15:00
5
\$\begingroup\$

Pari/GP, 81 bytes

p=polcoeff;f(n)=p(p(prod(i=1,n,prod(j=1,n,1+(valuation(i/j,2)==0)*x^i*y^j)),n),n)

For more efficiency, replace 1+ with 1+O(x^(n+1))+O(y^(n+1))+ (the first O term alone already helps a lot).

Try it online! (earlier 86 byte version with a pair of unneeded parens and without the p= abbreviation)

Old version, 90 bytes

f(n)=polcoeff(polcoeff(taylor(1/prod(i=0,n,prod(j=0,n,1-x^(2*i+1)*y^(2*j+1))),x,n+1),n),n)

Computing f(11) needs a bigger stack size, the error message will tell you how to increase it. It's more efficient (but less golfy) to replace the two n that appear as second arguments to prod with (n-1)/2.

\$\endgroup\$
  • \$\begingroup\$ Works up to 13 for me! \$\endgroup\$ – user9206 Apr 15 '18 at 20:04
  • \$\begingroup\$ I guess that is with the version using (n-1)/2? \$\endgroup\$ – Christian Sievers Apr 15 '18 at 20:37
  • \$\begingroup\$ Yes, good point. \$\endgroup\$ – user9206 Apr 15 '18 at 21:07
  • \$\begingroup\$ Out of interest, do you think it's possible to compute f(500)? \$\endgroup\$ – user9206 Apr 16 '18 at 15:16
  • 2
    \$\begingroup\$ It takes a few minutes to compute f(500)=214621724504756565823588442604868476223315183681404 \$\endgroup\$ – Christian Sievers Apr 17 '18 at 0:15
7
\$\begingroup\$

Python 3, 108 bytes

C=lambda l,r,o=():((l,r)>=o)*l*r%2+sum(C(l-x,r-y,(x,y))for x in range(1,l,2)for y in range(1,r,2)if(x,y)>=o)

Recursively enumerates all sets, making sure to not get duplicates by always generating the sets in order. Reasonably fast when memoized using C = functoools.lru_cache(None)(C), but this is not necessary for n = 11.

Call C(num_white, num_black) to get your result. First couple of n:

1: 1
3: 2
5: 4
7: 12
9: 32
11: 85
13: 217
15: 539
17: 1316
19: 3146
21: 7374

To generate the results:

def odd_parts(l, r, o=()):
    if l % 2 == r % 2 == 1 and (l, r) >= o:
        yield [(l, r)]

    for nl in range(1, l, 2):
        for nr in range(1, r, 2):
            if (nl, nr) < o: continue
            for t in odd_parts(l - nl, r - nr, (nl, nr)):
                yield [(nl, nr)] + t

E.g. for (7, 7):

[(7, 7)]
[(1, 1), (1, 1), (5, 5)]
[(1, 1), (1, 1), (1, 1), (1, 1), (3, 3)]
[(1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1)]
[(1, 1), (1, 1), (1, 1), (1, 3), (3, 1)]
[(1, 1), (1, 3), (5, 3)]
[(1, 1), (1, 5), (5, 1)]
[(1, 1), (3, 1), (3, 5)]
[(1, 1), (3, 3), (3, 3)]
[(1, 3), (1, 3), (5, 1)]
[(1, 3), (3, 1), (3, 3)]
[(1, 5), (3, 1), (3, 1)]
\$\endgroup\$
  • \$\begingroup\$ Very nice indeed. \$\endgroup\$ – user9206 Apr 14 '18 at 22:49
2
\$\begingroup\$

Python 3, 180 172 bytes

def f(n):
 r=range;N=n+1;a=[N*[0]for _ in r(N)];R=r(1,N,2);a[0][0]=1
 for i in R:
  for j in R:
   for k in r(N-i):
    for l in r(N-j):a[k+i][l+j]+=a[k][l]
 return a[n][n]

Try it online!

Straightforward implementation of the generating function. Long but (somewhat) efficient. O(n4) time, O(n2) memory.

The resulting array a contains all results of all sizes up to n, although only a[n][n] is returned.

\$\endgroup\$
  • \$\begingroup\$ What does your code calculate for even n, out of interest? As in a[4][4]. \$\endgroup\$ – user9206 Apr 15 '18 at 19:37
  • \$\begingroup\$ This is the fastest solution so far too! \$\endgroup\$ – user9206 Apr 15 '18 at 20:15
  • 2
    \$\begingroup\$ @Lembik a[4][4] = Number of ways to put 4 white balls and 4 black balls into bins, each bin has an odd number of white balls and an odd number of black balls. Exacly as in the defintion. \$\endgroup\$ – user202729 Apr 16 '18 at 2:09
1
\$\begingroup\$

Python 2, 168 181 bytes

from itertools import*
r,p=range,product
def f(n):
 a,R=eval(`[[0]*n]*n`),r(1,n,2);a[0][0]=1
 for i,j in p(R,R):
  for k,l in p(r(n-i),r(n-j)):a[k+i][l+j]+=a[k][l]
 return a[-1][-1]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This is a snippet (assumes n contains the input) You should either add def f(n): or n=input() (to make it a function/full program resp.) \$\endgroup\$ – user202729 Apr 18 '18 at 14:31
  • \$\begingroup\$ And... this is Python 2, you can use a tab instead of two spaces. Saves a byte. The a can be eval(`[[0]*n]*n`) (where ` stands for repr). \$\endgroup\$ – user202729 Apr 18 '18 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy