Enigmatic Code

Programming Enigma Puzzles

Enigma 325: Clear thin circuit

notableFrom New Scientist #1473, 12th September 1985 [link]

 

 

Enigma 325

An n-circuit is drawn on a triangular grid made up of equilateral triangles. It is a closed path of n different points and n different legs. Every leg runs along a grid-line and every point is a junction of grid-lines. Legs do not overlap, but they may cross.

A clear circuit is one that you cannot make a circuit with just some of the points. Thus the 5-circuit A is not clear. Points 1, 2 and 5 would make a 3-circuit: so would points 3, 4 and 5. But B is clear.

The fatness of a circuit is the area it encloses. Thus A has fatness 5 (measured by the number of little triangles enclosed), and B has fatness 7.

Can you find a clear 9-circuit with a fatness of 9 (or less)?

Happy Christmas from Enigmatic Code!

[enigma325]

Advertisements

One response to “Enigma 325: Clear thin circuit

  1. Jim Randell 25 December 2015 at 8:12 am

    I thought this was an interesting puzzle to solve programatically.

    Firstly we have to deal with the triangular grid (rather than the more normal rectilinear one). I used a similar approach to that in Enigma 175, where I consider grid axes that are 60° apart.

    Then we have to write code that will generate “clear” circuits with the required number of legs. I generate circuits with increasing maximum leg lengths.

    And finally we have to compute enclosed area of a (possibly) self-crossing circuit. My approach was to construct a box on the grid that encloses the shape, and then label all the triangles inside that box. We start by labelling a triangle on the outside of the shape with 0, then we label all adjacent triangles with 0 or 1 according to whether the shared edge of the adjacent triangles is part of the perimeter of the shape. If the shared edge is not included in the shape, then the value remains unchanged. But if the shared edge is included in the shape then value changes (from 0 to 1, or 1 to 0).

    Here is my Python program. It finds the first solution to the puzzle in 7.5s, but you can leave it running to find more solutions.

    # points are represented by a triangular grid with 60 degrees between the axes
    #
    # so points that correspond to legs in the circuit differ by multiples of one
    # of the following three "directions": (0, 1), (1, 0), (1, -1)
    #
    # an edge between two adjacent points is represented by a pair consisting of
    # those two points
    #
    # a grid triangle in represented by the three points that make up its vertices
    
    from itertools import count
    from enigma import irange, tuples, printf
    
    # can points p0 and p1 be connected along grid lines
    # return (<point>, <direction>, <number of edges>)
    def connected(p0, p1):
      ((x0, y0), (x1, y1)) = (p0, p1)
      if x0 == x1:
        if y0 < y1:
          return (p0, (0, +1), y1 - y0)
        else:
          return (p1, (0, +1), y0 - y1)
      elif y0 == y1:
        if x0 < x1:
          return (p0, (+1, 0), x1 - x0)
        else:
          return (p1, (+1, 0), x0 - x1)
      elif x0 + y0 == x1 + y1:
        if p0 < p1:
          return (p0, (+1, -1), x1 - x0)
        else:
          return (p1, (+1, -1), x0 - x1)
      else:
        return None
    
    # the edges between two connected points
    def edges(p0, p1):
      r = connected(p0, p1)
      if r is None: return None
      ((x0, y0), (dx, dy), n) = r
      s = list()
      for i in irange(1, n):
        (x1, y1) = (x0 + dx, y0 + dy)
        s.append(((x0, y0), (x1, y1)))
        (x0, y0) = (x1, y1)
      return s
    
    # generate "clear" n-circuits
    # n - number of points remaining to add to the circuit
    # m - max leg length
    # ps - points in the circuit
    # es - edges in the circuit
    # d - direction of the previous leg
    def generate(n, m, ps, es, d):
      # current position
      (x, y) = p = ps[-1]
      # choose a direction
      for (dx, dy) in ((+1, 0), (0, +1), (+1, -1)):
        # different from the last direction
        if (dx, dy) == d: continue
        # choose a length
        for i in irange(1, m):
          for i in (i, -i):
            # the new point
            q = (x + i * dx, y + i * dy)
    
            # check it is clear
            if any(connected(q, q1) for q1 in ps[1:-1]): continue
              
            # and new edges don't overlap
            es1 = edges(q, p)
            if es.intersection(es1): continue
            es1 = es.union(es1)
    
            # the last point should close the circuit
            if n == 1:
              es2 = edges(q, ps[0])
              if not(es2 is None or len(es2) > m or es1.intersection(es2)):
                yield (ps + [q], es1.union(es2))
    
            else:
              if connected(q, ps[0]): continue
              for s in generate(n - 1, m, ps + [q], es1, (dx, dy)):
                yield s
    
    # generate clear n-circuits
    def clear_circuits(n):
      # consider increasing maximum leg length
      for m in count(1):
        # shape with an initial leg of length m and a max edge of m
        (p0, p) = ((0, 0), (m, 0))
        # and add (n-2) more points to made an n-circuit
        for s in generate(n - 2, m, [p0, p], set(edges(p0, p)), (1, 0)):
          yield s
    
    # yield the three grid triangles adjacent to triangle <t>
    # returns (<adjacent triangle>, <shared edge>)
    def adj(t):
      ((x, y), (x1, y1), _) = t
      if x == x1:
        yield (((x - 1, y + 1), (x, y), (x, y + 1)), ((x, y), (x, y + 1)))
        yield (((x, y), (x + 1, y - 1), (x + 1, y)), ((x, y), (x + 1, y)))
        yield (((x, y + 1), (x + 1, y), (x + 1, y + 1)), ((x, y + 1), (x + 1, y)))
      else:
        yield (((x, y - 1), (x, y), (x + 1, y - 1)), ((x, y), (x + 1, y - 1)))
        yield (((x, y), (x, y + 1), (x + 1, y)), ((x, y), (x + 1, y)))
        yield (((x + 1, y - 1), (x + 1, y), (x + 2, y - 1)), ((x + 1, y - 1), (x + 1, y)))
    
    # return area enclosed by circuit <ps>
    def enclosed(ps, es):
    
      # compute the bounding box
      minx = min(x for (x, y) in ps) - 1
      maxx = max(x for (x, y) in ps)
      miny = min(y for (x, y) in ps) - 1
      maxy = max(y for (x, y) in ps)
    
      # generate the triangles in the bounding box
      tri = dict()
      for y in irange(miny, maxy):
        for x in irange(minx, maxx):
          tri[((x, y), (x, y + 1), (x + 1, y))] = None
          tri[((x, y + 1), (x + 1, y), (x + 1, y + 1))] = None
    
      # label the first triangle
      t0 = ((minx, miny), (minx, miny + 1), (minx + 1, miny))
      tri[t0] = 0
      ts = [t0]
    
      # consider triangles in ts
      while ts:
        t1s = list()
        for t in ts:
          v = tri[t]
          # and adjacent triangles / edges
          for (t1, e) in adj(t):
            if tri.get(t1, -1) is not None: continue
            tri[t1] = (v ^ 1 if e in es else v)
            t1s.append(t1)
        ts = t1s
    
      # count the squares (tri.valueus().count() doesn't work in Python 3)
      return sum(1 for x in tri.values() if x == 1)
    
    # generate clear 9-circuits
    for (ps, es) in clear_circuits(9):
      # calculate the enclosed area
      a = enclosed(ps, es)
      if a > 9: continue
      printf("{ps} enclosed = {a}")
      break
    

    Solution: Yes – it is possible to find a clear 9-circuit with a fatness of 9 (or less).

    The neatest looking solution, with a fatness of 7, is shown below:

    Enigma 325 - Solution 1

    The maximum leg length is 4.

    This figure was the published solution.

    Although there are other solutions, with a maximum leg length of 4, that have a fatness of 9:
    Enigma 325 - Solution 2a

    Enigma 325 - Solution 2b

    Enigma 325 - Solution 2c

    It could be argued that, although these shapes are less pleasing to the eye, they are a better fit to the question posed in the puzzle.

    There are also solutions with a maximum leg length of 5 that also have a fatness of 9:

    Enigma 325 - Solution 3

    (Of course the shapes given can be reflected and/or rotated to give similar solutions).

    For other Enigmas that have fun on triangular grids see: Enigma 82, Enigma 144, Enigma 175, Enigma 1774.

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: