Wednesday, March 23, 2016

Single Elimination Tournament Possibility Problem


This is a real Google onsite interview question.

Problem

Give you a winning rates matrix for each team vs each team, an initial sequence of rivals and a team index, then compute the possibility that this team could be the champion of the whole tournament. The team number would be 2^n.

For example, we have a 4 teams. [0, 1, 2, 3], we have a winning rate matrix:
      x   0.7   0.6   0.5
    0.3     x   0.1   0.2
    0.4   0.9     x   0.4
    0.5   0.8   0.6     x
Solution

Because a team itself will never match itself, so the diagonal of the matrix will not be used.



As the graph shows above, if team 1 wants to be the champion, they need to first beat team 0 and then beat team 3 or team 4. So in this 4 teams scenario, the possibility of team 1 finally win is:

The number on the lower right corner means the winning team and the failed team. P23 means the possibility team 2 beats team 3.

From the formula, we could see that for any round(final, semifinal etc.), for the half that contains the team we specified to be the champion, we just need the possibility that the team make here. But for the other half doesn't contain the specified team, we need all possibilities that any team in this part could make here. Then just compute the possibility as formula shows above.

Because in any round, the scenario is the same. We could use recursion to simplify our computation. The base condition is that we there are just two teams, just return the possibility that specified team beats the other one.

Below is the Python code to solve this question and some test cases.


def single_elimination(poss, matches, num):
    """
    poss: possibility matrix
    matches: intial team index
    num: wanted champion index
    rtype: float
    """

    # base case: when two teams available
    if len(matches) == 2:
        if num == matches[0]:
            return poss[matches[0]][matches[1]]
        else:
            return poss[matches[1]][matches[0]]
    half = len(matches) / 2
    # parts contains the specified team as east, the other part as west
    east = matches[:half] if num in matches[:half] else matches[half:]
    west = matches[half:] if num not in matches[half:] else matches[:half]

    # for the half that contains wanted team
    main = single_elimination(poss, east, num)
    # for the half that doesn't contains wanted team
    sub = [single_elimination(poss, west, team) for team in west]
    # p is the possibility that a team made there,
    # t is other teams index. 
    return sum([p * main * poss[num][t] for p, t in zip(sub, west)])

matrix2 = [
    [0.0, 0.9],
    [0.1, 0.0]
]

matches2 = [0, 1]

matrix4 = [
    [0.0, 0.1, 0.2, 0.3],
    [0.9, 0.0, 0.4, 0.5],
    [0.8, 0.6, 0.0, 0.6],
    [0.7, 0.5, 0.4, 0.0]
]

matches4 = [0, 1, 2, 3, ]
print(single_elimination(matrix2, matches2, 0))
print(single_elimination(matrix2, matches2, 1))


print(single_elimination(matrix4, matches4, 0))
print(single_elimination(matrix4, matches4, 1))
print(single_elimination(matrix4, matches4, 2))
print(single_elimination(matrix4, matches4, 3))