1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
# Valid links in a 'daisy-chain' OK = {"01", "18", "21", "38", "58", "79", "82", "83", "98"} def is_daisy(n): s, l, j = str(n), len(str(n)), set() for i in range(l - 1): j.add(s[i] + s[i + 1] in OK) return all(j) # Structure 'looped daisy-chains' are head + body + tail # # body = (8 + 3)*n or (8 + 2 + 1)*n ie allways 11*n # # 1 + 11*n + 8 + 2 | # 2 + 1 + 11*n + 8 | # 3 + 11*n + 8 > 11*(n + 1) # 11*n + 8 + 3 | # for n in range(501): if is_daisy(11*(n + 1)): print("Total:", 11*(n + 1)) |

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 |
dw = 'zero one two three four five six seven eight nine'.split() links = set((i, j) for j in range(10) for i in range(10) if dw[i][-1] == dw[j][0]) # allowed digit to digit transitions: # # 0 -> 1 ; 1 -> 8; 2 -> 1; 3 -> 8; 5 -> 8; 7 -> 9; 8 -> 2 / 3; 9 -> 8 # # chains consist of only two different links: 8 -> 2 -> 1 and 8 -> 3; # hence digit sums for looped digital daisy-chains are multiples of 11 # look for digital daisy-chains in multiples of eleven n, dc = 0, 0 while True: n += 11 # find the digits ... dts = tuple(int(x) for x in str(n)) # ... and check that each digit can follow its predecessor if all((x, y) in links for x, y in zip(dts, dts[1:])): print(f"Total = {n}") # the looped daisy-chain has less than 1000 digits and # each multiple of 11 is the sum of at least two digits if (dc := dc + 2) > 1000: break |

“Assuming that the 4 digit PINS are 4 digit integers, then a, b, c and d will all be in the range 10 to 99 inclusive.”

The range could be more optimal: 32-99 due to the squares in the edges.

]]>I just noticed this myself this morning as I was tidying up the code.

]]>
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
from itertools import combinations as comb M = 30 # A1 A2 A3 B1 B2 C1 adj = [-6, -6, -6, 20, 20, -21] # loop until a solution is found while M < 99: for (A1, A2, A3) in comb(range(7, M + 1), 3): if A2 == A1 + 1 or A3 == A2 + 1: continue for (B1, B2) in comb(range(1, M - 19), 2): if B2 == B1 + 1: continue for C1 in range(22, M + 1): old = [A1, A2, A3, B1, B2, C1] # different numbers if len(set(old)) != 6: continue dOld = dict() # calculate old series lengths for i, x in enumerate(sorted(old)): dOld[x] = x if i == 0 else x - prev prev = x # no adjacent fields of same type for x, z in [[A1, A2], [A2, A3], [B1, B2]]: if not any(x < y < z for y in old): break else: # no break new = [x + y for x, y in zip(old, adj)] # different numbers if len(set(new)) != 6: continue # within boundaries if any(x < 1 or x > M for x in new): continue # no adjacent fields of same type for x, z in [[A1 - 6, A2 - 6], [A2 - 6, A3 - 6], [B1 + 20, B2 + 20]]: if not any (x < y < z for y in new): break else: # no break dNew = dict() # calculate new series lengths for i, x in enumerate(sorted(new)): dNew[x] = x if i == 0 else x - prev if dNew[x] not in dOld.values(): break prev = x else: # no break for i in range(6): if dNew[new[i]] != dOld[old[i]]: break else: # no break print("old", ([A1, A2, A3], [B1, B2], [C1]), "new", (new[:3], new[3:5], [new[5]])) print("answer:", list(dNew.values())) exit() M += 1 |

Following is not the most elegant program but it runs in 9ms with Cpython.

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
# neither A nor C can be first because they are moved to earlier slots later # this leaves us only 2 options BABACA (type 0) or BACABA (type 1) # using series lengths a, b, c, d, e and f in order along the initial # timeline, list their [start, end) intervals on the final timeline # 1 B [20,20+a] or B [20,20+a] # 2 A [a-6,a+b-6] A [a-6,a+b-6] # 3 B [a+b+20,a+b+c+20] C [a+b-21,a+b+c-21] # 4 A [a+b+c-6,a+b+c+d-6] A [a+b+c-6,a+b+c+d-6] # 5 C [a+b+c+d-21,a+b+c+d+e-21] B [a+b+c+d+20,a+b+c+d+e+20] # 6 A [a+b+c+d+e-6,a+b+c+d+e+f-6] A [a+b+c+d+e-6,a+b+c+d+e+f-6] # which entry can start with a+b+c+d-6 (ending 4th entry)? # for BABACA a+b+c+d-6 is either 20 or a+b+20 # --> a+b+c+d is 26 or c+d is 26 --> overall a+b+c+d >= 26 # for BACABA a+b+c+d-6 must be 20 # --> a+b+c+d is 26 # for BABACA for only 2nd and 5th position an interval can start with 0 # so a is 6 or a+b+c+d = 21 (latter option contradicts previous finding) # so a = 6 # which entry can end with a+b+c+d+e-6 (start 6th entry)? # for BABACA a+b+c+d+e-6 is either 20+a or a+b+c+20 # --> e = 26-b-c-d or e = 26-d # for BACABA a+b+c+d+e-6 must be 20+a --> e = 26-b-c-d def hghs(t, a,b,c,d,e,f): hgh = [[20+a, a+b-6, a+b+c+20, a+b+c+d-6, a+b+c+d+e-21, a+b+c+d+e+f-6], [20+a, a+b-6, a+b+c-21, a+b+c+d-6, a+b+c+d+e+20, a+b+c+d+e+f-6]] return hgh[t] def lows(t, a,b,c,d,e,f): low = [[20, a-6, a+b+20, a+b+c-6, a+b+c+d-21, a+b+c+d+e-6], [20, a-6, a+b-21, a+b+c-6, a+b+c+d+20, a+b+c+d+e-6]] return low[t] # loop over BABACA (tp 0) or BACABA (tp 1) for tp in range(2): # for BABACA a+b+c+d >= 26 or c+d = 26 with a = 6 so b+c+d >= 20 or c+d = 26 # for BACABA a+b+c+d = 26 so max(a)= 23 and max(b, c or d) = 18 mx_cd = 26 # for BABACA a must be equal to 6 for a in range(6, 24 if tp else 7): # for BACABA a+b+c+d is 26 # for BABACA a+b-6 may not be higher than 20 for b in range(1, 25 - a if tp else 21): # for BACABA only 2nd and 3rd position an interval can start with 0 if tp == 1 and not (a == 6 or a + b == 21): continue for c in range(1, 26 - a - b if tp else mx_cd): # a+b+c+d is always greater equal to 26 for d in range(max(1, 26 - a - b - c), 27 - a - b - c if tp else min(mx_cd, 27 - c)): if tp == 0 and not(a + b + c + d == 26 or c + d == 26): continue # new interval may not overlap with interval 20-20+a if lows(tp, a,b,c,d,0,0)[3] < 20 + a and \ hghs(tp, a,b,c,d,0,0)[3] > 20: continue for e in [26-b-c-d] if tp else [26-b-c-d, 26-d]: lows_abcdef = lows(tp, a,b,c,d,e,0) if not (20 + a in lows_abcdef): continue hghs_abcdef = hghs(tp, a,b,c,d,e,0) if not (20 in hghs_abcdef): continue # already at least 5 intervals must be adjacent intv = sorted(zip(lows_abcdef, hghs_abcdef)) if sum(intv[i][0] != intv[i-1][1] for i in range(1, 6)) > 1: continue # find f for i, (x, y) in enumerate(intv): if x == y : # if multiple solutions then choose smallest intv[i] = (x, x + intv[i + 1][0] - y) if i < 5 else (x, x + 1) break print(tuple(y - x for x, y in intv), "sequence:", intv) |

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
from itertools import combinations, permutations, product # find the overlap of two python ranges; return values: # > 0 the length of the overlap # = 0 the ranges are adjacent # < 0 the distance between them def overlap(a, b): return min(a[1], b[1]) - max(a[0], b[0]) # the series moves l2i = {'A':-6, 'B':20, 'C':-21} # find distinct arrangements of A's, B's # and C's where adjacent letters differ seen = set() ncp = list() for pi in permutations('AAABBC'): if not pi in seen: seen.add(pi) if all(x != y for x, y in zip(pi, pi[1:])): ncp.append(''.join(pi)) # consider all initial arrangements of the series for pi in ncp: # neither A nor C can be first because they # are moved to earlier slots; and B can't # be last as it is moved to a later slot if pi[0] != 'B' or pi[-1] == 'B': continue # consider the six series lengths between 2 and 10 for lths in product(range(2, 11), repeat=6): # form a sequence of intervals for the initial sequence # of the series and then move them to their final positions intv, pos = [], 0 for c, l in zip(pi, lths): intv.append((pos + l2i[c], pos + l2i[c] + l, c)) pos += l # the new sequence must not extend beyond the original one if any(l < 0 or h > pos for l, h, c in intv): continue # the new intervals must not overlap each other if any(overlap(x, y) > 0 for x, y in combinations(intv, 2)): continue # output the initial and final arrangements and the series lengths pf = ''.join(c for x, y, c in sorted(intv)) li = tuple(y - x for x, y, c in intv) lf = tuple(y - x for x, y, c in sorted(intv)) print(f"{pi} = {li} -> {pf} -> {lf}") |

This is quite slow in CPython but less than 500ms in PyPy. But Jim Randell has produced a neat and faster solution here. I also think it is a better approach because it avoids setting any limits on series lengths that are being considered. Here is Jim’s approach using the NumPy package:

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
from itertools import permutations import numpy as np # solution method credit: Jim Randell # create a list of varibles from an # arrangement <p> of A's, B's and C's def make_vars(p): vbls, ac, bc = [], 1, 1 for v in p: if v == 'A': vbls.append('A' + str(ac)) ac += 1 elif v == 'B': vbls.append('B' + str(bc)) bc += 1 else: vbls.append('C1') return vbls # find distinct arrangements of A's, B's # and C's where adjacent letters differ seen = set() ncp = list() for p in permutations('AAABBC'): if not p in seen: seen.add(p) if all(x != y for x, y in zip(p, p[1:])): ncp.append(''.join(p)) # consider all initial orders of the series for pi, pf in permutations(ncp, 2): # neither A nor C can be first because they # are moved to earlier slots; and B can't # be last as it is moved to a later slot if pi[0] != 'B' or pi[-1] == 'B': continue # convert the initial and final permutations to # use the six variables: A1, A2, A3, B1, B2, C1 vi, vf = make_vars(pi), make_vars(pf) # construct the six equations that give the # offsets between the initial and the final # positions of the six series vbls, eqs = sorted(vi), list() for v in vbls: eq = [0] * len(vbls) # subtract the initial amounts for x in vi: if x == v: break eq[vbls.index(x)] -= 1 # add the final amounts for x in vf: if x == v: break eq[vbls.index(x)] += 1 eqs.append(eq) # solve numerically for the six series lengths # (symbolic solving using SymPy is too slow) try: rhs = [-6, -6, -6, 20, 20, -21] res = np.linalg.solve(np.array(eqs), np.array(rhs)) if not all(x > 0 for x in res): continue res = tuple(int(x) for x in res) except np.linalg.LinAlgError: continue var2val = dict(zip(sorted(vi), res)) li = tuple(var2val[v] for v in vi) lf = tuple(var2val[v] for v in vf) print(f"{', '.join(f'{x} = {v}' for x, v in var2val.items())}") print(f"{pi} = {li} -> {pf} -> {lf}") |

which the diagonals are not integers, I believe the intention of the teaser is

that they are. But my current answer is wrong for another reason so the text

and code above will need to be updated anyway (now done). ]]>

But it is also conceivable that the sum of the second and third terms of your expression in (a,b,c) is an integer while the terms themselves are not.

]]>So, after a lot of sketching of possible paths, I believe that when all the diagonals are face diagonals, two of the three must lie on opposite cuboid faces with the third on another face. When one of the diagonals is a space diagonal, the two face diagonals do not need to be on opposite faces but there is always a path of this kind. (I have written a program which verifies these observations by generating all 1,421,716 different paths).

This means that two different path arrangements need to be considered:

In the left hand arrangement, the third diagonal is on another face, which means that the shortest integer length path traversing all edges of a cuboid with edges \((a, b, c)\) has a length of \[4(a+b+c)+2\sqrt{a^2+b^2}+\sqrt{a^2+c^2}\]where \((a,b)\) and \((a, c)\) are the non-hypotenuse sides of Pythagorean triangles. In the right hand arrangement, the third diagonal is a space diagonal of the cuboid, giving the length as:\[4(a+b+c)+2\sqrt{a^2+b^2}+\sqrt{a^2+b^2+c^2}\]. In this case the third diagonal has to be what is known as a Pythagorean quadruple.

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 |
from itertools import combinations from collections import defaultdict from math import isqrt # a path consisting of straight lines between the vertexes of a cuboid # with three different dimensions which traverses all its edges, each # only once, also has to traverse two equal face diagonals on opposite # faces and one (either face or space) diagonal elsewhere # store solutions indexed on path length s2abc = defaultdict(list) # consider possible cuboid dimensions ... for a, b, c in combinations(range(3, 50), 3): # ... less than one litre in volume if a * b * c <= 1000: # find diagonals that are perfect squares h4 = a * a + b * b, a * a + c * c, b * b + c * c, a * a + b * b + c * c sqrs = sorted(r for x in h4 if (r := isqrt(x)) ** 2 == x) # of which there must be at least two if len(sqrs) >= 2: s2abc[4 * (a + b + c) + 2 * sqrs[0] + sqrs[1]].append((a, b, c)) sm3 = sorted(s2abc.keys())[:3] if len(sm3) > 2: print(f"Total length {sum(sm3)} cms, box sizes: {sum((s2abc[k] for k in sm3), [])}.") |