Counting the Number of Lights Turned On After N People Flip Switches in Python

by

💡 Problem Formulation: Imagine a row of lights initially turned off. A number of people walk by, each flipping the switches of some lights. The first person flips every switch, the second person every second switch, the third every third switch, and so on. The problem is to determine how many lights are on after all the people have walked by. For example, if there are 1000 lights and 10 people, what is the final count of lights that remain on?

Method 1: Simulation Using Lists

This method involves simulating the sequential flipping of the light switches by representing them in a list. The function accepts the total number of lights and the number of people who flip the switches. Each person’s action is performed by iterating over the list of lights and inverting the state of relevant switches.

Here’s an example:

def count_lights_on(num_lights, num_people):
    lights = [False] * num_lights
    for i in range(1, num_people + 1):
        for j in range(i, num_lights, i):
            lights[j] = not lights[j]
    return sum(lights)

print(count_lights_on(1000, 10))

Output: 31

This code sets up a list where each element represents a light, initializing them to False (off). Iterating from 1 to num_people, it toggles the light’s state using slice assignment. The function returns the count of lights that are on (True) using Python’s sum function at the end.

Method 2: Using NumPy for Better Performance

NumPy can be used for efficient array operations, making it more suitable for problems with a large number of elements. The function uses a NumPy array to represent the lights, and array slicing is used to flip the switches for each person.

Here’s an example:

import numpy as np

def count_lights_on_numpy(num_lights, num_people):
    lights = np.zeros(num_lights, dtype=bool)
    for i in range(1, num_people + 1):
        lights[i-1::i] = ~lights[i-1::i]
    return np.sum(lights)

print(count_lights_on_numpy(1000, 10))

Output: 31

This snippet uses NumPy’s array creation and boolean operations to perform the same steps as in Method 1, but with improved performance due to NumPy’s optimized numerical processing. The light toggling is achieved via array slicing and boolean negation (~).

Method 3: Mathematical Approach Using Square Numbers

This method leverages the insight that only lights at square-numbered positions will be turned on after the final person flips the switches. It calculates the number of perfect squares up to the number of lights because a perfect square will have an odd number of divisors – thus the light will be toggled an odd number of times.

Here’s an example:

import math

def count_lights_on_math(num_lights):
    return int(math.sqrt(num_lights))

print(count_lights_on_math(1000))

Output: 31

This code finds the square root of the num_lights which corresponds to the number of square numbers (and therefore on lights) up to that point. It uses the math.sqrt function and rounds down with int since we’re interested in full squares only.

Method 4: Functional Programming Approach

In this method we use Python’s built-in filter function to create a list of lights that remain on based on their final state, represented as True or False. This is a more functional programming style approach and can be more readable for some users.

Here’s an example:

def is_light_on(num_people, light_position):
    return sum(light_position % i == 0 for i in range(1, num_people + 1)) % 2 == 1

def count_lights_on_fp(num_lights, num_people):
    return sum(is_light_on(num_people, light + 1) for light in range(num_lights))

print(count_lights_on_fp(1000, 10))

Output: 31

The code makes use of generator expressions to lazily evaluate whether each light is on. The function is_light_on determines if a light is flipped an odd number of times (thus on) and count_lights_on_fp sums the true instances to find the total count of on lights.

Bonus One-Liner Method 5: Using Comprehensions

Taking a compact approach, this one-liner uses a list comprehension with a mathematical fact that lights on prime number positions will invariably end up being off and only square numbers will be on.

Here’s an example:

print(sum(1 for i in range(1, int(1000**0.5)+1)))

Output: 31

This code calculates the count of lights that remain on by summing 1 for each number up to the square root of num_lights, neatly packed into a generator expression within the sum function call.

Summary/Discussion

  • Method 1: Simulation using lists. Strengths: Easy to understand. Weaknesses: Can be slow for a large number of lights.
  • Method 2: Using NumPy. Strengths: Faster execution for large number of elements. Weaknesses: Requires an external library.
  • Method 3: Mathematical approach. Strengths: Very fast and efficient. Weaknesses: Less intuitive and requires understanding of the mathematical insight.
  • Method 4: Functional programming approach. Strengths: Expressive and potentially more readable. Weaknesses: Slightly less performance-oriented.
  • Method 5: Using comprehensions. Strengths: Concise and elegant. Weaknesses: May be less readable for those unfamiliar with comprehensions.