Sunday Times Teaser 2840 – Signs of the Times

Brian Gladman permalink

There are multiple solutions, of which it seems likely that the intended answer is the one with the smallest distance to Secombe.


from itertools import combinations

# consider squares up to the square of this value
maxr = 20

# map perfect squares to the set of differences between them and all lower ones
gaps = {x * x: set(x * x - y * y for y in range(1, x)) for x in range(1, maxr)}
         
# the distance to Firsk (f) and Secombe (s) on the first signpost
for fr, sr in combinations(range(1, maxr), 2):
  f, s = fr ** 2, sr ** 2
  # now find distances to other signposts that make the signposted
  # distances to Firsk and Secombe both square
  dists = sorted(gaps[f] & gaps[s])
  # find two such positions for which all six distances are different
  for x, y in combinations(dists, 2):
    sp = (f, s, f - x, s - x, f - y, s - y)
    if len(set(sp)) == 6:
      print(f'{(f, s)} - [{s-f:3}, {y-x}, {x:3}] => {(f-x, s-x)}, {(f-y, s-y)}')

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

from itertools import combinations

# consider squares up to the square of this value

maxr = 20

# map perfect squares to the set of differences between them and all lower ones

gaps = {x * x: set(x * x - y * y for y in range(1, x)) for x in range(1, maxr)}

# the distance to Firsk (f) and Secombe (s) on the first signpost

for fr, sr in combinations(range(1, maxr), 2):

f, s = fr ** 2, sr ** 2

# now find distances to other signposts that make the signposted

# distances to Firsk and Secombe both square

dists = sorted(gaps[f] & gaps[s])

# find two such positions for which all six distances are different

for x, y in combinations(dists, 2):

sp = (f, s, f - x, s - x, f - y, s - y)

if len(set(sp)) == 6:

print(f'{(f, s)} - [{s-f:3}, {y-x}, {x:3}] => {(f-x, s-x)}, {(f-y, s-y)}')

and here is an alternative approach


from itertools import combinations
from collections import defaultdict

# consider squares up to the square of this value
maxr = 20

# record pairs of squares according to their difference
# (which is the distance between Firsk and Secombe)
dif = defaultdict(set)
for a, b in combinations(range(1, maxr), 2):
  dif[b * b - a * a].add((a, b))

# consider increasing distances between Firsk and Secombe 
for d in sorted(dif.keys()):
  # we need three pairs of squares for the three signposts 
  if len(dif[d]) > 2:
    # look for three signposts with six different squares
    for p in combinations(dif[d], 3):
      s6 = (y for x in p for y in x)
      if len(set(s6)) == 6:
        p2, p1, p0 = sorted([(x * x, y * y) for x, y in sorted(p)])
        x, y = (p1[0] - p2[0]), (p0[0] - p1[0])
        print(f'{p0} - [{d:3}, {x:3}, {y:3}] => {p1}, {p2}')

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

from itertools import combinations

from collections import defaultdict

# consider squares up to the square of this value

maxr = 20

# record pairs of squares according to their difference

# (which is the distance between Firsk and Secombe)

dif = defaultdict(set)

for a, b in combinations(range(1, maxr), 2):

dif[b * b - a * a].add((a, b))

# consider increasing distances between Firsk and Secombe

for d in sorted(dif.keys()):

# we need three pairs of squares for the three signposts

if len(dif[d]) > 2:

# look for three signposts with six different squares

for p in combinations(dif[d], 3):

s6 = (y for x in p for y in x)

if len(set(s6)) == 6:

p2, p1, p0 = sorted([(x * x, y * y) for x, y in sorted(p)])

x, y = (p1[0] - p2[0]), (p0[0] - p1[0])

print(f'{p0} - [{d:3}, {x:3}, {y:3}] => {p1}, {p2}')

It has been suggested on my other Sunday Times Teaser website that the differences between squares on each signpost don’t need to be the same because they are only listed to the nearest mile. I don’t consider this possibility above but I think it is reasonable since distances of hundreds of miles don’t equate to a “gentle morning drive”. So here is a solution that considers this possibility, one which produces a more likely answer. This currently does more work than is necessary so I might tidy it up later (I might not!).


from itertools import combinations

is_square = lambda x: int(x ** 0.5 + 0.5) ** 2 == x

# for pairs of miles on signposts
pairs = set()

# consider distances between Firsk and Secombe and between
# Firsk and a signpost that are not whole numbers of miles

# the distance between Firsk and Secombe in 1/2 mile steps 
for s2f in range(1, 40):
  sf = s2f / 2
  # the distance between Firsk and a signpost in 1/2 mile steps
  for f2p in range(1, 120):
    fp = f2p / 2
    # round the distances to Firsk and Secombe for the signpost
    f_p, s_p = round(fp), round(sf + fp)
    # record them if they are different non-zero squares
    if is_square(f_p) and is_square(s_p):
      if s_p and f_p and f_p != s_p:
        pairs.add((f_p, s_p))                           

# consider three signposts
for p in combinations(sorted(pairs), 3):
  # where the differences between the miles on each
  # signpost differ by at most one
  dd = set(abs(x - y) for x, y in p)
  if max(dd) - min(dd) < 2:
    # look for six different squares
    s6 = [y for x in p for y in x]
    if len(set(s6)) == 6 and max(s6) < 100:
      p2, p1, p0 = p
      x, y, d = (p1[0] - p2[0]), (p0[0] - p1[0]), p0[1] - p0[0]
      print(f'{p0} - [~{d}, ~{x}, ~{y}] => {p1}, {p2}')

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

from itertools import combinations

is_square = lambda x: int(x ** 0.5 + 0.5) ** 2 == x

# for pairs of miles on signposts

pairs = set()

# consider distances between Firsk and Secombe and between

# Firsk and a signpost that are not whole numbers of miles

# the distance between Firsk and Secombe in 1/2 mile steps

for s2f in range(1, 40):

sf = s2f / 2

# the distance between Firsk and a signpost in 1/2 mile steps

for f2p in range(1, 120):

fp = f2p / 2

# round the distances to Firsk and Secombe for the signpost

f_p, s_p = round(fp), round(sf + fp)

# record them if they are different non-zero squares

if is_square(f_p) and is_square(s_p):

if s_p and f_p and f_p != s_p:

pairs.add((f_p, s_p))

# consider three signposts

for p in combinations(sorted(pairs), 3):

# where the differences between the miles on each

# signpost differ by at most one

dd = set(abs(x - y) for x, y in p)

if max(dd) - min(dd) < 2:

# look for six different squares

s6 = [y for x in p for y in x]

if len(set(s6)) == 6 and max(s6) < 100:

p2, p1, p0 = p

x, y, d = (p1[0] - p2[0]), (p0[0] - p1[0]), p0[1] - p0[0]

print(f'{p0} - [~{d}, ~{x}, ~{y}] => {p1}, {p2}')

Reply

Jim Randell permalink

Here’s a solution that uses intervals, so that the distances involved don’t have to be integral numbers of miles.

By default the distances given on the signs is limited to be below 100 miles, which gives a unique solution in 47ms (but this limit can be specified on the command line).


from itertools import combinations
from enigma import irange, isqrt, arg, printf

# limit to numbers on signs
M = arg(100, 0, int)

# possible squares that can appear on the signs
squares = list(i * i for i in irange(1, isqrt(M - 1)))

# possible distances for three signs (in order)
signs = combinations(squares, 3)

# combine lower/upper bounds into an interval
def interval(v, *vs):
  (l, u) = v
  for (l1, u1) in vs:
    (l, u) = (max(l, l1), min(u, u1))
  return (l, u)

# choose squares for the distances to F and S on the signs
for ((f1, f2, f3), (s1, s2, s3)) in combinations(signs, 2):

  # check the distances are all different
  if len(set((f1, f2, f3, s1, s2, s3))) < 6: continue

  # calculate the position of S is
  (sl, su) = interval(
    (s1 - f1 - 1, s1 - f1 + 1),
    (s2 - f2 - 1, s2 - f2 + 1),
    (s3 - f3 - 1, s3 - f3 + 1),
  )

  if 0 < sl < su:
    printf("signs = ({f1} {s1}) ({f2} {s2}) ({f3} {s3}), F -> S = ({sl}, {su})")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

from itertools import combinations

from enigma import irange, isqrt, arg, printf

# limit to numbers on signs

M = arg(100, 0, int)

# possible squares that can appear on the signs

squares = list(i * i for i in irange(1, isqrt(M - 1)))

# possible distances for three signs (in order)

signs = combinations(squares, 3)

# combine lower/upper bounds into an interval

def interval(v, *vs):

(l, u) = v

for (l1, u1) in vs:

(l, u) = (max(l, l1), min(u, u1))

return (l, u)

# choose squares for the distances to F and S on the signs

for ((f1, f2, f3), (s1, s2, s3)) in combinations(signs, 2):

# check the distances are all different

if len(set((f1, f2, f3, s1, s2, s3))) < 6: continue

# calculate the position of S is

(sl, su) = interval(

(s1 - f1 - 1, s1 - f1 + 1),

(s2 - f2 - 1, s2 - f2 + 1),

(s3 - f3 - 1, s3 - f3 + 1),

)

if 0 < sl < su:

printf("signs = ({f1} {s1}) ({f2} {s2}) ({f3} {s3}), F -> S = ({sl}, {su})")

The enigma.py library is available at [ https://www.magwag.plus.com/jim/enigma.html ].

Reply

Trevor Kirsten permalink

If we limit the morning drive to 200 miles then here is my exact solution:


# let a,b & c be the square roots of the distances to Secombe
# and d,e & f (                   "                 ) Firsk
# on the 1st,2nd & 3rd signposts resp. 
for a in range (3,15):
  for b in range (2,a):
    for c in range (1,b):
      for d in range (3,a):
        for e in range (2,b):
          for f in range (1,c):
            if a*a-d*d == b*b-e*e == c*c-f*f and b!=(d or f) and c!=(d or e) :  
              print(a*a,d*d,b*b,e*e,c*c,f*f)

1

2

3

4

5

6

7

8

9

10

11

12

13

# let a,b & c be the square roots of the distances to Secombe

# and d,e & f ( " ) Firsk

# on the 1st,2nd & 3rd signposts resp.

for a in range (3,15):

for b in range (2,a):

for c in range (1,b):

for d in range (3,a):

for e in range (2,b):

for f in range (1,c):

if a*a-d*d == b*b-e*e == c*c-f*f and b!=(d or f) and c!=(d or e) :

print(a*a,d*d,b*b,e*e,c*c,f*f)

And if we prefer a more gentler drive of less than 100 miles then here is the modified code for signposts to the nearest mile:


# let a,b & c be the square roots of the distances to Secombe
# and d,e & f (                   "                 ) Firsk
# on the 1st,2nd & 3rd signposts resp. 
for a in range (3,10):
  for b in range (2,a):
    for c in range (1,b):
      for d in range (3,a):
        for e in range (2,b):
          for f in range (1,c):
            if -1<=((a*a-d*d)-(b*b-e*e))<=1 and -1<=((a*a-d*d)-(c*c-f*f))<=1 \
            and b!=(d or f) and c!=(d or e) :  
              print(a*a,d*d,b*b,e*e,c*c,f*f)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

# let a,b & c be the square roots of the distances to Secombe

# and d,e & f ( " ) Firsk

# on the 1st,2nd & 3rd signposts resp.

for a in range (3,10):

for b in range (2,a):

for c in range (1,b):

for d in range (3,a):

for e in range (2,b):

for f in range (1,c):

if -1<=((a*a-d*d)-(b*b-e*e))<=1 and -1<=((a*a-d*d)-(c*c-f*f))<=1 \

and b!=(d or f) and c!=(d or e) :

print(a*a,d*d,b*b,e*e,c*c,f*f)

Reply

Sunday Times Teaser 2840 – Signs of the Times

by Victor Bryant

Published February 26 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta