Weekly Challenge: Absolute Champion

Weekly Challenge 343

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Zero Friend

Task

You are given a list of numbers.

Find the number that is closest to zero and return its distance to zero.

My solution

This is relatively straight forward, and does not require much explanation. As we are dealing with numbers (which may not be a whole number), I use the decimal module.

The solution can be found by taking the minimum of the absolute values of the inputs.

from decimal import Decimal

def zero_friend(numbers: list) -> Decimal:
    return min(abs(n) for n in numbers)

Examples

$ ./ch-1.py 4 2 -1 3 -2
1

$ ./ch-1.py -5 5 -3 3 -1 1
1

$ ./ch-1.py 7 -3 0 2 -8
0

$ ./ch-1.py -2 -5 -1 -8
1

$ ./ch-1.py -2 2 -4 4 -1 1
1

All the example dealt with integers. This example checks non-integers too.

$ ./ch-1.py 1.2 2 4 -5
1.2

Task 2: Champion Team

Task

You have n teams in a tournament. A matrix grid tells you which team is stronger between any two teams:

• If grid[i][j] == 1, then team i is stronger than team j.
• If grid[i][j] == 0, then team j is stronger than team i.

Find the champion team - the one with most wins, or if there is no single such team, the strongest of the teams with most wins. (You may assume that there is a definite answer.)

My solution

For input from the command line, I take a JSON formatted string and convert it to a list of lists.

This solution can be broken up to three parts. The first part is validation of the input. I check:

• The matrix is square (each row is the same length as the number of teams)
• Each value in the matrix is either 0 or 1.
• A team doesn't win against itself.

def champion_team(matrix: list[list[int]], consider_teams: list[int]|None = None) -> str:
    size = len(matrix)
    if any(len(row) != size for row in matrix):
        raise ValueError("Matrix must be square")

    if any(matrix[i][j] not in (0, 1) for i in range(size) for j in range(size)):
        raise ValueError("Matrix must only contain 0s and 1s")

    if any(matrix[i][i] != 0 for i in range(size)):
        raise ValueError("A team cannot win against itself")

The next step is to calculate the scores for each team. The first time this is called (more about that later), I calculate the score of all results. The teams I am calculating is stored as the consider_teams list. The max_wins variable is set to -1 and winning_teams is an empty list. At the end of this section, the winning_teams variable will have the teams with the highest score.

    # Consider all teams by default
    if consider_teams is None:
        consider_teams = list(range(len(matrix)))

    max_wins = -1
    winning_teams = []

    for team_index, results in enumerate(matrix):
        if team_index not in consider_teams:
            continue

        wins = sum(results[i] for i in consider_teams)

        if wins > max_wins:
            max_wins = wins
            winning_teams = [team_index]
        elif wins == max_wins:
            winning_teams.append(team_index)

The final part is to decide what to do with this list.

• If there is only one winner, return that value.
• If the length of the winning_teams list is the same as the length of the consider_teams list, then there is a tie that cannot be resolved.
• In all other cases, I call the function again, setting the consider_teams to the current winning_teams variable. In this run, I will only consider the scores between these teams when calculating the new winning_teams list.

    if len(winning_teams) == 1:
        return f"Team {winning_teams[0]}"

    if len(winning_teams) == len(consider_teams):
        return "No champion"

    return champion_team(matrix, consider_teams=winning_teams)

Examples

$ ./ch-2.py "[[0, 1, 1], [0, 0, 1], [0, 0, 0]]"
Team 0

$ ./ch-2.py "[[0, 1, 0, 0], [0, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 0]]"
Team 3

$ ./ch-2.py "[[0, 1, 0, 1], [0, 0, 1, 1], [1, 0, 0, 0], [0, 0, 1, 0]]"
Team 0

$ ./ch-2.py "[[0, 1, 1], [0, 0, 0], [0, 1, 0]]"
Team 0

$ ./ch-2.py "[[0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1], [1, 1, 0, 0, 0], [1, 1, 0, 1, 0]]"
Team 2

This is the same as the third example, but swaps Teams 0 and Teams 1 around. This is to ensure that the tie breaker (second recursion) works.

$ ./ch-2.py "[[0, 0, 1, 1], [1, 0, 0, 1], [0, 1, 0, 0], [0, 0, 1, 0]]"
Team 1

The last example shows what happens if there is a three or more way tie. This should not happens, as the task makes an assumption that there is a definite winner. I'm making an assumption this might not be the case :)

$ ./ch-2.py "[[0, 1, 0, 1], [0, 0, 1, 1], [1, 0, 0, 1], [0, 0, 0, 0]]"
No champion