Problem

This module contains the Problem, Instance, Solution, and other related classes and thus the interface you can use to provide your own problems.

algobattle.problem.Problem

The definition of a problem.

Source code in algobattle/problem.py

class Problem:
    """The definition of a problem."""

    @overload
    def __init__(  # noqa: D107
        self,
        *,
        name: str,
        instance_cls: type[InstanceT],
        solution_cls: type[SolutionT],
        min_size: int = 0,
        with_solution: Literal[True] = True,
        score_function: ScoreFunctionWithSol[InstanceT, SolutionT] = default_score,
        test_instance: InstanceT | None = None,
    ) -> None:
        ...

    @overload
    def __init__(  # noqa: D107
        self,
        *,
        name: str,
        instance_cls: type[InstanceT],
        solution_cls: type[SolutionT],
        min_size: int = 0,
        with_solution: Literal[False],
        score_function: ScoreFunctionNoSol[InstanceT, SolutionT] = default_score,
        test_instance: InstanceT | None = None,
    ) -> None:
        ...

    def __init__(
        self,
        *,
        name: str,
        instance_cls: type[InstanceT],
        solution_cls: type[SolutionT],
        min_size: int = 0,
        with_solution: bool = True,
        score_function: ScoreFunction[InstanceT, SolutionT] = default_score,
        test_instance: InstanceT | None = None,
    ) -> None:
        """The definition of a problem.

        Args:
            name: The name of the problem.
            instance_cls: Class defining what instances of this problem look like.
            solution_cls: Class definitng what solutions of this problem look like.
            min_size: Minimum size of valid instances of this problem.
            with_solution: Whether the generator should also create a solution.
            score_function: Function used to score how well a solution solves a problem instance.

                The default scoring function returns the quotient of the solver's to the generator's solution score.

                The score function always takes the instance as the first argument. If `with_solution` is set it then
                gets the generated solutions at `generator_solution` and `solver_solution`. If it is not set it receives
                the solver's solution at `solution`. It should return the calculated score, a number in [0, 1] with a
                value of 0 indicating that the solver failed completely and 1 that it solved the instance perfectly.
            test_instance: A dummy instance that can be used to test whether a solver produces correct output.
        """
        self.name = name
        self.instance_cls = instance_cls
        self.solution_cls = solution_cls
        self.min_size = min_size
        self.with_solution = with_solution
        self.score_function = score_function
        self.test_instance = test_instance
        self._problems[name] = self

    __slots__ = ("name", "instance_cls", "solution_cls", "min_size", "with_solution", "score_function", "test_instance")
    _problems: ClassVar[dict[str, Self]] = {}

    @overload
    def score(self, instance: InstanceT, *, solution: Solution[InstanceT]) -> float:
        ...

    @overload
    def score(
        self, instance: InstanceT, *, generator_solution: Solution[InstanceT], solver_solution: Solution[InstanceT]
    ) -> float:
        ...

    def score(
        self,
        instance: Instance,
        *,
        solution: SolutionT | None = None,
        generator_solution: SolutionT | None = None,
        solver_solution: SolutionT | None = None,
    ) -> float:
        """Helper function to call self.score_function with easier to use overloads."""
        if self.with_solution:
            if not (
                isinstance(instance, self.instance_cls)
                and isinstance(generator_solution, self.solution_cls)
                and isinstance(solver_solution, self.solution_cls)
                and solution is None
            ):
                raise TypeError
            if TYPE_CHECKING:
                assert isinstance(self.score_function, ScoreFunctionWithSol)
            return self.score_function(instance, generator_solution=generator_solution, solver_solution=solver_solution)
        else:
            if not (
                isinstance(instance, self.instance_cls)
                and isinstance(solution, self.solution_cls)
                and generator_solution is None
                and solver_solution is None
            ):
                raise TypeError
            if TYPE_CHECKING:
                assert isinstance(self.score_function, ScoreFunctionNoSol)
            return self.score_function(instance, solution=solution)

    @classmethod
    def load_file(cls, name: str, file: Path) -> Self:
        """Loads the problem from the specified file."""
        existing_problems = cls._problems.copy()
        cls._problems = {}
        try:
            import_file_as_module(file, "__algobattle_problem__")
            if name not in cls._problems:
                raise ValueError(f"The {name} problem is not defined in {file}")
            else:
                return cls._problems[name]
        finally:
            cls._problems = existing_problems

    @classmethod
    def load(cls, name: str, file: Path | None = None) -> Self:
        """Loads the problem with the given name.

        Args:
            name: The name of the Problem to use.
            file: Path to a file containing this problem.

        Raises:
            ValueError: If the problem is not specified properly
            RuntimeError: If the problem's dynamic import fails
        """
        if file:
            return cls.load_file(name, file)
        if name in cls._problems:
            return cls._problems[name]
        match list(entry_points(group="algobattle.problem", name=name)):
            case []:
                raise ValueError("Problem name is not valid.")
            case [e]:
                loaded: object = e.load()
                if not isinstance(loaded, cls):
                    raise ValueError(
                        f"The entrypoint '{name}' doesn't point to a problem but a {loaded.__class__.__qualname__}."
                    )
                return loaded
            case entypoints:
                raise ValueError(
                    f"Multiple problem entrypoints with the name {name} exist!"
                    f" The modules providing them are: {', '.join(e.module for e in entypoints)}."
                )

    @classmethod
    def available(cls) -> set[str]:
        """Returns the names of all available Problems."""
        return set(chain(cls._problems.keys(), (e.name for e in entry_points(group="algobattle.problem"))))

__init__(*, name, instance_cls, solution_cls, min_size=0, with_solution=True, score_function=default_score, test_instance=None)

The definition of a problem.

Parameters:

Name	Type	Description	Default
name	str	The name of the problem.	required
instance_cls	type[InstanceT]	Class defining what instances of this problem look like.	required
solution_cls	type[SolutionT]	Class definitng what solutions of this problem look like.	required
min_size	int	Minimum size of valid instances of this problem.	0
with_solution	bool	Whether the generator should also create a solution.	True
score_function	ScoreFunction[InstanceT, SolutionT]	Function used to score how well a solution solves a problem instance. The default scoring function returns the quotient of the solver's to the generator's solution score. The score function always takes the instance as the first argument. If with_solution is set it then gets the generated solutions at generator_solution and solver_solution. If it is not set it receives the solver's solution at solution. It should return the calculated score, a number in [0, 1] with a value of 0 indicating that the solver failed completely and 1 that it solved the instance perfectly.	default_score
test_instance	InstanceT | None	A dummy instance that can be used to test whether a solver produces correct output.	None

Source code in algobattle/problem.py

def __init__(
    self,
    *,
    name: str,
    instance_cls: type[InstanceT],
    solution_cls: type[SolutionT],
    min_size: int = 0,
    with_solution: bool = True,
    score_function: ScoreFunction[InstanceT, SolutionT] = default_score,
    test_instance: InstanceT | None = None,
) -> None:
    """The definition of a problem.

    Args:
        name: The name of the problem.
        instance_cls: Class defining what instances of this problem look like.
        solution_cls: Class definitng what solutions of this problem look like.
        min_size: Minimum size of valid instances of this problem.
        with_solution: Whether the generator should also create a solution.
        score_function: Function used to score how well a solution solves a problem instance.

            The default scoring function returns the quotient of the solver's to the generator's solution score.

            The score function always takes the instance as the first argument. If `with_solution` is set it then
            gets the generated solutions at `generator_solution` and `solver_solution`. If it is not set it receives
            the solver's solution at `solution`. It should return the calculated score, a number in [0, 1] with a
            value of 0 indicating that the solver failed completely and 1 that it solved the instance perfectly.
        test_instance: A dummy instance that can be used to test whether a solver produces correct output.
    """
    self.name = name
    self.instance_cls = instance_cls
    self.solution_cls = solution_cls
    self.min_size = min_size
    self.with_solution = with_solution
    self.score_function = score_function
    self.test_instance = test_instance
    self._problems[name] = self

score(instance, *, solution=None, generator_solution=None, solver_solution=None)

Helper function to call self.score_function with easier to use overloads.

Source code in algobattle/problem.py

def score(
    self,
    instance: Instance,
    *,
    solution: SolutionT | None = None,
    generator_solution: SolutionT | None = None,
    solver_solution: SolutionT | None = None,
) -> float:
    """Helper function to call self.score_function with easier to use overloads."""
    if self.with_solution:
        if not (
            isinstance(instance, self.instance_cls)
            and isinstance(generator_solution, self.solution_cls)
            and isinstance(solver_solution, self.solution_cls)
            and solution is None
        ):
            raise TypeError
        if TYPE_CHECKING:
            assert isinstance(self.score_function, ScoreFunctionWithSol)
        return self.score_function(instance, generator_solution=generator_solution, solver_solution=solver_solution)
    else:
        if not (
            isinstance(instance, self.instance_cls)
            and isinstance(solution, self.solution_cls)
            and generator_solution is None
            and solver_solution is None
        ):
            raise TypeError
        if TYPE_CHECKING:
            assert isinstance(self.score_function, ScoreFunctionNoSol)
        return self.score_function(instance, solution=solution)

load_file(name, file) classmethod

Loads the problem from the specified file.

Source code in algobattle/problem.py

@classmethod
def load_file(cls, name: str, file: Path) -> Self:
    """Loads the problem from the specified file."""
    existing_problems = cls._problems.copy()
    cls._problems = {}
    try:
        import_file_as_module(file, "__algobattle_problem__")
        if name not in cls._problems:
            raise ValueError(f"The {name} problem is not defined in {file}")
        else:
            return cls._problems[name]
    finally:
        cls._problems = existing_problems

load(name, file=None) classmethod

Loads the problem with the given name.

Parameters:

Name	Type	Description	Default
name	str	The name of the Problem to use.	required
file	Path | None	Path to a file containing this problem.	None

Raises:

Type	Description
ValueError	If the problem is not specified properly
RuntimeError	If the problem's dynamic import fails

Source code in algobattle/problem.py

@classmethod
def load(cls, name: str, file: Path | None = None) -> Self:
    """Loads the problem with the given name.

    Args:
        name: The name of the Problem to use.
        file: Path to a file containing this problem.

    Raises:
        ValueError: If the problem is not specified properly
        RuntimeError: If the problem's dynamic import fails
    """
    if file:
        return cls.load_file(name, file)
    if name in cls._problems:
        return cls._problems[name]
    match list(entry_points(group="algobattle.problem", name=name)):
        case []:
            raise ValueError("Problem name is not valid.")
        case [e]:
            loaded: object = e.load()
            if not isinstance(loaded, cls):
                raise ValueError(
                    f"The entrypoint '{name}' doesn't point to a problem but a {loaded.__class__.__qualname__}."
                )
            return loaded
        case entypoints:
            raise ValueError(
                f"Multiple problem entrypoints with the name {name} exist!"
                f" The modules providing them are: {', '.join(e.module for e in entypoints)}."
            )

available() classmethod

Returns the names of all available Problems.

Source code in algobattle/problem.py

@classmethod
def available(cls) -> set[str]:
    """Returns the names of all available Problems."""
    return set(chain(cls._problems.keys(), (e.name for e in entry_points(group="algobattle.problem"))))

algobattle.problem.Instance

Bases: Encodable, ABC

Instance base class.

Source code in algobattle/problem.py

class Instance(Encodable, ABC):
    """Instance base class."""

    @property
    @abstractmethod
    def size(self) -> int:
        """The instance's size."""
        raise NotImplementedError

    def validate_instance(self) -> None:
        """Confirms that the parsed instance is valid.

        Should be idempotent, but may also perform additional postprocessing such as bringing the instance
        into a normal form.

        Raises:
            ValidationError: if the created instance is invalid.
        """
        return

size: int abstractmethod property

The instance's size.

validate_instance()

Confirms that the parsed instance is valid.

Should be idempotent, but may also perform additional postprocessing such as bringing the instance into a normal form.

Raises:

Type	Description
ValidationError	if the created instance is invalid.

Source code in algobattle/problem.py

def validate_instance(self) -> None:
    """Confirms that the parsed instance is valid.

    Should be idempotent, but may also perform additional postprocessing such as bringing the instance
    into a normal form.

    Raises:
        ValidationError: if the created instance is invalid.
    """
    return

algobattle.problem.Solution

Bases: EncodableBase, Generic[InstanceT], ABC

A proposed solution for an instance of this problem.

Source code in algobattle/problem.py

class Solution(EncodableBase, Generic[InstanceT], ABC):
    """A proposed solution for an instance of this problem."""

    @classmethod
    @abstractmethod
    def decode(cls, source: Path, max_size: int, role: Role, instance: InstanceT) -> Self:  # noqa: D102
        raise NotImplementedError

    def validate_solution(self, instance: InstanceT, role: Role) -> None:
        """Confirms that the parsed solution is valid.

        Should be idempotent, but may also perform additional postprocessing such as bringing the solution
        into a normal form.

        Args:
            instance: The problem instance this solution is purported to solve.
            role: The role of the team that generated this solution.

        Raises:
            ValidationError: if the created instance is invalid.
        """
        return

    def score(self, instance: InstanceT, role: Role) -> float:
        """Calculate the score of this solution for the given problem instance.

        The default implementation always returns 1, indicating that all solutions of this problem are equally good.

        Args:
            instance: The instance this solution solves
            role: The role of the team that generated this solution
        Returns:
            The calculates score of this solution. Must be a nonnegative number. Bigger scores are considered better,
            if your score rates better scores lower you can use the @minimize decorator.
        """
        return 1

validate_solution(instance, role)

Confirms that the parsed solution is valid.

Should be idempotent, but may also perform additional postprocessing such as bringing the solution into a normal form.

Parameters:

Name	Type	Description	Default
instance	InstanceT	The problem instance this solution is purported to solve.	required
role	Role	The role of the team that generated this solution.	required

Raises:

Type	Description
ValidationError	if the created instance is invalid.

Source code in algobattle/problem.py

def validate_solution(self, instance: InstanceT, role: Role) -> None:
    """Confirms that the parsed solution is valid.

    Should be idempotent, but may also perform additional postprocessing such as bringing the solution
    into a normal form.

    Args:
        instance: The problem instance this solution is purported to solve.
        role: The role of the team that generated this solution.

    Raises:
        ValidationError: if the created instance is invalid.
    """
    return

score(instance, role)

Calculate the score of this solution for the given problem instance.

The default implementation always returns 1, indicating that all solutions of this problem are equally good.

Parameters:

Name	Type	Description	Default
instance	InstanceT	The instance this solution solves	required
role	Role	The role of the team that generated this solution	required

Returns: The calculates score of this solution. Must be a nonnegative number. Bigger scores are considered better, if your score rates better scores lower you can use the @minimize decorator.

Source code in algobattle/problem.py

def score(self, instance: InstanceT, role: Role) -> float:
    """Calculate the score of this solution for the given problem instance.

    The default implementation always returns 1, indicating that all solutions of this problem are equally good.

    Args:
        instance: The instance this solution solves
        role: The role of the team that generated this solution
    Returns:
        The calculates score of this solution. Must be a nonnegative number. Bigger scores are considered better,
        if your score rates better scores lower you can use the @minimize decorator.
    """
    return 1

algobattle.problem.InstanceModel

Bases: InstanceSolutionModel, EncodableModel, Instance, ABC

An instance that can easily be parsed to/from a json file.

Source code in algobattle/problem.py

class InstanceModel(InstanceSolutionModel, EncodableModel, Instance, ABC):
    """An instance that can easily be parsed to/from a json file."""

    pass

algobattle.problem.SolutionModel

Bases: InstanceSolutionModel, Solution[InstanceT], ABC

A solution that can easily be parsed to/from a json file.

Source code in algobattle/problem.py

class SolutionModel(InstanceSolutionModel, Solution[InstanceT], ABC):
    """A solution that can easily be parsed to/from a json file."""

    @classmethod
    def decode(cls, source: Path, max_size: int, role: Role, instance: InstanceT) -> Self:
        """Uses pydantic to create a python object from a `.json` file."""
        context: dict[str, Any] = {"max_size": max_size, "role": role, "instance": instance}
        return cls._decode(cls, source, **context)

decode(source, max_size, role, instance) classmethod

Uses pydantic to create a python object from a .json file.

Source code in algobattle/problem.py

@classmethod
def decode(cls, source: Path, max_size: int, role: Role, instance: InstanceT) -> Self:
    """Uses pydantic to create a python object from a `.json` file."""
    context: dict[str, Any] = {"max_size": max_size, "role": role, "instance": instance}
    return cls._decode(cls, source, **context)