josephus_problem.py

"""
The Josephus problem is a famous theoretical problem related to a certain
counting-out game. This module provides functions to solve the Josephus problem
for num_people and a step_size.

The Josephus problem is defined as follows:
- num_people are standing in a circle.
- Starting with a specified person, you count around the circle,
  skipping a fixed number of people (step_size).
- The person at which you stop counting is eliminated from the circle.
- The counting continues until only one person remains.

For more information about the Josephus problem, refer to:
https://en.wikipedia.org/wiki/Josephus_problem
"""


def josephus_recursive(num_people: int, step_size: int) -> int:
    """
    Solve the Josephus problem for num_people and a step_size recursively.

    Args:
        num_people (int): Number of people.
        step_size (int): Step size for elimination.

    Returns:
        int: The position of the last person remaining.

    Examples:
        >>> josephus_recursive(7, 3)
        3
        >>> josephus_recursive(10, 2)
        4
    """
    if num_people == 1:
        return 0

    return (josephus_recursive(num_people - 1, step_size) + step_size) % num_people


def find_winner(num_people: int, step_size: int) -> int:
    """
    Find the winner of the Josephus problem for num_people and a step_size.

    Args:
        num_people (int): Number of people.
        step_size (int): Step size for elimination.

    Returns:
        int: The position of the last person remaining (1-based index).

    Examples:
        >>> find_winner(7, 3)
        4
        >>> find_winner(10, 2)
        5
    """
    return josephus_recursive(num_people, step_size) + 1


def josephus_iterative(num_people: int, step_size: int) -> int:
    """
    Solve the Josephus problem for num_people and a step_size iteratively.

    Args:
        num_people (int): The number of people in the circle.
        step_size (int): The number of steps to take before eliminating someone.

    Returns:
        int: The position of the last person standing.

    Examples:
        >>> josephus_iterative(5, 2)
        3
        >>> josephus_iterative(7, 3)
        4
    """
    circle = list(range(1, num_people + 1))
    current = 0

    while len(circle) > 1:
        current = (current + step_size - 1) % len(circle)
        circle.pop(current)

    return circle[0]


if __name__ == "__main__":
    import doctest

    doctest.testmod()