How to Resolve the Circular Seating (Josephus) Problem in Python

The "Circular Seating Arrangement" or "Josephus Problem" is a classic algorithmic puzzle. The premise is simple: a group of people stand in a circle and count off by a specific number X. Every time the count reaches X, that person leaves the circle, and the counting continues from the next person. This process repeats until only one person remains.

This guide explains how to simulate this process in Python using lists and modular arithmetic to determine the last survivor.

Understanding the Logic

To solve this programmatically, we treat the circle of people as a list of numbers [1, 2, ..., n]. The core challenge is calculating the correct index to remove, especially since the list shrinks and the counting wraps around to the beginning.

We track the current_index. To find the next person to eliminate based on step x:

1. Add x to the current position.
2. Subtract 1 (because Python lists are 0-indexed, but our count is 1-based).
3. Use the modulo operator % against the current number of people to wrap around if the index exceeds the list size.

Step 1: Setting Up the Simulation

First, we create a function that accepts the total number of people (n) and the step count (x). We initialize the list of seats.

def game(n, x):
    # Create a list from 1 to n
    # Example: if n=5, seats = [1, 2, 3, 4, 5]
    seats = list(range(1, n + 1))
    
    return seats

Step 2: Implementing the Elimination Loop

We need a loop that continues as long as there is more than one person left (len(seats) > 1). Inside this loop, we calculate the removal index and pop the element.

Calculating the Index

A common mistake is forgetting that the list size changes or mishandling the 0-based index conversion.

# ⛔️ Incorrect: Logic errors in index calculation
index = 0
while len(seats) > 1:
    # Error 1: Using 'n' instead of len(seats) prevents shrinking logic
    # Error 2: Not subtracting 1 leads to "off-by-one" errors
    index = (index + x) % n 
    seats.pop(index)

# ✅ Correct: Dynamic index calculation
index = 0
while len(seats) > 1:
    # 1. Add (x - 1) to move x steps forward in 0-indexed logic
    # 2. Modulo by len(seats) (current size) to wrap around
    index = (index + x - 1) % len(seats)
    
    # Remove the person at the calculated index
    removed_person = seats.pop(index)
    # Note: After popping, the next person naturally shifts into 'index'
    # so we don't need to increment index manually again.

note

When you pop(index), the element at index + 1 shifts to index. Therefore, the index variable automatically points to the "next" person for the start of the next round of counting.

Complete Code Solution

Here is the complete implementation in party.py. It takes user input for x and runs the simulation for n=263 (as per the specific problem requirements).

def game(n, x):
    """
    Simulates the circular elimination game.
    n: Total number of people
    x: The counting step (reporting period)
    """
    # Initialize the seat list, representing the seat numbers
    seats = list(range(1, n + 1))
    
    # Initialize the index for counting
    index = 0

    # Simulate counting until only one person is left
    while len(seats) > 1:
        # Calculate the next position to remove
        index = (index + x - 1) % len(seats)
        
        # Remove the person
        seats.pop(index)

    # The remaining person is the last performer
    last_performer = seats[0]
    print(f"The number of the last performer is: {last_performer}")

if __name__ == '__main__':
    try:
        # Get input from user
        input_val = input('Please enter the numerical value of the reporting period x: ')
        x = int(input_val)
        
        # Run game with n=263
        game(263, x)
    except ValueError:
        print("Invalid input. Please enter an integer.")

Execution Output

If you run the script with x=10:

Please enter the numerical value of the reporting period x: 10
The number of the last performer is: 108

If you run the script with x=18:

Please enter the numerical value of the reporting period x: 18
The number of the last performer is: 254

Conclusion

Solving circular arrangement problems relies heavily on modular arithmetic. By consistently applying the formula (current_index + step - 1) % current_length, you can simulate the wrapping behavior of a circle using a linear array or list.

1. Initialize your list of participants.
2. Loop until the list length is 1.
3. Calculate the removal index dynamically based on the remaining number of elements.
4. Pop the element and let the indices shift naturally.