Enigmatic Code

Programming Enigma Puzzles

Enigma 329: Clear short circuit

From New Scientist #1477, 10th October 1985 [link]

Enigma 325

An n-circuit 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 length of a circuit is just the sum of the lengths of the legs. Thus A has length 7, and B has length 11.

Can you find a clear 12-circuit with a length of 21 (or less)?

A similar problem to Enigma 325.

[enigma329]

Advertisements

One response to “Enigma 329: Clear short circuit

  1. Jim Randell 22 January 2016 at 7:39 am

    From my perspective this is an easier variation on Enigma 325. Having solved the previous puzzle I already have code to generate “clear” n-circuits, and calculating the length of a circuit is much easier than calculating the area it encloses (in fact the program accumulates the list of edges that make up the circuit as it goes, so we can even prune away circuits that exceed the maximum required length as they are constructed).

    This Python program runs in 2.9s.

    from enigma import irange, 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
    # t - max total perimeter
    # ps - points in the circuit
    # es - edges in the circuit
    # d - direction of the previous leg
    def generate(n, m, t, 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 len(es1) + len(es2) > t or es1.intersection(es2)):
                yield (ps + [q], es1.union(es2))
    
            else:
              if not(len(es1) < t) or connected(q, ps[0]): continue
              for s in generate(n - 1, m, t, ps + [q], es1, (dx, dy)):
                yield s
    
    # generate clear n-circuits with a maximum total perimeter of t
    def clear_circuits(n, t):
      # consider increasing maximum leg length
      for m in irange(1, t - n + 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, t, [p0, p], set(edges(p0, p)), (1, 0)):
          yield s
    
    # generate clear 12-circuits, with a max perimeter of 21
    for (ps, es) in clear_circuits(12, 21):
      printf("{ps} length = {n}", n=len(es))
      break
    

    Solution: Yes. It is possible to find a clear 12-circuit with a length of 21.

    Here’s a nice symmetrical solution:

    Enigma 329 - Solution 2

    This has a maximum leg length of 3, and encloses 55 triangles.

    Another solution, also with a maximum leg length of 3, is:

    Enigma 329 - Solution 1

    This shape encloses 37 triangles.

    The published solution is shown below, it has a maximum leg length of 5, and encloses 41 triangles:

    Enigma 329 - Solution 3

    These shapes (along with their reflections/rotations) are the only solutions, and each has a perimeter of length 21.

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: