Enigmatic Code

Programming Enigma Puzzles

Puzzle #51: Birthday candles

From New Scientist #3274, 21st March 2020 [link] [link]

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).

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: