# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1427: Equal lengths

From New Scientist #2588, 27th January 2007

I challenged Harry and Tom to draw this diagram, with the angles ABD, BEC and CED each 90° and each side of the three triangles an integral number (less than 40) of centimetres long. They each managed to do this.

In Harry’s version (AB+BC) was the same length as (AD+DC); in Tom’s version (AB+BE) was the same length as (AD+DE); CE was the same length in both versions.

What was the length of the perimeter of the quadrilateral ABCD in (a) Harry’s version, (b) Tom’s version?

[enigma1427]

### 5 responses to “Enigma 1427: Equal lengths”

1. Jim Randell 26 May 2013 at 9:40 am

This Python program examines all possible combinations of Pythagorean triangles with hypotenuse less than 40 to find the answer. It runs in 51ms.

```from collections import defaultdict
from itertools import product
from enigma import irange, printf

# find pythagorean triples with a hypotenuse less than 40
ts = list()
for c in irange(1, 39):
for b in irange(1, c - 1):
for a in irange(1, b - 1):
if a * a + b * b == c * c:
ts.append((a, b, c))

# now find pairs of triangles with a matching non-hypotenuse side
(Hs, Ts) = (list(), list())
for (X, Y) in product(ts, repeat=2):
# match the sides
for (x, y) in product((0, 1), repeat=2):
if X[x] != Y[y]: continue
# sum the non-matching non-hypotenuse sides
s = X[x ^ 1] + Y[y ^ 1]
# find a matching Z
for Z in ts:
for z in (0, 1):
if Z[z] != s: continue
# check the conditions
(AB, BC, BE, CE, AD, DC, DE) = (Z[z ^ 1], Y, Y[y ^ 1], X[x], Z, X, X[x ^ 1])
p = AB + BC + DC + AD
# for Harry:
if (AB + BC == AD + DC):
Hs.append((CE, p, (X, Y, Z)))
printf("[H: {X} {Y} {Z} / {x} {y} {z} / CE={CE} p={p}]")
# for Tom: AB + BE = AD + DE
if (AB + BE == AD + DE):
Ts.append((CE, p, (X, Y, Z)))
printf("[T: {X} {Y} {Z} / {x} {y} {z} / CE={CE} p={p}]")

# choose H and T
for (H, T) in product(Hs, Ts):
# CE is the same
if H != T: continue

printf("pH={H} pT={T} [H={H} T={T}]")
```

Solution: (a) 90 cm; (b) 76 cm.

2. Ahmet Saracoğlu 31 May 2013 at 1:07 pm

In my machine which has 2.6 Ghz processor, the execution time is 16ms.

```import time
time1=int(round(time.time()*1000))
print(time1)
Hip=[5,10,15,20,25,30,35,13,26,39,17,34,29,37]# These are the biggest side of the triangles

import itertools as permt
permus=list(permt.permutations(Hip,3))

def FindTwoCircumferences():
c,d,counter=0,0,0
satisfier=[[0 for i in range(2)]for i in range(20)]
circumference=dict()
#print(satisfier)
for i in range(len(permus)):
e,b,f=permus[i],permus[i],permus[i]
a=e+f-b
if a in range(40):#Every side must be less than 40."
root=pow(pow(e,2)-pow(a,2),0.5).real
if int(root)==root:
cminusd=(b-f)*(b+f)//root#this equation comes from c^2+h^2=b^2 and d^2+h^2=f^2
c=(root+cminusd)//2# root denotes for c+d and c can be found easly by solving the eq.
d=root-c
h1,h2=pow(pow(b,2)-pow(c,2),0.5).real,pow(pow(f,2)-pow(d,2),0.5).real
if int(h1)==h1 and h1>0 and h1==h2 :
#print(a+b+e+f,a,b,e,f,h1)
for j in range(len(Hip)):
hip=Hip[j]
if h1<hip:
diff=pow(hip,2)-pow(h1,2)
c1=pow(diff,0.5).real
if int(c1)==c1:
satisfier[counter],satisfier[counter]=c1,h1
circumference.update({h1:a+b+e+f})
counter+=1

#This part is for the other circumference
for i in range(counter):
for j in range(counter):
c,d=satisfier[i],satisfier[j]
if c>d and satisfier[i]==satisfier[j]:
aminuse=d-c
for k in range(len(Hip)):
cplusd=c+d
hip=Hip[k]
if cplusd<hip:
a=aminuse+hip
#print(a,c1,d1,hip,cplusd,satisfier[j])

if (pow(hip,2)-pow(cplusd,2))==pow(a,2):
h=satisfier[j]
hsquare=pow(h,2)
b,f=pow(pow(c,2)+hsquare,0.5).real,pow(pow(d,2)+hsquare,0.5).real
print("CIRC1:",a+b+e+f,"CIRC2:",circumference[h])

FindTwoCircumferences()
time2=int(round(time.time()*1000))
print(time2)
print("s",time2-time1)
```
3. geoffrounce 29 October 2017 at 11:18 am

Triangles BEC and DEC are the same for Tom and Harry. Only triangle ABD is different between them. To get Tom’s solution I had to comment out Harry’s constraint and output line – vice versa to get Harry’s solutions, for which the code is relevant.

Only Tom’s perimeter of 76 cm and Harry’s perimeter of 90 cm have the same value of EC (or CE)

```% A Solution in MiniZinc
include "globals.mzn";

var 1..40:AB;   var 1..40:BD;   var 1..40:AD;   var 1..40:BC;
var 1..40:CD;   var 1..40:BE;   var 1..40:ED;   var 1..40:EC;

var 4..160:ABCD = AB + BC + CD + AD;   % perimeter of quadrilateral ABCD

% Triangle square constraints
constraint AB * AB + BD * BD = AD * AD;
constraint BE * BE + EC * EC = BC * BC;
constraint ED * ED + EC * EC = CD * CD;

constraint BD = BE + ED;

% Harry's constraint
constraint AB + BC = AD + CD;

% Tom's constraint
%constraint AB + BE = AD + ED;

solve satisfy;

%output [ "Tom's perimeter ABCD = " ++ show(ABCD)]
output [ "Harry's perimeter ABCD = " ++ show(ABCD)]
++     [ ":  (AB,BD,AD) = " ++ show(AB) ++ " " ++ show(BD) ++ " " ++ show(AD) ]
++     [ ",  (BC,BE,EC) = " ++ show(BC) ++ " " ++ show(BE) ++ " " ++ show(EC) ]
++     [ ",  (CD,ED,EC) = " ++ show(CD) ++ " " ++ show(ED) ++ " " ++ show(EC) ] ;

% Multiple Output Configuration
% Tom's perimeter ABCD = 76:  (AB,BD,AD) = 20 21 29,  (BC,BE,EC) = 17 15 8,  (CD,ED,EC) = 10 6 8
%----------------
% Harry's perimeter ABCD = 90:  (AB,BD,AD) = 28 21 35,  (BC,BE,EC) = 17 15 8,  (CD,ED,EC) = 10 6 8
% ----------
% Harry's perimeter ABCD = 96:  (AB,BD,AD) = 28 21 35,  (BC,BE,EC) = 20 16 12,  (CD,ED,EC) = 13 5 12
% Finished in 55msec

```
4. Brian Gladman 29 October 2017 at 3:16 pm

Using Google’s Python interface to their Google Optimization Tools (or Jim’s MiniZinc wrapper), it is straightforward to produce a full constraint programming solution to this puzzle.

```from ortools.constraint_solver import pywrapcp
from collections import defaultdict

# 1. Set up the solver
solver = pywrapcp.Solver('Sunday Times Teaser 2875')

# 2. Create the model variables
AB, BD, AD, BC, CD, BE, ED, EC = vars = [solver.IntVar(1, 40, x) for x in
'AB BD AD BC CD BE ED EC'.split()]
ABCD = solver.IntVar(4, 160, 'ABCD')
all_vars = vars + [ABCD]

# 3. Set up the constraints
solver.Add(BE * BE + EC * EC == BC * BC)
solver.Add(ED * ED + EC * EC == CD * CD)

# index solutions on the length of EC
ec_to_sol = defaultdict(list)

# 4. Initialise the solver
solution = solver.Assignment()
solver.NewSearch(solver.Phase(all_vars, solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE))
# 5. Find possible solutions
while solver.NextSolution():
ab, bd, ad, bc, cd, be, ed, ec = [x.Value() for x in
(AB, BD, AD, BC, CD, BE, ED, EC)]
# record solutions for Harry
if ab + bc == ad + cd:
ec_to_sol[EC.Value()].append(('H', ABCD.Value()))
# record solutions for Tom
if ab + be == ad + ed:
ec_to_sol[EC.Value()].append(('T', ABCD.Value()))
solver.EndSearch()

# look for solutions for both Harry and Tom with the same EC length
for ce, sl in ec_to_sol.items():
if len(sl) > 1:
h, t = ([y for x, y in sl if x == c] for c in 'HT')
if len(h) == len(t) == 1:
print(f'(a) {h}cm (b) {t}cm.')
else:
print(f'Multiple solutions: (a) {h}cm (b) {t}cm.')
```
5. Jim Randell 4 November 2017 at 7:50 am

A blast from the past!

Here’s a MiniZinc model that generates possibilities for Harry’s and Tom’s triangles as output. It runs in 67ms (using the [[ `mzn-gecode -a` ]] solver).

```%#! mzn-gecode -a

% triangle CED
var 1..39: CE;
var 1..39: DE;
var 1..39: CD;
constraint CE * CE + DE * DE = CD * CD;

% triangle BEC
var 1..39: BE;
var 1..39: BC;
constraint BE * BE + CE * CE = BC * BC;

% triangle ABD
var 1..39: AB;
var 1..39: BD = BE + DE;
constraint AB * AB + BD * BD = AD * AD;

% we only need candidates for Harry and Tom
constraint (AB + BC = AD + CD) \/ (AB + BE = AD + DE);

solve satisfy;
```

In fact there is only one possible triangle for Tom. There are two possible triangles for Harry, but only one of them has the same CE length as Tom’s triangle.

The following Python program executes the above MiniZinc code and analyses the output to find matching possibilities for Tom and Harry. It uses the minizinc.py wrapper library (which, of course, I hadn’t written in 2013 when this puzzle was posted to the site). The overall execution time is 132ms.

```from collections import defaultdict
from enigma import printf
from minizinc import MiniZinc;

# load the minizinc model for possible diagrams
p = MiniZinc("enigma1427.mzn")

# record perimters by CE for Harry and Tom
Hs = defaultdict(list)
Ts = defaultdict(list)

# record results
n = 0
for (AB, AD, BC, BE, CD, CE, DE) in p.solve(result="AB AD BC BE CD CE DE"):
if AB + BC == AD + CD:
# Harry's diagram
Hs[CE].append(AB + BC + CD + AD)
if AB + BE == AD + DE:
# Tom's diagram