def win_series(p, W=0, L=0):
    "Probability of winning best-of-7 series, given a probability p of winning a game."
    return (1 if W == 4 else
            0 if L == 4 else
            p       * win_series(p, W + 1, L) +
            (1 - p) * win_series(p, W, L + 1))

win_series(0.58)

"""
Explanation: WWW: Will the Warriors Win?
18 April 2016
The Golden State Warriors have had a historic basketball season, winning more games than any other team ever has. But will they top that off by winning the championship? There are 15 other teams in contention, including one, the Spurs, that has had a historic season as the best second-best team ever. The web site fivethirtyeight, using a complicated scoring syste, gives the Warriors a 44% chance of winning, with the Spurs at 28%. Basketball-reference has the Warriors at 41% and Spurs at 32.5%, while a betting site had the Warriors at 54% and Spurs at 18%. But what's a good way to make a prediction? There are several choices:

Subjective impression of a team's strength? Or a statistical model?
Predictions based on:
Holistic impression of entire postseason (e.g. "I think the Warriors have a 50% chance of winning it all")
Series by series (e.g. "I think the Warriors have a 95% chance of beating the Rockets in the first round, then ...")
Game by game (e.g. "I think the Warriors have a 83% chance of beating the Rockets in Game 1, then ...")
Possession by possession (e.g. simulate games basket by basket, based on past stats)

Here are the top four teams with their Won-Loss percentage and SRS (Simple rating system: average margin of victory, adjusted for strength of opponents):
 TEAM         PCT    SRS
 Warriors    .890  10.38
 Spurs       .817  10.28
 Thunder     .671   7.09
 Cavaliers   .695   5.45

I decided to go with a subjective impression of one team beating another in a single game. For example, I might think that the Warriors have a 58% chance of beating the Cavaliers in any one game, and from that compute the odds of winning a series:
End of explanation
"""


def percents(items, fmt='{:4.0%}'): return ' '.join(fmt.format(item) for item in items)

def series_table(pcts=[p/100 for p in range(20, 81, 5)]):
    print('W-L | Singe Game Win Percentage')
    print('    | ' + percents(pcts))
    for W in range(4):
        print('----+' + '-' * 5 * len(pcts))
        for L in reversed(range(4)):
            results = [win_series(p, W, L) for p in pcts]
            print('{}-{} | {}'.format(W, L, percents(results)))

series_table()

"""
Explanation: In other words, if you have a 58% chance of winning a game, you have a 67% chance of winning the series.
Note that I ignore the fact that games aren't strictly independent; I ignore home court advantage; and I ignore the chance of catastrophic injuries. Why? Because all these factors would change the final winning estimate by only a few percentage points, and I already have more uncertainty than that.
Note that win_series takes optional arguments to say how many games in the sries have been won and lost so far. Here's a table showing your chance of winning a series, given the current tally of games won and lost on the left, and your expected percentage of winning a game at the top:
End of explanation
"""


def playoffs(name, rounds):
    "Print probability for team winning each series."
    overall = (1, 1, 1) # (lo, med, hi) probabilities of winning it all
    for (opponent, probs) in rounds:
        this_round = [win_series(p) for p in probs]
        overall = [overall[i] * this_round[i] for i in range(len(probs))]
        print('{} vs {:8} win this round: {}; win through here: {}'.format(
               name, opponent, percents(this_round), percents(overall)))

"""
Explanation: And here's a function to tabulate the chances of winning each series on the way to a title:
End of explanation
"""


playoffs('Warriors',
     [('Rockets',  (0.75, 0.83, 0.85)),
      ('Clippers', (0.67, 0.73, 0.80)),
      ('Spurs',    (0.45, 0.58, 0.70)),
      ('Cavs',     (0.60, 0.67, 0.75))])

playoffs('Spurs',
     [('Memphis',  (0.75, 0.83, 0.85)),
      ('Thunder',  (0.45, 0.62, 0.70)),
      ('Warriors', (0.30, 0.42, 0.55)),
      ('Cavs',     (0.60, 0.67, 0.75))])

playoffs('Cavs',
     [('Pistons', (0.75, 0.83, 0.85)),
      ('Hawks',   (0.45, 0.60, 0.75)),
      ('Raptors', (0.40, 0.55, 0.65)),
      ('GSW/SAS', (0.25, 0.33, 0.40))])

"""
Explanation: Now I enter my subjective probability estimates (low, medium, and high), and likely opponents for each round, for the three top contenders:
End of explanation
"""


def playoffs(name, rounds):
    "Print probability for team winning each series."
    overall = (1, 1, 1) # (lo, med, hi) probabilities of winning it all
    for (opponent, probs, *args) in rounds:
        this_round = [win_series(p, *args) for p in probs]
        overall = [overall[i] * this_round[i] for i in range(len(probs))]
        print('{} vs {:8} win this round: ({}) win through here: ({})'.format(
               name, opponent, percents(this_round), percents(overall)))

"""
Explanation: I have the Warriors at 50% (for the medium estimate of winning it all) and the Spurs at 20%, so I'm more of a Warriors fan than fivethirtyeight and basketball-reference, but I have very wide margins between my low and high estimate: 22% to 78% for the Warriors;  3% to 49% for the Spurs; 1% to 21% for the Cavs. Interestingly, while fivethirtyeight does not think this year's Warriors are better than the 1995 Bulls, they do think the Spurs, Thunder, and Cavs are the best ever second-, third-, and fourth-best teams in a season.
What's better--a holistic guess at the outcome, or a reductionist model like this one? I can't say that one is better than the other in every case, but it can be instructive to examine the cases where the reductionist model differs from your holistic impressions. For example, look at the low end of my prediction for the Spurs. I feel like it is crazy to say the Spurs only have a 3% chance of winning the title, but I don't feel that any of the individual game win probabilities (75%, 45%, 30%, and 60%, respectively) are crazy. So now I know that at least one of my intutions is wrong. But I'm not sure how to reconcile the mismatch...
WWWWC: Will Warriors Win Without Curry?
27 April 2016
The Playoff picture has changed! 
We have some results for first-round series, and there have been key injuries to players including Steph Curry, Avery Bradley, Chris Paul, and Blake Griffin. To update, first I make a small alteration to allow the current state of a series in terms of wins/loses to be specified as part of the input to playoffs:
End of explanation
"""


playoffs('Warriors',
     [('Rockets',  (0.50, 0.70, 0.80), 3, 1),
      ('Blazers',  (0.45, 0.55, 0.67)),
      ('Spurs',    (0.30, 0.55, 0.67)),
      ('Cavs',     (0.40, 0.60, 0.70))])

"""
Explanation: We don't know for sure how long Curry will be out, but here are my updated odds for the Warriors, with the middle probability value representing the assumption that Curry misses the second round, and comes back in time for the Western Conference Finals at a mildly reduced capacity; the low and high probability values represent more and less severe injuries:
End of explanation
"""


playoffs('Spurs',
     [('Memphis',  (0.75, 0.83, 0.85), 4, 0),
      ('Thunder',  (0.45, 0.62, 0.70)),
      ('Warriors', (0.33, 0.45, 0.70)),
      ('Cavs',     (0.60, 0.67, 0.75))])

playoffs('Cavs',
     [('Pistons', (0.75, 0.83, 0.85), 4, 0),
      ('Hawks',   (0.45, 0.60, 0.75)),
      ('Raptors', (0.40, 0.55, 0.65)),
      ('GSW/SAS', (0.30, 0.40, 0.60))])

"""
Explanation: The Spurs and Cavs are rolling; let's update their odds:
End of explanation
"""


playoffs('Warriors',
     [('Rockets',  (0.50, 0.70, 0.80), 4, 1),
      ('Blazers',  (0.55, 0.67, 0.75), 3, 1),
      ('Spurs',    (0.45, 0.60, 0.67)),
      ('Cavs',     (0.40, 0.55, 0.67))])

playoffs('Spurs',
     [('Memphis',  (0.75, 0.83, 0.85), 4, 0),
      ('Thunder',  (0.40, 0.60, 0.70), 2, 3),
      ('Warriors', (0.33, 0.40, 0.55)),
      ('Cavs',     (0.40, 0.50, 0.70))])

playoffs('Thunder',
     [('Dallas',   (0.75, 0.83, 0.85), 4, 1),
      ('Spurs',    (0.30, 0.40, 0.60), 3, 2),
      ('Warriors', (0.33, 0.40, 0.55)),
      ('Cavs',     (0.35, 0.45, 0.60))])

playoffs('Cavs',
     [('Pistons',  (0.75, 0.83, 0.85), 4, 0),
      ('Hawks',    (0.45, 0.60, 0.75), 4, 0),
      ('Raptors',  (0.50, 0.65, 0.75)),
      ('GS/SA/OK', (0.33, 0.45, 0.55))])

"""
Explanation: So my updated odds are that the Warriors and Spurs are roughly equally likely to win (26% and 24%); the Cavs are still less likely (13%), and there is more uncertainty.
WWWWCB: Will Warriors Win With Curry Back?
10 May 2016
Curry has returned from his injury, and after a slow shooting start, had the highest-scoring overtime period in the history of the NBA. Meanwhile, the Thunder lead the Spurs, 3-2, and the Cavaliers have been dominant in the East, hitting a historic number of 3-point shots. Here is my revised outlook:
End of explanation
"""


playoffs('Warriors',
     [('Rockets',  (0.50, 0.70, 0.80), 4, 1),
      ('Blazers',  (0.55, 0.67, 0.75), 4, 1),
      ('Thunder',  (0.45, 0.63, 0.70), 0, 1),
      ('Cavs',     (0.40, 0.55, 0.65))])

"""
Explanation: So overall, from the start of the playoffs up to May 10th, I have:

Warriors: Dropped from 50% to 26% with Curry's injury, and rebounded to 42%. 
Spurs: Dropped from 20% to 5% after falling behind Thunder.
Thunder: Increased to 7%.
Cavs: Increased to 31%.

Time to Panic?
17 May 2016
The Thunder finished off the Spurs and beat the Warriors in game 1. Are the Thunder, like the Cavs, peaking at just the right time, after an inconsistant regular season? Is it time for Warriors fans to panic?
Sure, the Warriors were down a game twice in last year's playoffs and came back to win both times. Sure, the Warriors are still 3-1 against the Thunder this year, and only lost two games all season to elite teams (Spurs, Thunder, Cavs, Clippers, Raptors). But the Thunder are playing at a top level. Here's my update, showing that the loss cost the Warriors 5%:
End of explanation
"""


playoffs('Warriors',
     [('Rockets',  (0.50, 0.70, 0.80), 4, 1),
      ('Blazers',  (0.55, 0.67, 0.75), 4, 1),
      ('Thunder',  (0.45, 0.63, 0.70), 1, 1),
      ('Cavs',     (0.40, 0.55, 0.65))])

playoffs('Cavs',
     [('Pistons',  (0.75, 0.83, 0.85), 4, 0),
      ('Hawks',    (0.45, 0.60, 0.75), 4, 0),
      ('Raptors',  (0.50, 0.65, 0.75), 1, 0),
      ('GSW',      (0.35, 0.45, 0.60))])

"""
Explanation: Not Yet?
18 May 2016
The Warriors won game two of the series, so now they're back up to 45%, with the Cavs at 35%. At this time, fivethirtyeight has the Warriors at 45%, Cavs at 28% and Thunder at 24%
End of explanation
"""


playoffs('Warriors',
     [('Rockets',  (0.50, 0.70, 0.80), 4, 1),
      ('Blazers',  (0.55, 0.67, 0.75), 4, 1),
      ('Thunder',  (0.25, 0.55, 0.65), 1, 3),
      ('Cavs',     (0.40, 0.55, 0.65))])

playoffs('Cavs',
     [('Pistons',  (0.75, 0.83, 0.85), 4, 0),
      ('Hawks',    (0.45, 0.60, 0.75), 4, 0),
      ('Raptors',  (0.50, 0.55, 0.70), 2, 2),
      ('Thunder',  (0.35, 0.45, 0.60))])

playoffs('Thunder',
     [('Dallas',   (0.75, 0.83, 0.85), 4, 1),
      ('Spurs',    (0.30, 0.40, 0.60), 4, 2),
      ('Warriors', (0.35, 0.45, 0.75), 3, 1),
      ('Cavs',     (0.40, 0.55, 0.65))])

"""
Explanation: Yet!
24 May 2016
The Thunder won two in a row (first time the Warriors had lost two in a row all year), putting the Warriors down 3-1. And the Cavs are looking mortal, losing two to the Raptors. So now it looks to me like the Thunder are favorites to win it all:
End of explanation
"""


playoffs('Warriors',
     [('Rockets',  (0.50, 0.70, 0.80), 4, 1),
      ('Blazers',  (0.55, 0.67, 0.75), 4, 1),
      ('Thunder',  (0.35, 0.55, 0.65), 2, 3),
      ('Cavs',     (0.40, 0.55, 0.65))])

playoffs('Cavs',
     [('Pistons',  (0.75, 0.83, 0.85), 4, 0),
      ('Hawks',    (0.45, 0.60, 0.75), 4, 0),
      ('Raptors',  (0.50, 0.55, 0.70), 3, 2),
      ('Thunder',  (0.35, 0.45, 0.60))])

playoffs('Thunder',
     [('Dallas',   (0.75, 0.83, 0.85), 4, 1),
      ('Spurs',    (0.30, 0.40, 0.60), 4, 2),
      ('Warriors', (0.35, 0.45, 0.75), 3, 2),
      ('Cavs',     (0.40, 0.55, 0.65))])

"""
Explanation: But Not Done Yet
26 May 2016
The Warriors won game 5, bringing them up from a 10% to an 18% chance of winning it all:
End of explanation
"""


series_table()

"""
Explanation: The Finals
1 June 2016
The Warriors completed their comeback against the Thunder, putting them in a great position to win this year (and they are already established as favorites for next year). Rather than update the odds after each game 0f the finals, I'll just repeat the table (with the note that I think the Warriors are somewhere in the 60% range for each game):
End of explanation
"""


