Enigmatic Code

Programming Enigma Puzzles

Enigma 1616: One good turn

From New Scientist #2781, 9th October 2010 [link]

Joe’s 3-by-3 grid can be made to represent any of the six faces of a die by placing nine counters, coloured on one side and white on the other. Joe placed the nine counters with just the one in the centre coloured side up. Penny’s task this week is to increase the number represented to 4 by turning over counters. But, of course, there is a catch. Every time Penny decides which counter to turn over she has to remember to turn over all counters in squares that are immediately adjacent, horizontally and vertically. Not only that, she has to record how many counters she turns over each time, and the total has to be the minimum possible.

What is that minimum?

In 2018 this puzzle published again by New Scientist as a tribute to Bob Walker, who died in February of that year. (New Scientist #3171, 31st March 2018)

[enigma1616]

Advertisements

2 responses to “Enigma 1616: One good turn

  1. jimrandell 28 December 2011 at 4:13 pm

    The following Python program does a breadth first search to find the minimum number of flips required to reach all possible outcomes from the starting position. It runs in 4.3s (2.0s under PyPy).

    start  = "000" + "010" + "000"
    finish = "101" + "000" + "101"
    
    # actually, due to symmetry we only need to consider first moves of a corner, edge and centre
    r0 = list(map(str, (0, 1, 4)))
    r1 = list(map(str, range(9)))
    
    # track the minimum number of moves to get to a certain position
    mc = {}
    
    # initiate a breadth first search
    def search(l):
      while len(l) > 0:
        n = []
        for (p, m, c) in l:
          if p in mc:
            if mc[p] < c: continue # we already have a lower min for this position
          else:
            mc[p] = c
          if p != finish:
            # try each turn
            for s in (r0 if len(l) == 1 else r1):
              if len(m) > 0 and m[-1] == s: continue
              n.append(flip(p, m, c, s))
        l = n
    
    # do a flip
    
    f = { '0': '1', '1': '0' }
    
    def flip(p, m, c, s):
      (p0, p1, p2, p3, p4, p5, p6, p7, p8) = p
      if s == '0':
        return ( f[p0] + f[p1] +   p2  + f[p3] +   p4  +   p5  +   p6  +   p7  +   p8,  m + s, c + 3 )
      elif s == '1':
        return ( f[p0] + f[p1] + f[p2] +   p3  + f[p4] +   p5  +   p6  +   p7  +   p8,  m + s, c + 4 )
      elif s == '2':
        return (   p0  + f[p1] + f[p2] +   p3  +   p4  + f[p5] +   p6  +   p7  +   p8,  m + s, c + 3 )
      elif s == '3':
        return ( f[p0] +   p1  +   p2  + f[p3] + f[p4] +   p5  + f[p6] +   p7  +   p8,  m + s, c + 4 )
      elif s == '4':
        return (   p0  + f[p1] +   p2  + f[p3] + f[p4] + f[p5] +   p6  + f[p7] +   p8,  m + s, c + 5 )
      elif s == '5':
        return (   p0  +   p1  + f[p2] +   p3  + f[p4] + f[p5] +   p6  +   p7  + f[p8], m + s, c + 4 )
      elif s == '6':
        return (   p0  +   p1  +   p2  + f[p3] +   p4  +   p5  + f[p6] + f[p7] +   p8,  m + s, c + 3 )
      elif s == '7':
        return (   p0  +   p1  +   p2  +   p3  + f[p4] +   p5  + f[p6] + f[p7] + f[p8], m + s, c + 4 )
      elif s == '8':
        return (   p0  +   p1  +   p2  +   p3  +   p4  + f[p5] +   p6  + f[p7] + f[p8], m + s, c + 3 )
    
    # list of [ <current-pos>, <moves>, <count> ]
    search([(start, '', 0)])
    
    print("found {n} configurations".format(n=len(mc)))
    print("{p} => {m} flips".format(p=finish, m=mc[finish]))
    

    Solution: The minimum number of counters turned over is 33.

    Each counter is selected to be turned over once (and it along with its neighbours are flipped). The order the counters are selected in doesn’t matter.

    You can also use this program to find the minimum number of flips required to reach other representations of dice faces (1 → 0 flips, 2 → 11 flips, 3 → 22 flips, 4 → 33 flips, 5 → 12 flips, 6 → 13 flips).

  2. Jim Randell 10 April 2018 at 7:21 am

    This was one of the earlier puzzles I posted to the site in December 2011.

    I am revisiting it now, as it was selected as one of Bob Walker‘s best Enigma puzzles in a recent tribute to him in New Scientist [ link ]. (I think I would have chosen Enigma 1475 as my favourite puzzle by Bob Walker).

    This Python program executes in 79ms, and finds all possible finishing positions and their flip count. Positions you want to see the answer for can be placed in the finish list.

    Run: [ @repl.it ]

    from enigma import grid_adjacency, subsets, printf
    
    # consider the 3x3 grid:
    #
    #   0 1 2
    #   3 4 5
    #   6 7 8
    
    # flip[i] = counters flipped by position i
    flip = grid_adjacency(3, 3, include_self=1)
    
    # apply the sequence of moves in <ss> to position <pos>
    # return (<final position>, <number of flips>)
    def play(pos, ss):
      pos = list(pos)
      t = 0
      for i in ss:
        for j in flip[i]:
          pos[j] ^= 1
          t += 1
      return (tuple(pos), t)
    
    # start position
    start = (0, 0, 0) + (0, 1, 0) + (0, 0, 0)
    
    # finish positions
    finish = [
      (1, 0, 1) + (0, 0, 0) + (1, 0, 1),
    ]
    
    # find final positions for each sequence of moves
    for ss in subsets((0, 1, 2, 3, 4, 5, 6, 7, 8)):
      (final, t) = play(start, ss)
      if final in finish:
        printf("{start} -> {final} [{t} flips] = {ss}")
    

    Or, using bit patterns to represent the grid:

    from enigma import irange, int2base, printf
    
    # bit patterns for flips, and number of flips
    flip = (
       # 876543210 flips
      (0b000001011, 3), # 0
      (0b000010111, 4), # 1
      (0b000100110, 3), # 2
      (0b001011001, 4), # 3
      (0b010111010, 5), # 4
      (0b100110100, 4), # 5
      (0b011001000, 3), # 6
      (0b111010000, 4), # 7
      (0b110100000, 3), # 8
    )
    
    # apply the sequence of moves in <ss> to position <pos>
    # return (<final position>, <number of flips>)
    def play(pos, ss):
      t = 0
      b = 0
      while ss:
        if ss & 1:
          (m, v) = flip[b]
          pos ^= m
          t += v
        ss >>= 1
        b += 1
      return (pos, t)
    
    # start position
    start = 0b000010000
    
    # finish positions
    finish = [ 0b101000101 ]
    
    # find final positions for each sequence of moves
    for ss in irange(0, 0b111111111):
      (final, t) = play(start, ss)
      if final in finish:
        fmt = lambda n: int2base(n, base=2, width=9, group=3, sep="_")
        printf("{start} -> {final} [{t} flips] = {ss}", start=fmt(start), final=fmt(final), ss=fmt(ss))
    

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 )

w

Connecting to %s

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

%d bloggers like this: