# CGAC2022 Day 18: Light all of the candles

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.

It's Hanukkah! Unfortunately, it appears some of the candles in your menorah have been blown out. You've got a lighter on hand, but it doesn't work quite right. Whenever you use your lighter at position k, the candles at positions k-1, k, and k+1 all toggle. Let's see an example. We'll represent our candles as a binary sequence with 1 being the "lit" state.

[1, 1, 1, 1, 0, 1, 1, 1, 1]  initial
[1, 1, 1, 0, 1, 0, 1, 1, 1]  light 4
[1, 1, 0, 1, 0, 0, 1, 1, 1]  light 3
[0, 0, 1, 1, 0, 0, 1, 1, 1]  light 1
[1, 1, 1, 1, 0, 0, 1, 1, 1]  light 0
[1, 1, 1, 1, 1, 1, 0, 1, 1]  light 5
[1, 1, 1, 1, 1, 1, 1, 0, 0]  light 7
[1, 1, 1, 1, 1, 1, 1, 1, 1]  light 8


## The challenge

To cover our candelabra bases, we'll be working with any n>0 candles. Given the initial state of the candles as input, you must output a lighter usage sequence which will result in all of the candles being lit. Input and output can be taken in any reasonable form for a sequence. Output can be 0 or 1 indexed, but all numbers must fall within the range of the length (ie. no using the lighter at -1). You may assume that the input is always solvable, and you need only output one valid solution.

## Test cases

These examples are zero indexed.

[1, 1, 1, 1, 0, 1, 1, 1, 1] -> [4, 3, 1, 0, 5, 7, 8]
[0, 1, 1, 1, 1, 1, 1, 1, 1] -> [1, 2, 4, 5, 7, 8]
[1, 0, 1, 1, 1, 1, 1, 1, 1] -> [0, 1, 2, 4, 5, 7, 8]
[0, 0, 0, 0, 0, 0, 0, 0, 0] -> [1, 4, 7]
[1, 1, 1, 1, 1, 1, 1, 1, 1] -> []
[1, 1, 1, 0, 1, 1, 1] -> [0, 1, 3, 5, 6]
[0, 1, 1, 1, 1, 1, 1] -> [0, 2, 3, 5, 6]
[1, 1, 1, 1, 1, 1, 1] -> []
[0, 0] -> [0]
[0] -> [0]
[1] -> []

• Suggested testcases: [0, 0] -> [0]. Commented Dec 18, 2022 at 3:30
• Is a binary sequence of which candle get lighted allowed?
– l4m2
Commented Dec 18, 2022 at 5:46
• [1, 0, 1, 1, 1, 1, 1, 1, 1] -> [0, 1, 2, 4, 5, 7, 8]
– Neil
Commented Dec 18, 2022 at 9:58
• @alephalpha That mean some case with multiple solution?
– l4m2
Commented Dec 18, 2022 at 12:09
• Also, there's exactly 1 solution iff n mod 3 != 2
– l4m2
Commented Dec 18, 2022 at 12:10

# Jelly, 19 or 18 bytes

’1;Ø1ị^ḊƲƬṖḢ€ṪỊ‘&ƲT


Try it online! (note: this solution produces 1-based output but the footer which tries all test cases converts the output format to 0-based to make it easier to compare to the given examples)

This works as either a function or full program. Input is taken from a function argument or command-line argument as an array of 0 (unlit) / 1 (lit). Output is an array of the 1-based indexes of the candles that should be lit, and the order will be a suitable order in which you could light them.

The T at the end is what specifies the output format as the indexes of all the candles that should be lit. If you remove it, you instead get an array which specifies, for each candle, whether to light it or not (via the truthiness or falsiness of the element), although the truthy values could be either 1 or 2. I'm not sure whether that's a valid output format; if it is, that saves a byte.

## Algorithm

Most of the other answers here are brute-forcing, and the others are solving equations in order to solve the problem semi-efficiently. However, it's actually possible to solve the problem in linear time using an algorithm customised for the problem, and the linear-time algorithm comes out shorter than all the other answers so far.

The first observation is that the order in which the candles are lit doesn't matter; additionally, lighting the same candle twice cancels itself out. So all that we need to do is to identify the set of candles that need to be lit, and we can assume without loss of generality that the candles are lit from left to right.

Now imagine an algorithm that moves from candle to candle, from left to right, deciding whether or not to light each candle as it goes. If it's currently at the second candle or later, there actually isn't a decision to be made here; if the candle to the left of the current candle is unlit, it'd better light the current candle, because otherwise there's no way the candle to the left will ever be lit; and if the candle to the left of the current candle is lit, it can't light the current candle because then the candle to the left would be permanently extinguished.

This means that the only decision that has to be made is whether or not to light the first candle; after that all decisions are forced. In turn, that means that it's possible to "brute-force" the solution by only checking two possibilities, with the first candle lit and with the first candle unlit. As it happens, if the number of candles is equal to 2 modulo 3, either both of these possibilities will work or neither will; if the number of candles is unequal to 2 modulo 3, exactly one will work.

My conversion of this algorithm to Jelly works by storing the row of candles as integers for which only the bottom two bits are relevant; the 1s bit specifies the current state of the candle in the scenario where the first candle was lit, and the 2s bit specifies the current state of the candle in the scenario where the first candle wasn't lit. Using XOR operations to do the toggles means that we're processing both of the scenarios in parallel, by focusing on different bits – in other words, this is SIMD Jelly that actually vectorises on the processsor! All that then needs to be implemented is to simulate the two possible starting states in parallel, then see which of them worked. (Because the challenge says "You may assume that the input is always solvable, and you need only output one valid solution.", this solution picks one of the two scenarios arbitrarily if both of them work or if neither of them work; the latter situation shouldn't occur and the former situation allows either solution.)

One thing that makes the answer a little more confusing: because only the bottom two bits of the integers matter, the obvious choice would be to use 0, 1, 2, 3, but I actually used -2, -1, 0, 1 because it was slightly golfier. Additionally, a bit being clear means that the candle is lit, and a bit being set means that the candle is unlit, the other way round from the intuitive meaning; again, this was just because it was slightly golfier. Thus, 0 means that a candle is lit in both scenarios; -1 means that a candle is unlit in both scenarios; 1 means that the candle is lit if and only if the first candle was left unlit; -2 means that the candle is lit if and only if the first candle was lit.

## Explanation

’1;Ø1ị^ḊƲƬṖḢ€ṪỊ‘&ƲT
’                      decrement each:
maps a    lit candle (1) to 0
maps an unlit candle (0) to -1
1;                    prepend 1; this inserts a "zeroth candle" that
determines whether to light the first candle
Ƭ             loop until a previously seen output is observed:
Ʋ                (the loop body contains four commands)
ị                   take the following elements from {the loop variable}:
Ø1                      the first element, and the first element again
^                  bitwise XOR {corresponding elements of that list} with
Ḋ                   {the loop variable} minus its first element
Ṗ            take all but the last element of
{the history of the loop variable's values}
€          replace each element of {that curtailed history}
Ḣ             with its first element
{this is the value Ʋ refers to later}
Ṫ         take its last element
Ị        0 if {the last element} is <-1 or >1, 1 otherwise
‘       increment this
&      bitwise AND with
Ʋ       the value as of four commands ago
{except its last element, due to Ṫ}
T    take the 1-based indexes of all truthy elements


The main loop that simulates the behaviour of all the candles is Ø1ị^ḊƲƬ (here, Ƭ specifies that there is a loop and what type of loop it is, Ʋ is what specifies how many commands to loop over, and the rest of it is the loop body). The idea is that the loop variable stores the current state of all the relevant candles (i.e. the candle that we're considering whether to light, plus one candle to its left and all candles to its right); the first element of the loop variable determines whether the first three candles should have their lighting status toggled (i.e. the second candle is lit), but because the first element will become irrelevant after this point, the required functionality is to delete the first element of the array and XOR it with the second and third (which can be expressed tersely in Jelly by forming a list of two copies of the first element, and XORing corresponding elements with the tail of the loop variable – elements beyond the first two remain untouched).

Things get a bit weird at the end of the loop, but this solution just allows the weirdness to happen and fixes it up later. This sort of loop iterates until it sees an output it's previously seen. The last iteration that actually represents candles is the iteration where the algorithm is considering whether to light the last candle; at this point, the array is two elements long, consisting of the states of the penultimate and last candles (let's call these x and y, so the array is [x, y]). For a possibility to be valid, x and y must be in the same state as each other at this point, either both lit or both unlit (otherwise, either the first candle was wrong or the problem is unsolvable). The next loop iteration should conceptually be on a 1-element list, but the algorithm always toggles two elements of the list, so the loop variable will now be [x^y, x]. Continuing to calculate, on the iteration after that, the loop variable will be [y, x^y], and on the iteration after that, it will be [x, y], i.e. a repeat. So the loop must end after at most three 2-element loop variables.

As it happens, these last three variables must always be distinct from each other. To prove this, consider the two scenarios (first candle lit, and first candle unlit), and consider which candles have differing actions in both scenarios (i.e. candles on which the algorithm uses the lighter in one scenario, but not in the other). It's fairly easy to see that the positions of these differing candles follow a regular repeating pattern (of two differing candles followed by one non-differing candle), regardless of which candles were initially lit; this implies that on any three consecutive iterations of the loop, their internal states must be different from each other (otherwise, the information needed to maintain this regular repeating pattern would be lost).

This in turn means that the history of loop iterations will contain the useful iterations that specify the history of what happened to the candles, plus two more: [x^y, x] and [y, x^y]. The latter is useless, and gets discarded by Ṗ. However, the former starts with the value x^y, which is useful because a scenario is valid if and only if x and y are equal in that scenario. The value of x^y therefore specifies which scenarios are valid: 0 means that they're both valid, 1 means that only the scenario where the first candle was unlit is valid, -2 means that only the scenario where the first candle was lit is valid, and -1 means that they are both invalid. This value is then used to select a scenario: I chose the first-candle-lit scenario only when the value is -2, and the first-candle-unlit scenario otherwise, because this makes it possible to map the x^y value onto an integer with the relevant bit set in only two commands (Ị that checks whether the value is in the range -1..1 inclusive, and an increment).

Once the algorithm has chosen a scenario, it then needs to work out which candles were lit in that scenario; this can be done simply by looking at the first element of the loop variable as of each loop iteration (which is why µ was used to save the history of the loop), and using a bitwise AND to extract the relevant bit.

The loop iteration history is therefore being used for two different purposes, but both of them only care about the first element of the loop variable. This makes it possible to rewrite the history to remove all but the first element of each element, which saves a byte later because it means that the "keep only the first element" command Ḣ doesn't need to be written twice.

Thanks to @Jonathan Allan for saving a byte – normally I use µ to mark values that need to be reused later in the code, but Ʋ also works in this context. Although this doesn't save any bytes directly, its positioning to the right of the & means that it separates the & from the T, preventing them accidentally (and incorrectly) parsing as a group, thus meaning that no extra bytes need be wasted to make the T parse correctly.

• Nice job. The 20 can be 19 with ṪỊ‘&Ʋ. Commented Dec 18, 2022 at 18:42
• What an incredibly subtle improvement! Both µ and Ʋ work to prevent part of the code taking a right-hand argument, but they go in different places in the program and thus apply to different things, and my hint about arity was redundant whereas yours isn't and saved a byte. I hadn't even thought of using the small-ranged scoping quicks like Ʋ as a method of reusing values (as opposed to a method of specifying the scope of loops) – that's something that you could reasonably add to the Jelly tips page, as it's non-obvious and there are a few other situations in which it could help. Commented Dec 18, 2022 at 19:24
• Wonderful insight and explanation Commented Dec 20, 2022 at 23:57

# PARI/GP, 54 bytes

a->matsolvemod(matrix(#a,,i,j,(i-j)^2<2),2,[!t|t<-a]~)


Attempt This Online!

Returns a binary array of which candle get lighted.

# PARI/GP, 72 bytes

a->k=0;[k|t<-a,matsolvemod(matrix(#a,,i,j,(i-j)^2<2),2,[!t|t<-a]~)[k++]]


Attempt This Online!

$$\1\$$-indexed.

This is solving linear equations $$\AX=B\$$ over the field $$\\mathbb{F}_2\$$. The vector $$\B\$$ is the element-wise negation of out input. The matrix is $$\A = (a_{ij})\$$, where $$\a_{ij} = 1\$$ whenever $$\|i-j|<2\$$, and $$\0\$$ otherwise. After that we just take the indices of $$\1\$$'s in the solution $$\X\$$.

The matrix $$\A\$$ is singular when the length of the input satisfies $$\n\equiv2\pmod 3\$$. So I have to use the built-in matsolvemod instead of simply multiplying the inverse matrix.

# Python NumPy, 71 bytes

lambda N:where(~N*mat(tril(triu(N==N,-1),1)).I%2)[1]
from numpy import*


Attempt This Online!

Port of @alephalpha's PARI/GP answer (but 0-indexed).

# 05AB1E, 22 bytes

TS¹gã.ΔÐ¦0ª^s0š^^P}∞sÏ


Try it online!

$$\O(n2^n)\$$ brute force.

-1 byte: append only one 0

TS¹gã.ΔÐ¦0ª^s0š^^P}∞sÏ
TS                      # digits of 10 (pushes ["1", "0"])
¹g                    # length of input
ã                   # cartesian power
.Δ            }    # first where the following is true:
Ð                #   triplicate
¦               #   tail
0ª             #   append 0
^            #   xor
s           #   swap
0š         #   prepend 0
^        #   xor
^       #   xor with implicit input
P      #   product
∞sÏ  # truthy indicies


# 05AB1E, 33 bytes

¦1ª^ΔDNo3*.$0Þ«^}ćiR5bÞ^R1ë0}ª∞sÏ  Try it online! $$\O(n log(n))\$$. Uses the same idea as alephalpha's answer but it implements the algorithm for solving $$\A{\bf x} = {\bf b}\$$. Unfortunately it's longer than just brute force. ¦1ª^ΔDNo3*.$0Þ«^}


transforms $$\{\bf b}\$$ into $$\{\bf d}\$$ such that $$\ A{\bf x} = {\bf b} \Leftrightarrow C{\bf x} = {\bf d} \$$ where $$\C = (c_{ij})\$$, $$\c_{ij}=1\$$ if $$\i=j+1\$$ or $$\j=n\$$ and $$\n-i\not\equiv 1\pmod{3}\$$ and $$\c_{ij}=0\$$ otherwise. This is a matrix where all numbers just below the diagonal are 1 and the last column from bottom up is 1, 0, 1, 1, 0, 1 ...

ćiR5bÞ^R1ë0}ª


uses substitution to finally solve the equation.

# Charcoal, 29 bytes

ＩΦＥＸ²Ｌθ⌕Ａ⮌⍘ι²1⬤θ﹪⁺λΣＥ³№ι⊖⁺μν²


Try it online! Link is to verbose version of code. Outputs all solutions (e.g. [1, 1, 0, 1, 1] -> [0, 1] or [3, 4]; solutions are double-spaced from each other). Explanation: Generates all 2ⁿ sets of lighter usage and filters out those that don't result in the desired candle state.

    ²                           Literal integer 2
Ｘ                            Raised to power
θ                         Input array
Ｌ                          Length
Ｅ                             Map over implicit range
ι                    Current value
⍘                     Converted to base
²                   Literal integer 2
⮌                      Reversed
⌕Ａ                      Find all occurrences of
1                  Literal string 1
Φ                             Filter sets where
θ                Input array
⬤                 All elements satisfy
³          Literal integer 3
Ｅ           Map over implicit range
№         Count of
μ     Inner index
⁺      Plus
ν    Innermost value
⊖       Decremented
ι        In current set
Σ            Take the sum
⁺              Plus
λ             Inner value
﹪           ²   Is odd
Ｉ                              Cast to string
Implicitly print

• Best I could do with @ais523's algorithm was 36 bytes: Try it online! Link is to verbose version of code. 1-indexed output.
– Neil
Commented Dec 20, 2022 at 23:17

# JavaScript (V8), 86 bytes

f=(x,e=[],i=0)=>1+x[j=i]?f(x.map(v=>j*j--<2^v),[...e,i],++i)||f(x,e,i):/0/.test(x)?0:e


Try it online!

-1 from Arnauld

• Fact: I use V8 because I copied test case from a python answer
– l4m2
Commented Dec 18, 2022 at 5:55
• You can use !/0/.test(x) instead of x.every(_=>_) (-1) Commented Dec 18, 2022 at 11:53

# JavaScript (ES6), 48 bytes

This is based on ais523's insight
-3 thanks to @l4m2

Returns an array of binary values telling which candles were lit.

f=(a,p,b=a.map(q=v=>q^=(p^=v^!q)^v))=>p?b:f(a,1)


Try it online! (raw output)

Try it online! (with postprocessing to print a list of indices)

### Commented

f = (            // f is a recursive function taking:
a,             //   a[] = input array
p,             //   p   = value of the previous candle,
//         initially set to either undefined or 1
b =            //   b[] = output array, built as follows:
a.map(q =    //     initialize q to a zero'ish value
v =>         //     for each value v in a[]:
q ^= (     //       the value of the current candle is v XOR q
p ^=     //       the value of the previous candle is p
v ^ !q //       if p is not set, we toggle the current
//       candle, implicitly toggle the previous one
) ^ v      //       and set q = 1 to toggle the next one
)            //     end of map()
) =>             //
p ?            // if the last candle is lit:
b            //   success: return b[]
:              // else:
f(a, 1)      //   try again with p initially set to 1

• 50
– l4m2
Commented Dec 19, 2022 at 8:31
• 48
– l4m2
Commented Dec 19, 2022 at 11:35

# Pip, 75 66 bytes

@({$+($BX((^1X3WR0Xk)@(k-_+1,2*k-_+1)Ma)BX\a)=k}FI,(k:#a)CB_MF\,k)


Try It Online!

-9 bytes thanks to @DLosc

0 indexed. Verify all test cases here (it's slow)

• I haven't looked at the whole solution yet, but the Wrap and Split operators are quite useful in part of it: (_M(J[0Xk;1X3;0Xk])) -> (^1X3WR0Xk) Commented Dec 19, 2022 at 19:34

# Python3, 214 bytes:

def f(m):
q,s=[(m,[])],[m]
while q:
m,M=q.pop(0)
if all(m):return M
for i in range(len(m)):
U=[*m]
for j in[-1,0,1]:
if 0<=i+j<len(m):
U[i+j]=not U[i+j]
if U not in s:q+=[(U,M+[i])];s+=[U]


Try it online!

• -8 bytes Commented Dec 18, 2022 at 2:00
• 192 bytes: Try it online! Commented Dec 18, 2022 at 2:32

# Python, 133 bytes

lambda t:max((w:=[j,*(u:=t+[0,0])[:2]])and[i for i in range(len(u)-2)if(w:=[w[1]^(s:=w[0]^1),w[2]^s,u[i+2]])and s]*w[0]for j in[0,1])


Attempt This Online!

An alternative Python answer based on @ais523's insight. Not a competitive method compared to @loopywalt's numpy answer, but I thought it was interesting enough to warrant posting.

Interstingly, a recursive solution was the same length, but as it required the inclusion of f= in the byte count, it was technically longer.