/*The algorithm described at http://boardgamegeek.com/article/2906986#2906986
coded in C by Daniel B. Cristofani, 14 December 2008.
Uses the GMP bignum library, so compile with -lgmp.
Expects a card list via stdin, format "blah abilitycode how-many blah,\n".
You can give it a starting condition via arguments, same format. So if you
want it to assume we've already drawn Alpha Centauri and go from there, type
$ race 8 1 <summary_abils.txt
or for concision you can type
$ race 8 <summary_abils.txt
and it will do the same thing. To assume we've drawn 90 cards without seeing
a development power, type
$ race 47 90 <summary_abils.txt
and of course typing
$ race <summary_abils.txt
will just start from the beginning, drawing from a complete deck.*/
#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>
int cards[64]; /*for each combo, how many cards have exactly that combo.*/
int a[64][64]; /*a[x][y] = number with all abilities in x and none in y.*/
mpz_t p[64][200]; /*p[s][m] = # of ways to have s after drawing m cards...*/
mpz_t d[200]; /*and d[m] is the denominator to make that a probability.*/
mpq_t t, e;
int k=63, m, n, r, s, x, y, f=-1;
double g;
int initpull, initcombo; /*Card # and abilities stipulated as already drawn.*/
int main(int argc,char **argv){
while (scanf("%*[^0123456789]%d%d%*[^\n]\n",&x,&y)==2)
cards[x]+=y,n+=y;
initpull=argc>2?atoi(argv[2]):argc-1;
initcombo=argc>1?atoi(argv[1]):0;
for(s=0;s<=k;s++)
for(y=0;y<=k;y++)
if(!(y&s))
for(x=0;x<=k;x++)
if(!(x&~s))
a[x][y]+=cards[s];
for(s=0;s<=k;s++)
mpz_init(p[s][initpull]);
mpz_set_si(p[initcombo][initpull],1);
mpz_init_set_si(d[initpull],1);
mpq_init(t);
mpq_init(e);
mpq_set_si(e,n-initpull,1);
for(m=initpull;m<n;m++){
for(s=0;s<=k;s++)
for(mpz_init(p[s][m+1]),r=0;r<=k;r++)
if(!(r&~s))
mpz_addmul_ui(p[s][m+1],p[r][m],a[s&~r][k&~s]-(s==r?m:0));
mpz_init(d[m+1]);
mpz_mul_si(d[m+1],d[m],n-m);
mpz_set(mpq_numref(t),p[63][m]);
mpz_set(mpq_denref(t),d[m]);
mpq_canonicalize(t);
mpq_sub(e,e,t);
if (f==-1&&mpq_cmp_si(t,1,2)>=0)
f=m-initpull, g=mpq_get_d(t)*100;
}
printf("The expected number of cards is ");
mpq_out_str(stdout,10,e);
printf(", or about %g,\nbut the probability of finishing",mpq_get_d(e));
printf(" the set within %d card%s is around %g%%.\n",f,f==1?"":"s",g);
exit(0);
}