Enigmatic Code

Programming Enigma Puzzles

Enigma 1127: Lights out

From New Scientist #2283, 24th March 2001 [link]

There are 13 lights, A, B, C, …, L, M, in the dormitory and each one has its own switch. To save matron having to operate all 13 switches, 34 pairs of lights are connected. They are:

AB, AC, AD, AJ, BC, BE, BI, CE, CF, CG, CH, CI, CK, CM, DE, DF, DG, DI, DJ, DK, DL, DM, EF, EG, EH, EI, EJ, EL, FJ, FM, GH, GM, KL, LM.

Whenever a switch is operated it changes its own light and each of the lights connected to it from on to off, or from off to on. When matron enters the dormitory at 9.00 pm all the lights are on. As an example, if she operates switch A then lights A, B, C, D and J go off. If she then operates switch J then lights A, D and J come back on and lights E and F go off.

Question: Which switches should matron operate so that all the lights are off when she has finished.

See also Enigma 1137.

[enigma1127]

Advertisements

One response to “Enigma 1127: Lights out

  1. Jim Randell 20 February 2017 at 7:25 am

    This is a precursor of Enigma 1137 (which was published 10 weeks after this puzzle).

    Having already solved the second part of Enigma 1137 we know that there will be a sequence that turns all the lights off if they all start off illuminated.

    The same program used to solve the first part of Enigma 1137 can also be used to solve this puzzle.

    This Python program runs in 167ms.

    from collections import defaultdict
    from enigma import subsets, join, printf
    
    # labels for lights and switches
    labels = 'ABCDEFGHIJKLM'
    
    # connections between lights
    connections = (
      'AB', 'AC', 'AD', 'AJ', 'BC', 'BE', 'BI', 'CE', 'CF', 'CG', 'CH',
      'CI', 'CK', 'CM', 'DE', 'DF', 'DG', 'DI', 'DJ', 'DK', 'DL', 'DM',
      'EF', 'EG', 'EH', 'EI', 'EJ', 'EL', 'FJ', 'FM', 'GH', 'GM', 'KL', 'LM'
    )
    
    # map of switch -> lights
    switch = defaultdict(set)
    
    # each switch operates it's own light
    for k in labels:
      switch[k].add(k)
    
    # if lights X and Y are connected then switch X also operates light Y
    # and switch Y also operates light X
    for (x, y) in connections:
      switch[x].add(y)
      switch[y].add(x)
    
    # operate a set of switches
    # return the lights that are on
    def operate(s, on, switch):
      d = defaultdict(int)
      # initially the lights in "on" are on
      for k in on:
        d[k] = 1
      # operate each switch
      for x in s:
        for k in switch[x]:
          d[k] ^= 1
      return sorted(k for (k, v) in d.items() if v)
    
    # lights that are initially on
    on = labels
    
    # consider possible subsets of switches
    for s in subsets(labels):
      r = operate(s, on, switch)
      if len(r) == 0:
        printf("on = {on}, switch {s} -> all off", s=join(s))
    

    Solution: Matron should operate switches A, D, E, F, I, J, M to turn off all the lights.

    This is the only solution.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: