100 switches/100 lights puzzle

one_hundred_switches_one_hundred_lights.py

#!/usr/bin/env python3

# Solves https://www.youtube.com/watch?v=ltsx5389iEs

# The idea is to identify all lights in ⌈log2(n)⌉ moves by assigning each bulb
# an integer and using the unique bit representation of each as the sequence of
# light switches for which it was powered on (1 means it was on for a given
# trial, 0 means it was off).

# NOTE: The bit representation + transpose operation makes the logic most clear,
# but you can also generate this code in other ways (e.g., by applying a "01"
# pattern to each half of the previous pattern recursively). There are also many
# equivalent codes (which you can generate by permuting the number assignments
# before transposing or swapping out bulb numbers up to the next power of 2
# where the number of bulbs is not a power of 2, or similarly reordering the
# switches).

import math


def main():
    for pattern in transpose(bitmasks(100)):
        print("".join(pattern))


def transpose(it):
    return zip(*it, strict=True)


def bitmasks(n):
    size = math.ceil(math.log2(n))
    spec = f"0{size}b"
    for i in range(n):
        yield format(i, spec)


if __name__ == "__main__":
    main()