Five Players

README.md

The problem can be solved using discrete Fourier transform (DFT).

Rewriting the problem as a matrix equation Cx = b, we noticed that the coefficient matrix C is a circulant square matrix. The equation can then be rewriten as the circular convolution of c and x.

By circular convolution theorem, the point-wise product of the DFT of c and that of x is the DFT of b. We can compute x from the point-wise quotient. (Wikipedia)

1. We compute x.
2. We iterate x to find the youngest player.

The running time of this algorithm is bounded by DFT. When using DFT, we can achieve O(n^2). If we use fast Fourier transform, the upper bound can be reduced to O(n log n).

five_players.py

"""
five_players.py
"""

import cmath
import math

def conjugate(number):
    """
    conjugate takes a complex number number.
    conjugate returns its conjugate.
    """

    return complex(number.real, -number.imag)

def dft(sequence):
    """
    dft takes a iterable of complex numbers sequence.
    dft returns its discrete Fourier transform.
    """

    results = []

    for index_k in range(len(sequence)):
        result = complex(0, 0)
        for index_n, value in enumerate(sequence):
            result += value * cmath.exp(
                - 1j * 2 * cmath.pi * index_k * index_n / len(sequence)
            )
        results.append(result)

    return results

def idft(sequence):
    """
    idft takes a iterable of complex numbers sequence.
    idft returns its inverse DFT using conjugate trick
    """

    sequence_inverse = [conjugate(item) for item in sequence]

    result = [conjugate(item) / len(sequence) for item in dft(sequence_inverse)]

    return result

def solve_circulant(vector, constant, rounding=0):
    """
    solve_circulant takes a iterable vector, a iterable constant and a int
        rounding.
    solve_circulant returns the solution to system Cx = b rounded up to the
        digit set by rounding.
    C is a circulant matrix made up by vector.
    b is the vector constant.
    """

    results = idft(
        [
            item_b / item_c
            for item_b, item_c in zip(dft(constant), dft(vector))
        ]
    )

    results = [
        complex(
            round(result.real, rounding),
            round(result.imag, rounding)
        )
        for result in results
    ]

    return results

def find_youngest_player(ages):
    """
    find_youngest_player takes a iterable of sums of ages during double matchs
        ages.
    find_youngest_player returns the age of the youngest player.
    """

    vector = [1 for _ in range(len(ages))]

    vector[-1] = 0

    ages = solve_circulant(vector, ages)

    youngest = math.inf

    for age in ages:
        if age.real < youngest:
            youngest = age.real

    return youngest