# Enigmatic Code

Programming Enigma Puzzles

## Enigma 329: Clear short circuit

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

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:

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

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

This shape encloses 37 triangles.

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

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

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