/*The algorithm described at http://boardgamegeek.com/article/2906986#2906986coded 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 youwant it to assume we've already drawn Alpha Centauri and go from there, type $ race 8 1 <summary_abils.txtor for concision you can type $ race 8 <summary_abils.txtand it will do the same thing. To assume we've drawn 90 cards without seeinga development power, type $ race 47 90 <summary_abils.txtand of course typing $ race <summary_abils.txtwill 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);}