Enigmatic Code

Programming Enigma Puzzles

Enigma 1708: Pentagon

From New Scientist #2875, 28th July 2012 [link]

From a point on one side of a rectangular sheet of paper I drew two straight lines, one of them to a point on one adjacent side and the other to a point on the other adjacent side. My sheet of paper was now divided into two triangles and a pentagon. The lengths of the sides of the triangles were all integers, the lengths of the sides of the pentagon were, in some order, five consecutive integers, each less than 50.

What were the dimensions of the sheet of paper?

Note: It might have been clearer if the puzzle talked about the edges of the sheet of paper, rather than the sides of the corresponding rectangle.

[enigma1708]

4 responses to “Enigma 1708: Pentagon”

1. Jim Randell 25 July 2012 at 5:03 pm

Here’s my first attempt. It runs in 43ms, but I’m not entirely happy with it. I lifted the generator for Pythagorean triples from a Project Euler problem I was looking at.

Here’s a diagram to illustrate how I tackled the problem.

```import sys
from enigma import sqrt, irange, printf

# generate pythagorean triples (including non-primitive ones)
def generate():
a = 0
while True:
a += 2
n = (a * a) // 2
s = int(sqrt(n))
for b in irange(s, 1, step=-1):
(c, r) = divmod(n, b)
if r > 0: continue
yield (a + b, a + c, a + b + c)

# is this arrangement a solution?
def check(a, b, c, d, e, f):
# three sides of the pentagon are: c, f, a+d
p3 = set((c, f, a + d))
# there must be three different values, max - min less than 5
if len(p3) != 3: continue
(pmin, pmax) = (min(p3), max(p3))
if not(pmax < 50): continue
if pmax - pmin > 4: continue
# find possible 5-tuples for the pentagon
for p in irange(min(pmin, pmax - 4), max(pmin, pmax - 4)):
p5 = set(range(p, p + 5))
# what are the remaining two sides?
p2 = p5.difference(p3)
#  the difference between the two sides must be the difference between b and e
if max(p2) - min(p2) != abs(b - e): continue
# what are the dimensions of the rectangle
printf("{w}x{l} [{t1} {t2} {p5}]", w = a + d, l = (b + e + sum(p2)) // 2, t1 = (a, b, c), t2 = (d, e, f), p5 = tuple(sorted(p5)))
# and we're done
sys.exit(0)

# solve the problem
def solve():
# accumulate the pythagorean triples
tris = []
# t2
for (d, e, f) in generate():
# t1 < t2
for (a, b, c) in tris:
# try the possibilities
check(a, b, c, d, e, f)
check(b, a, c, d, e, f)
check(a, b, c, e, d, f)
check(b, a, c, e, d, f)
tris.append((d, e, f))

solve()
```

Solution: The dimensions of the sheet of paper are 37 x 66.

• Jim Randell 25 July 2012 at 7:14 pm

Here’s a slightly modified approach. It generates all possible Pythagorean triples with a hypotenuse less than 50 up front, and then checks all pairs of them. This does away with the exit() for termination, and hence checks all possible answers, instead of stopping at the first one. It runs in 37ms.

```from itertools import combinations
from enigma import sqrt, is_square, irange, printf

# pythagorean triples with hypotenuse < 50 (unnormalised)
tris = []
for h in irange(1, 49):
for a in irange(1, int(sqrt(0.5) * h)):
b = is_square(h * h - a * a)
if b is None: continue
tris.extend(((a, b, h), (b, a, h)))

for ((a, b, c), (d, e, f)) in combinations(tris, 2):
# three sides of the pentagon are: c, f, a+d
p3 = set((c, f, a + d))
# there must be three different values, max - min less than 5
if len(p3) != 3: continue
(pmin, pmax) = (min(p3), max(p3))
if not(pmax < 50): continue
if pmax - pmin > 4: continue
# find possible 5-tuples for the pentagon
for p in irange(min(pmin, pmax - 4), max(pmin, pmax - 4)):
p5 = set(range(p, p + 5))
# what are the remaining two sides?
p2 = p5.difference(p3)
# difference between the two sides = difference between b and e
if max(p2) - min(p2) != abs(b - e): continue
# what are the dimensions of the rectangle
printf("{w}x{l} [{t1} {t2} {p5}]", w = a + d, l = (b + e + sum(p2)) // 2, t1 = (a, b, c), t2 = (d, e, f), p5 = tuple(sorted(p5)))
```
2. arthurvause 25 July 2012 at 7:42 pm

I probably should have done this one in SQL, but here is some Python:

```squares = {n*n:n for n in range(5,50)}
pythag = [(a,b,squares[a*a+b*b]) for a in range(3,50) for b in range(3,50) if a*a+b*b in squares]
candidates = [(p[0]+q[0],p[2],q[2],p[1],q[1]) for p in pythag for q in pythag
if 0 < abs(p[2]-q[2])<5
and 0<abs(p[0]+q[0]-p[2])<5
and 0<abs(p[0]+q[0]-q[2])<5
and 0 < abs(p[1]-q[1])<5
and p[2]<q[2]
]

for s in range(1,100):
for c in candidates:
pent = (c[0],c[1],c[2],s-c[3],s-c[4])
if len(set(pent))==5 and min(pent)+4==max(pent):
print "Paper dimensions are:", c[0],s
```
3. Naim Uygun 29 July 2012 at 8:55 pm
```"""
New Scientist Enigma 1708
The dimensions of the rectangular sheet are:
Width=37
Length=66
Right angled triangles are: (16,30,34), (21,28,35)
Pentagon sides are (34,35,36,37,38)

"""

for length in range(99,5,-1):

for a in range(1,50):
for b in range(1,50):
for c in range(1,50):
if   a**2+b**2 != c**2 : continue

for d in range(1,50):
for  e in range(1,50):
for f in range(1,50):
if d**2+e**2 != f**2: continue

if length-e >=50: continue
if length-b>=50: continue
if a+d>=50:continue
l=set()