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\$
10
  • \$\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\$
    – DELETE_ME
    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\$
    – DELETE_ME
    Apr 18 '18 at 15:00
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\$
1
  • \$\begingroup\$ Very nice indeed. \$\endgroup\$
    – user9206
    Apr 14 '18 at 22:49
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\$
5
  • \$\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\$ 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\$ Apr 17 '18 at 0:15
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\$
3
  • \$\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\$
    – DELETE_ME
    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\$
2
  • \$\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\$
    – DELETE_ME
    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\$
    – DELETE_ME
    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