Probability to clear the board or win

Question

In the game Hearthstone there is a playing board containing friendly and enemy minions, and two heroes - yours and the enemy's.

To generalize and simplify, we will assume it's your turn, the opponent has 0-7 minions with given health values on the board, and is at H life points. We will ignore our side of the board entirely.

Now we will cast a supercharged version of Arcane Missiles. This ability shoots a random enemy (uniformly selected from all alive minions and the hero) for 1 damage, repeated A times. Note that if a target dies (reduced to 0 health), it can not be hit again.

Given H, A and a list L containing the health values of the minions, output the probability as a percentage accurate to 2 digits after the decimal point that either or both the hero dies, or every minion dies (clearing the board).

Some examples logically derived:

H: 30, A: 2, L: [1, 1]

We have no chance of killing our opponent here. To clear the board, both shots
must hit a minion. The first shot has a 2/3 chance of hitting a minion, then
that minion dies. The second shot has a 1/2 chance. The probability of clearing
the board or killing our opponent is thus 2/6 = 33.33%.

H: 2, A: 3, L: [9, 3, 4, 1, 9]

We have no chance of clearing the board here. 2/3 shots must hit the hero. However,
if any of the shots hit the 1 health minion, it dies, increasing the odds for
future shots.

4/6 the first shot hits a health minion. The next two shots must hit the hero,
for a total probability of 4/6 * 1/6 * 1/6.

1/6 the first shot hits the 1 health minion and it dies. The next two shots must
hit the hero, for a total probability of 1/6 * 1/5 * 1/5.

1/6 the first shot hits the hero. Then there are three options again:

    1/6 the second shot hits the hero.
    4/6 the second shot hits a healthy minion. The last shot must hit 1/6.
    1/6 the second shot hits the 1 health minion. The last shot must hit 1/5.

This last option gives a probability of 1/6 * (1/6 + 4/6 * 1/6 + 1/(5*6)). The
total probability is the chance of any of these scenarios happening, or:

    4/6 * 1/6 * 1/6 + 1/(6*5*5) + 1/6 * (1/6 + 4/6 * 1/6 + 1/(5*6)) = 7.70%

As you can see, it gets complicated quickly... Good luck!

---

Your score is the number of bytes of code of your answer. If your code computes a probability exactly rather than simulating boards, halve your score. Lowest score wins.

Answer 1

Pyth, (67 bytes) / 2 = 33.5

L_,*lbJ*FeCbsm*hd/JedbM?&hHstH?GymgtG-XdKH_1_!dlH,01,TT*100cFghQstQ

This qualifies for the bonus even though I had to manually implement arbitrary precision rationals.

(I wish Pyth5 was already a thing).

Input from STDIN in the format A, H, L

Demonstration.

Corrected to output percentage. Percentage is as acurate as possible, due to use of integer math until the last step.

At the high level, the first segment, L_,*lbJ*FeCbsm*hd/Jedb, is a helper function which takes a list of rationals in the form of 2 element lists, and outputs their average as an (unreduced) rational.

The second segment, M?&hHstH?GymgtG-XdKH_1_!dlH,01,TT, recusively calculates the probability of victory.

The third segment, cFghQstQ formats the input to fit the function and performs the final division.

On the second example case, the final unreduced 2-tuple is too long to fit on the screen:

[83158592487544376524800000000000000000000, 1079462498636393349120000000000000000000000]

Fortunately, Pyth does have arbitrary precision integers.

Answer 2

Ruby, Score: 328/2 = 164

Here is a ruby solution that calculates the answer exactly (and then truncates the answer as specified), using the power of recursion. You run it in irb with the g function:

require 'rational'
def c(h, a, l)
  l=l.reject { |m| m == 0 }
  return 1.to_r if l.empty? ||h==0
  return 0.to_r if a==0
  a-=1
  n=[c(h-1, a, l), *((0..l.length-1).map { |i| nl = l.dup;nl[i]-=1;c(h, a, nl)})]
  n.inject(:+)/n.length
end
def g(h, a, l)
  puts "%.2f%%" % (c(h.to_r, a.to_r, l.map(&:to_r)) * 100)
end

Example output:

> g 30, 2, [1,1]
33.33%
> g 2, 3, [9,3,4,1,9]
7.70%