Teaser 3076: Bee lines
From The Sunday Times, 5th September 2021 [link] [link]
Three bees are each trapped inside an empty cuboidal box, each box of a different size, none of whose faces are squares. The lengths of the internal edges of each box in centimetres are whole numbers, and the volume of each box is no more than a litre. Starting at a corner, each bee moves only in straight lines, from corner to corner, until it has moved along every edge of its box. The only points a bee visits more than once are corners of its box, and the total distance moved by each bee is a whole number of centimetres. Given the above, the sum of these three distances is as small as it could be.
What is the sum of the distances that the bees moved?
[teaser3076]
GeoffR, 
Frits, and 1 other are discussing. 
S2T2 
Jim Randell 5:40 pm on 3 September 2021 Permalink |
After a couple of false starts I think I have found the answer.
We assume the bees are points of negligible size travelling along the inside edges and faces of the boxes, which have internal integer dimensions. [Note: This may not be what the setter intends, see my additional comment below].
If the cuboid has (increasing, internal) dimensions x, y, z, then in order to traverse all 12 edges (distance = 4x + 4y + 4z)) we need to also traverse the diagonals of 3 of the faces (as we do not need to form a closed path). So we need the diagonals of (at least) two of the three different face shapes to have integer values.
This Python program looks for viable cuboid shapes, and then finds three with the shortest distances traversed. It runs in 62ms.
Run: [ @replit ]
from enigma import (irange, is_square, subsets, group, unpack, printf) # integer diagonal? diag = lambda *vs: is_square(sum(v * v for v in vs)) # find possible cuboid dimensions (x, y, z) and distance traversed d # return (x, y, z, d) def generate(): for z in irange(3, 499): for y in irange(2, z - 1): if not (y * z < 1000): break dyz = diag(y, z) for x in irange(1, y - 1): if not (x * y * z < 1000): break dxy = diag(x, y) dxz = diag(x, z) # calculate paths d = 4 * (x + y + z) for (a, b) in subsets(filter(None, (dxy, dxz, dyz)), size=2): dx = 2 * a + b yield (x, y, z, d + dx) # group cuboids by distance g = group(generate(), by=unpack(lambda x, y, z, d: d)) # find 3 different cuboids with the smallest distances ss = set() t = 0 for k in sorted(g.keys()): for (x, y, z, d) in g[k]: if (x, y, z) not in ss: ss.add((x, y, z)) t += d printf("[{n}: ({x}, {y}, {z}) -> {d}]", n=len(ss)) if len(ss) == 3: printf("total distance = {t}") if len(ss) >= 3: breakThe program above finds minimal paths where the bee is constrained to the interior surface of the box, but if the bee is permitted to fly between diametrically opposite corners of the box we get a different answer (see comment below for modified program).
Solution: The sum of the distances is 397 cm.
The net of a cuboid has 8 vertices, each with three edges to other vertices. In order to make a continuous path we need there to be only two vertices of odd order (for the start and finish of the path), or all vertices to be even (for a path that starts and finishes at the same vertex).
Adding a diagonal link between two vertices, can reduce the number of even vertices by 2. Hence by adding in three diagonals between different vertices we can make a net with two vertices of odd order, which can be traversed (with these vertices as the start and finish of the path).
We need to traverse all 12 edges, and an additional 3 diagonals, giving a minimum path of 15 lines. We can’t use diagonals that have points in common (e.g. we can only cross a face once), as the only points the bee is allowed to revisit are the vertices.
Here is a diagram showing the traversal of the edges of a cuboid in 15 lines, using three “face” diagonals:
(The path could be closed by traversing the diagonal cross the front of the box, but this is not required by the puzzle, and wouldn’t provided a minimal length path).
To minimise the length of the path we want the paths that cross opposite faces (i.e. 6 and 14) to be the shortest available diagonal, and the remaining diagonal (i.e. 8) to be the next shortest.
We find there are three viable boxes for this method:
Together these constitute the answer if the bee is restricted to crossing the interior surface of the box, and give a total of 476 cm.
However, if we suppose the bee is permitted to fly (in a straight line) between diametrically opposite corners of the box (the puzzle text isn’t explicit on whether this is allowed or not), then there is another potential family of paths:
Here the “space” diagonal through the interior space of the box is shown as a curved line, but the bee travels in a straight line between opposite vertices. And all four of the “space” diagonals meet at the central point of the cuboid, so we can only use one of them.
(In this case closing the path would require traversing another “space” diagonal, so is not possible).
This method provides another two viable boxes:
Using the smallest of these, along with the smallest 2 previously found boxes gives a total distance of 397 cm.
This latter distance is the published solution, so the bee must be allowed to fly (in a straight line) between diametrically opposite corners.
LikeLike
Frits 10:53 pm on 3 September 2021 Permalink |
@Jim, I don’t know what you mean by “three edges”. I have the feeling your first solution was better (as I can visualize the route of the bee and it has a smaller distance).
“no more than a litre” can be coded more accurately.
LikeLike
Jim Randell 9:05 am on 4 September 2021 Permalink |
@Frits: I realised that the path my previous solution was based on didn’t meet all the necessary requirements of the puzzle, so I had to revise my approach. (Which gave a longer, but more correct answer).
Once a viable path for traversing the edges of the cuboid is worked out, you can proceed to look for paths which have integer lengths. (I’m going to put the path I worked out up with the solution, but if you want to see it now it is [here]).
The only slightly worrying thing is that the part about minimising the sum. With my current approach there are only three possible boxes, so only one possible sum.
LikeLike
Jim Randell 11:15 am on 4 September 2021 Permalink |
I think the minimal sum comes about because there are longer possible paths on the same cube. (We can generate these by adding a [[
select="P"]] parameter to the [[subsets()]] call on line 15. Without this it only generates the shorter variants).LikeLike
Jim Randell 10:13 pm on 4 September 2021 Permalink |
If the bee is allowed to travel (fly) along a path through the centre of the cube to the opposite corner (something my original approach did not allow), we can adapt the program to include this diagonal as follows:
Run: [ @replit ]
from enigma import (irange, is_square, group, unpack, printf) # integer diagonal? diag = lambda *vs: is_square(sum(v * v for v in vs)) # find possible cuboid dimensions (x, y, z) and minimal distance traversed d # return (x, y, z, d) def generate(): for z in irange(3, 499): for y in irange(2, z - 1): if not (y * z < 1000): break dyz = diag(y, z) for x in irange(1, y - 1): if not (x * y * z < 1000): break dxy = diag(x, y) dxz = diag(x, z) dxyz = diag(x, y, z) # calculate minimal path ds = list(x for x in (dxy, dxz, dyz, dxyz) if x is not None) if len(ds) > 1: (a, b) = ds[:2] yield (x, y, z, 4 * (x + y + z) + 2 * a + b) # group cuboids by distance g = group(generate(), by=unpack(lambda x, y, z, d: d)) # find 3 different cuboids with the smallest distances n = t = 0 for k in sorted(g.keys()): for (x, y, z, d) in g[k]: n += 1 t += d printf("[{n}: ({x}, {y}, {z}) -> {d}]") if n == 3: printf("total distance = {t}") if n >= 3: breakThis brings 2 more cuboids in to play, so there are now 5 to choose from.
This is probably the scenario intended by the setter.
(Although maybe the bee could cross a face diagonally in one direction by walking, and cross it in the other direction by flying, and thereby avoid visiting the centre of the face twice. This would bring me full circle back to my original (abandoned) approach where the bee crosses one face by 2 different diagonals).
LikeLike
Jim Randell 1:02 pm on 5 September 2021 Permalink |
I also wrote a program that performs an exhaustive search for the minimal path on each cuboid [@replit], which verifies that the programs above do find the minimal length paths in the cases where the space diagonal isn’t or is allowed.
from enigma import (irange, inf, Accumulator, is_square, group, unpack, printf) # vertices are labelled: 0 - 8 # moves are labelled by midpoints 0-19 (0 = n/a, +12 edges, +6 faces, +1 centre) # matrix of vertex to vertex moves, values = midpoints move = [ # 0 1 2 3 4 5 6 7 [ 0, 1, 13, 4, 15, 19, 16, 9 ], # 0 [ 1, 0, 2, 13, 19, 17, 10, 16 ], # 1 [ 13, 2, 0, 3, 18, 11, 17, 19 ], # 2 [ 4, 13, 3, 0, 12, 18, 19, 15 ], # 3 [ 15, 19, 18, 12, 0, 5, 14, 8 ], # 4 [ 19, 17, 11, 18, 5, 0, 6, 14 ], # 5 [ 16, 10, 17, 19, 14, 6, 0, 7 ], # 6 [ 9, 16, 19, 15, 8, 14, 7, 0 ], # 7 ] # find minimal path, visiting tgt midpoints # ws = weights for each midpoint 0-19, (0 for invalid midpoints) # tgt = target midpoints to collect # vs = vertices visited so far # r = accumulator for minimal path # ms = midpoints visited (so far) # t = total weight of path (so far) def path(ws, tgt, vs, r, ms=set(), t=0): # are we done? if tgt.issubset(ms): r.accumulate_data(t, vs) else: # extend the path for (v, m) in enumerate(move[vs[-1]]): if (not m) or (not ws[m]) or m in ms: continue t_ = t + ws[m] if not (t_ > r.value): path(ws, tgt, vs + [v], r, ms.union([m]), t_) # integer diagonal? diag = lambda *vs: is_square(sum(v * v for v in vs)) # find possible cuboid dimensions (x, y, z) and minimal distance traversed d # return (x, y, z, d) def generate(): for z in irange(3, 499): for y in irange(2, z - 1): if not (y * z < 1000): break dyz = diag(y, z) for x in irange(1, y - 1): if not (x * y * z < 1000): break dxy = diag(x, y) dxz = diag(x, z) dxyz = diag(x, y, z) # calculate minimal weight path, visiting all edges of the cuboid ws = [0, x, y, x, y, x, y, x, y, z, z, z, z, dxy, dxy, dyz, dxz, dyz, dxz, dxyz] tgt = set(irange(1, 12)) r = Accumulator(fn=min, value=inf) path(ws, tgt, [0], r) if r.value < inf: printf("({x}, {y}, {z}) -> {r.value}") yield (x, y, z, r.value) # group cuboids by distance g = group(generate(), by=unpack(lambda x, y, z, d: d)) # find 3 different cuboids with the smallest distances n = t = 0 for k in sorted(g.keys()): for (x, y, z, d) in g[k]: n += 1 t += d printf("[{n}: ({x}, {y}, {z}) -> {d}]") if n == 3: printf("total distance = {t}") if n >= 3: break(To disallow the space diagonal replace [[
dxyz]] with [[0]] on line 54).LikeLike
Brian Gladman 8:37 am on 4 September 2021 Permalink |
@Frits I don’t know what Jim’s earlier answer was but my current answer agrees with Jim’s current one. However, I must admit that I got there after a lot of path sketching to find the form of the shortest path and it is quite possible that I have missed a shorter arrangement.
LikeLike
Frits 1:42 pm on 4 September 2021 Permalink |
If we need to traverse the diagonals of (at least) two of the three different face shapes we can look for Pythagorean triples that share a non-hypotenuse side.
from enigma import pythagorean_triples pt = list(pythagorean_triples(200)) s = set() # check if pythogorean triples share a non-hypotenuse side for p1 in pt: for p2 in pt: if p2 == p1: continue if p1[0] in p2[:2]: match = p1[0] elif p1[1] in p2[:2]: match = p1[1] else: continue n3 = p2[0] if p2[1] == match else p2[1] if p1[0] * p1[1] * n3 <= 1000: d = 4 * (p1[0] + p1[1] + n3) + 2 * (min(p1[2], p2[2])) + max(p1[2], p2[2]) s.add((d, ) + tuple(sorted([p1[0], p1[1], n3]))) # more than 3 boxes? if len(s) > 2: sol = sorted(s)[:3] print("answer:", sum(x[0] for x in sol)) for x in sol: print(x[1:], "with distance", x[0])LikeLike
GeoffR 7:25 am on 7 September 2021 Permalink |
I realise that my code can probably be shortened, but I wanted to show the full workings of this solution and therefore code optimisation was of secondary importance to me. My solution finds the five cuboids mentioned and the three minimum cuboids for the triple flight path solution.
from itertools import combinations C = [] # list of cuboid flight path totals from math import isqrt def is_sq(x): return isqrt(x) ** 2 == x # consider possible cuboid dimensions for a, b, c in combinations(range(3, 50), 3): # each cuboid is less than one litre in volume if a * b * c <= 1000: # identify types of squares from dimensions a, b and c s1 = a*a + b*b s2 = a*a + c*c s3 = b*b + c*c s4 = a*a + b*b + c*c # separate research showed there were just two squares for each path if sum([is_sq(s1), is_sq(s2), is_sq(s3), is_sq(s4)]) == 2: # Type s1 and s2 squares contribute if is_sq(s1) and is_sq(s2): path = 4 *(a + b + c) + 2 * isqrt(a*a + b*b) + isqrt(a*a + c*c) C.append(path) # Type s1 and s3 squares contribute if is_sq(s1) and is_sq(s3): path = 4 *(a + b + c) + 2 * isqrt(a*a + b*b) + isqrt(b*b + c*c) C.append(path) # Type s1 and s4 squares contribute if is_sq(s1) and is_sq(s4): path = 4 *(a + b + c) + 2 * isqrt(a*a + b*b) + isqrt(a*a + b*b + c*c) C.append(path) # Type s2 and s3 squares contribute if is_sq(s2) and is_sq(s3): path = 4 *(a + b + c) + 2 * isqrt(a*a + c*c) + isqrt(b*b + c*c) C.append(path) # Type s2 and s4 squares contribute if is_sq(s2) and is_sq(s4): path = 4 *(a + b + c) + 2 * isqrt(a*a + c*c) + isqrt(a*a + b*b + c*c) C.append(path) # Type s3 and s4 squares contribute if is_sq(s3) and is_sq(s4): path = 4 *(a + b + c) + 2 * isqrt(b*b + c*c) + isqrt(a*a + b*b + c*c) C.append(path) # A sorted list of flight path totals C = sorted(C) # find minimum sum of three flight paths Min_FP = C[0] + C[1] + C[2] print(f"All possible flight path lengths = {C} cm.") print(f"Length of three shortest flight paths = {Min_FP} cm.")LikeLike