from typing import List, Tuple


class Cell:
    def __init__(self, pay1, pay2):
        self.pay1 = pay1
        self.pay2 = pay2


class Game:
    def __init__(self, p1: List[str], p2: List[str], payoffs: List[List[Cell]]) -> None:
        """
        p1: list of strategies for player 1
        p2: list of strategies for player 2
        payoffs: list of lists of Cells, representing the payoff matrix

        Example game:
              A     B
          |-----|-----|
        X | 1,2 | 2,1 |
          |-----|-----|
        Y | 3,3 | 4,4 |
          |-----|-----|

        p1 = ["X", "Y"]
        p2 = ["A", "B"]
        payoffs = [
            [Cell(1, 2), Cell(2, 1)],
            [Cell(3, 3), Cell(4, 4)]
        ]
        """

        # validate that this is a proper payoff matrix
        assert len(p1) == len(payoffs)
        assert len(p2) == len(payoffs[0])
        assert all(len(row) == len(p2) for row in payoffs)

        self.p1 = p1
        self.p2 = p2
        self.payoffs = payoffs

    def does_dominate(self, s1: str, s2: str, p: int, weak: bool = False) -> bool:
        assert p in [0, 1], "invalid player index"
        if p == 0:
            assert s1 in self.p1 and s2 in self.p1, "invalid strategy"
        else:
            assert s1 in self.p2 and s2 in self.p2, "invalid strategy"

        s1_index = self.p1.index(s1) if p == 0 else self.p2.index(s1)
        s2_index = self.p1.index(s2) if p == 0 else self.p2.index(s2)

        domination = True
        strict_found = False

        for i in range(len(self.payoffs)):
            if p == 0:
                payoff_s1 = self.payoffs[s1_index][i].pay1
                payoff_s2 = self.payoffs[s2_index][i].pay1
            else:
                payoff_s1 = self.payoffs[i][s1_index].pay2
                payoff_s2 = self.payoffs[i][s2_index].pay2

            if weak:
                if payoff_s1 < payoff_s2:
                    domination = False
                    break
                elif payoff_s1 > payoff_s2:
                    strict_found = True
            else:
                if payoff_s1 <= payoff_s2:
                    domination = False
                    break

        if weak:
            return domination and strict_found
        else:
            return domination

    def best_response(self, s: str, p: int) -> List[str]:
        """
        Returns the best response(s) for player p to strategy s
        made by the other player.
        Can be multiple in the case of two or more equally good responses.
        """
        assert p in [0, 1], "invalid player index"
        if p == 0:
            assert s in self.p2, "invalid strategy for player 2"
            s_index = self.p2.index(s)
            best_payoff = float('-inf')
            best_response = None
            for i, strategy in enumerate(self.p1):
                payoff = self.payoffs[i][s_index].pay1
                if payoff > best_payoff:
                    best_payoff = payoff
                    best_response = [strategy]
                elif payoff == best_payoff:
                    assert best_response is not None
                    best_response.append(strategy)
        else:
            assert s in self.p1, "invalid strategy for player 1"
            s_index = self.p1.index(s)
            best_payoff = float('-inf')
            best_response = None
            for i, strategy in enumerate(self.p2):
                payoff = self.payoffs[s_index][i].pay2
                if payoff > best_payoff:
                    best_payoff = payoff
                    best_response = [strategy]
                elif payoff == best_payoff:
                    assert best_response is not None
                    best_response.append(strategy)

        return best_response if best_response is not None else []

    def nash_equilibriums(self) -> List[Tuple[str, str]]:
        """
        Returns a list of Nash equilibriums.
        """
        s1_brs = {s: self.best_response(s, 0) for s in self.p2}
        s2_brs = {s: self.best_response(s, 1) for s in self.p1}

        nash_equilibriums = []
        for s1, brs in s1_brs.items():
            for s2 in brs:
                if s1 in s2_brs[s2]:
                    nash_equilibriums.append((s2, s1))

        return nash_equilibriums