Light bulb sequence

What this hard constraint-satisfaction puzzle tests

This is a hard combinatorial problem that requires you to count valid configurations under a structural constraint. It rewards systematic reasoning about forbidden patterns and how to avoid over- or under-counting when direct enumeration becomes intractable.

The challenge lies in translating the exclusion rule into a workable counting method. Candidates typically approach this by building up valid sequences incrementally, tracking state to ensure no forbidden substring emerges, or by using recurrence relations to capture valid extensions at each step. The constraint is local (no substring of length 4 has a specific pattern), but its global effect on the configuration space requires careful bookkeeping.

• Forbidden pattern avoidance and regular languages
• Dynamic programming with state tracking
• Recurrence relations and transfer matrices
• Distinguishing exhaustive search from structural insight

Firms value seeing a clear mental model of what states matter (e.g., what you need to remember about the last few bulbs to decide whether the next one can be lit) and whether you can implement that model without errors or combinatorial explosion.