# Enigmatic Code

Programming Enigma Puzzles

## Puzzle #51: Birthday candles

It is Tom’s 7th birthday and he has a cake with seven candles on it, arranged in a circle – but they are trick candles. If you blow on a lit candle, it will go out, but if you blow on an unlit candle, it will relight itself.

Since Tom is only 7, his aim isn’t brilliant. Any time he blows on a particular candle, the two either side also get blown on as well.

How can Tom blow out all the candles? What is the fewest number of puffs he can do it in?

[puzzle#51]

### 4 responses to “Puzzle #51: Birthday candles”

1. Jim Randell 21 March 2020 at 12:16 pm

Note: I solved a slightly different problem – where you can only aim for a candle that is lit.

This Python program runs in 155ms.

Run: [ @repl.it ]

```from enigma import irange, inf, arg, printf

N = arg(7, 0, int)
printf("[N={N}]")

# flip the bits at position (j - 1, j, j + 1)
def flip(bs, j):
bs = list(bs)
for i in (j, (j - 1) % N, (j + 1) % N):
bs[i] ^= 1
return bs

# clear the bits in <bs> in <k> moves (or less)
def clear(bs, k, ms=[]):
if not any(bs):
yield ms
elif k > 0:
for (j, x) in enumerate(bs):
if x:
yield from clear(flip(bs, j), k - 1, ms + [j])

# solutions for <n> bits, by shortest number of moves
def solve(n):
for k in irange(1, inf):
yield from clear([1] * n, k)

# find the smallest number of moves
for ms in solve(N):
printf("{n} -> {ms}", n=len(ms))
break
```

Solution: Tom can blow out the candles with 9 puffs.

Here is a diagram:

We start with all the candles alight (indicated by 1) and then in each row the state of the highlighted candles is flipped, until after 9 operations all the candles are out (indicate by 0).

2. Julian Gray 22 March 2020 at 6:00 pm

There is another way. If Tom blows once on each of his seven candles in any order, that makes them all go out.

• Jim Randell 22 March 2020 at 6:07 pm

@Julian: I see. I was only allowing blowing on candles that were lit. It seems that I was assuming a behaviour of 7 year old boys that isn’t specified in the puzzle text.

I expect your interpretation is the correct one.

• Jim Randell 22 March 2020 at 9:13 pm

Here is my program modified to allow aiming at any candle (lit or unlit).

```from enigma import irange, inf, arg, printf

N = arg(7, 0, int)
printf("[N={N}]")

# flip the bits at position (j - 1, j, j + 1)
def flip(bs, j):
bs = list(bs)
for i in (j, (j - 1) % N, (j + 1) % N):
bs[i] ^= 1
return bs

# clear the bits in <bs> in <k> moves (or less)
def clear(bs, k, ms=[]):
if not any(bs):
yield ms
elif k > 0:
for (j, _) in enumerate(bs):
if not(ms) or j != ms[-1]:
yield from clear(flip(bs, j), k - 1, ms + [j])

# solutions for <n> bits, by shortest number of moves
def solve(n):
for k in irange(1, inf):
yield from clear([1] * n, k)

# find the smallest number of moves
for ms in solve(N):
printf("{n} -> {ms}", n=len(ms))
break
```

It confirms that the candles can be blown out with only 7 puffs.

Aiming for each candle (in any order) means that each candle’s state will be flipped 3 times (once as the intended target, once as the intended target + 1, and once as the intended target – 1), so they will all end up extinguished. This works for any number of candles, but isn’t always the minimum number (e.g. when the number of candles is a multiple of 3, they can just be blown out in groups of 3).

This site uses Akismet to reduce spam. Learn how your comment data is processed.