#include <math.h>

static float factorial(int n)
{
  int res = 1;
  while (n > 1)
    res *= n--;
  return res;
}

static float binomial_coeff_ln(int n, int k)
{
  return log(factorial(n) / (factorial(k) * factorial(n-k)));
}

/***********************************************************************
Returns the chance of the attacker winning, a number between 0 and 1.
If you want the chance that the defender wins just use 1-chance(...)

The algoritm calculates the probability of each possible number of HP's
the attacker has left. Maybe that info should be preserved for use in
the AI.
***********************************************************************/
float chance(int as, int ahp, int afp, int ds, int dhp, int dfp)
{
  /* number of rounds a unit can fight without dying */
  int att_N_lose = ahp/dfp + ahp%dfp;
  int def_N_lose = dhp/afp + dhp%afp;
  /* Probability of losing one round */
  float att_P_lose1 = (float) ds / (as + ds);
  float def_P_lose1 = 1 - att_P_lose1;
  float att_P_lose1_ln = log(att_P_lose1);
  float def_P_lose1_ln = log(def_P_lose1);

  /*
    This calculates 

    binomial_coeff(def_N_lose-1 + lr, lr)
      * def_P_lose1^(def_N_lose-1)
      * att_P_lose1^(lr)
      * def_P_lose1

    for each possible number of rounds lost (rl) by the winning unit.
    rl is of course less than the number of rounds the winning unit
    should lose to lose all it's hit points.
    The probabilities are then summed.

    To see this is correct consider the set of series for all valid fights.
    These series are the type (win, lose, lose...). The possible lenghts are
    def_N_lose to def_N_lose+att_N_lose-1. A series is not valid unless it
    contains def_N_lose wins, and one of the wins must be the last one, or
    the series would be equivalent the a shorter series (the attacker would
    have won one or more fights previously).
    So since the last fight is a win we disregard it while calculating. Now
    a series contains def_N_lose-1 wins. So for each possible lenght of a
    series we find the probability of every valid series and then sum.
    For a specific lenght (a "lr") every series have the probability
      def_P_lose1^(def_N_lose-1) * att_P_lose1^(lr)
    and then getting from that to the real series requires a win, ie factor
    def_N_lose. The number of series with lenght (def_N_lose-1 + lr) and
    "lr" lost fights is
      binomial_coeff(def_N_lose-1 + lr, lr)
    And by multiplying we get the formula on the top of this code block.
    Adding the cumulative probability for each valid lenght then gives the
    total probability.

    We clearly have all valid series this way. To see that we have counted
    none twice note that would require a series with a smaller series inbedded.
    But since the smaller series already included def_N_lose wins, and the
    larger series ends with a win, it would have too many wins and therefore
    cannot exist.

    In practice we take log of the formula, for efficiency reasons. If you
    remember you log rules you should be able to match the code the formula.

    (lots of talk for so little code)
  */
  float accum_prob = 0; /* accumulated probability */
  int lr; /* the number of Lost Rounds by the attacker */
  for (lr = 0; lr < att_N_lose; lr++) {
    float prob_ln = binomial_coeff_ln(def_N_lose-1 + lr, lr)
      + def_N_lose * def_P_lose1_ln + lr * att_P_lose1_ln;
    accum_prob += exp(prob_ln);
  }
  /* Yes, all that comment just for the code to here! :) */

  return accum_prob;
}

int main(int argc, char **argv)
{
  int args[6];
  int i;

  if (argc != 7) {
    printf("6 args!\n"); /* +1 for command... */
    return 0;
  }

  for (i=0; i < 6; i++)
    sscanf(argv[i+1], "%d", &args[i]);

  printf("win chance: %f\n", chance(args[0], args[1], args[2],
				    args[3], args[4], args[5]));
  return 1;
}