algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

new-21-game-v3.py (762B)

      1 class Solution:
      2 
      3     def new21Game(self, n: int, k: int, maxPts: int) -> float:
      4         
      5         # while less than k she draws
      6         # stops when she has k or more points
      7         # return probability that alice has n or fewer points
      8 
      9         if k == 0:
     10             return 1
     11 
     12         left = 0
     13         right = 1
     14         csum = 1.0000
     15         jump_prob = 1/maxPts
     16 
     17         probs = [1.000000]
     18 
     19         while right < maxPts + k:
     20 
     21             probs.append(csum * jump_prob)
     22             if len(probs) - 1 < k:
     23                 csum += probs[len(probs) - 1]
     24 
     25             if right - left + 1 > maxPts:
     26                 csum -= probs[left]
     27                 left += 1
     28             
     29             right += 1
     30             
     31         print(probs)
     32         return 1 - sum(probs[n+1:])