7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If the calculations use floating-point, does that count as computing "exactly"? \$\endgroup\$ – feersum Jul 23 '15 at 23:43
  • \$\begingroup\$ @feersum If the method would be exact with an infinitely precise data type, then yes. Note however that the precision requirement is not forgiven - no matter the data type used, you must be precise to at least 2 digits after the decimal point. \$\endgroup\$ – orlp Jul 23 '15 at 23:48
  • \$\begingroup\$ Also, is OK to use intermediate floating point values if we're not going for the bonus? \$\endgroup\$ – isaacg Jul 25 '15 at 9:17
  • \$\begingroup\$ @isaacg Maybe I made myself unclear. You're free to use floating point either way, whether you go for the bonus or not. The only thing you have to do to qualify for the bonus is to make sure your answer would be exact, if hypothetically you'd replace the floating point numbers with infinitely precise reals. Note however that the precision requirement is not forgiven - no matter the data type used, you must be precise to at least 2 digits after the decimal point. \$\endgroup\$ – orlp Jul 25 '15 at 13:31
  • \$\begingroup\$ @orlp OK, but intermediate floating point values means that on sufficiently complicated board states there will be some inaccuracy. So I'm sticking to arbitrary precision. \$\endgroup\$ – isaacg Jul 25 '15 at 14:14
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You must give the answer as a percentage accurate to 2 digits after the decimal point . \$\endgroup\$ – orlp Jul 25 '15 at 13:31
  • \$\begingroup\$ @orlp Oh, I thought you meant at least, not exactly. Will change. \$\endgroup\$ – isaacg Jul 25 '15 at 14:13
  • \$\begingroup\$ Oh no, the program is fine, I just got thrown off by your explanation. I thought you were outputting a fraction. You can revert to the old version, except that you still have to multiply by 100 so you output a percentage. \$\endgroup\$ – orlp Jul 25 '15 at 15:54
2
\$\begingroup\$

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%
\$\endgroup\$
  • \$\begingroup\$ @orlp: done. No worries about the mistake, these things happen :) \$\endgroup\$ – David Miani Jul 24 '15 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.