: the same. I put in a count += 1 in the loop. Curiously at the point where a solution is found, there are 14255 iterations with combinations (should be even but isn’t!) but 14250 iterations with permutations. At the end of the run they have both done 86744 iterations. The difference in the count when the solution is found leaves me perplexed. ]]>

since they are a relatively recent addition to Python. ]]>

many more permutations than there are twice the number of combinations. ]]>

1 2 3 |
n2mf = (0, 1) + tuple(max(p for p in pr if not d % p ) for d in range(2, 49)) |

A few lines could be saved (but no speed gain) by removing line 7 and replacing lines 10 – 15 with:

1 2 3 |
n2mf = {1:1} | {d: max(p for p in pr if not d % p ) for d in range(2, 49)} |

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 |
from itertools import combinations # the set of primes less than 49 pr = {3, 5, 7} pr |= {2} | {n for n in range(11, 49, 2) if all(n % p for p in pr)} pr = sorted(pr, reverse=True) # map numbers in 1..48 to their maximum prime factors n2mf = {1:1} for d in range(2, 49): for p in pr: if not d % p: n2mf[d] = p break # routes (regions within routes are in numeric order) routes = {'ABC', 'ADE', 'BFE', 'DFC', 'CEC'} # hence possible orders for tram stop numbers # A < B < D < F < C < E # A < D < B < F < C < E # nine routes: (AB, BC) (AD, DE) (BF, FE), (DF, FC), (CE) # since all route numbers depend on differences between # region numbers, we can set A equal to one a = 1 # consider possible tram stop numbers for F, C and E # D - A >= 5; F - D >= 7; |B - D| >= 1 ==> F >= A + 13 for f, c, e in combinations(range(14, 50), 3): # check that routes CE, FC and FE are valid if c >= e or (r5 := n2mf[e - c]) < 5: continue if f >= c or (r4 := n2mf[c - f]) < 5: continue if f >= e or (r3 := n2mf[e - f]) < 5: continue # route numbers must be different if len({r3, r4, r5}) != 3: continue # consider possible tram stop numbers for B and D for b, d in combinations(range(6, f - 4), 2): for b, d in ((b, d), (d, b)): # check that routes BF, DF, AB and AD are valid if not (n2mf[f - b] == r3): continue if not (n2mf[f - d] == r4): continue if not ((r1 := n2mf[b - a]) == n2mf[c - b] >= 5): continue if not ((r2 := n2mf[d - a]) == n2mf[e - d] >= 5): continue # check that the route numbers are unique if len(set((rns := (r1, r2, r3, r4, r5)))) == 5: print(f'routes: {rns}, regions: {(a, b, c, d, e, f)}') |

1 2 3 |
len(set(g)) == 6 |

is redundant and can be removed. The next two tests in lines 26 and 27 are sufficient to ensure that all values are distinct.

]]>
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 |
from itertools import combinations, product p = {2, 3, 5, 7} p = p | set(x for x in range(11, 64, 2) if all(x % pp for pp in p)) p2 = {x * y for (x, y) in combinations(p, 2) if x * y < 64} m = 0b101010 n = 0b010101 # using same general logic as Brian for ab in range(6): g = [m, n, 0, 0, 0, 0] # vertical swap g[0] ^= 1 << ab #42 g[1] ^= 1 << ab #21 rng = range(g[1], g[0] + 1) if g[0] > g[1] else range(g[0], g[1] + 1) # vertical swap if rng[-1] > 42 and rng[0] < 21: continue for c, d, e in product(range(5), repeat = 3): g[2:] = [m, n, m, n] # horizontal swaps g[2] ^= 3 << c #42 g[3] ^= 3 << d #21 # horizontal swaps in correct order if g[2] <= g[3]: continue g[4] ^= 3 << e #42 if g[3] <= g[4]: continue if (len(set(g)) == 6 and # all values distinct len(p.intersection(g)) == 3 and # three primes len(p2.intersection(g)) == 3 and # three products of 2 primes # no values in between vertical swap not set(rng).intersection(g[2:])): print(sorted(g, reverse = True)) |

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 |
from itertools import combinations N = 6 # get primes below 64 ... P = {3, 5, 7} P |= {2} | {x for x in range(11, 2**N, 2) if all(x % p for p in P)} # ... and add product of 2 different primes valid_nums = P | {a * b for a, b in combinations(P, 2) if a * b < 2**N} # check number <n> to be prime or product of 2 different primes check = lambda n: n in valid_nums # solve the last <k> rows by doing horizontal swaps def solve(k, ns, rest): if k == 0: # three primes implicitly means three products of 2 different primes if sum(n in P for n in ns) == 3: yield ns else: r = rest[0] mx, mn = (next((x for x in ns[:r][::-1] if x != -1), -1), next((x for x in ns[r + 1:] if x != -1), -1)) # try numbers for this row for n in (h_even if r % 2 else h_odd): if not (mn < n and (mx == -1 or n < mx)): continue ns_ = [x if i != r else n for i, x in enumerate(ns)] yield from solve(k -1, ns_, rest[1:]) # valid horizontal moves (as at least one row remains unaltered ) # bit logic, credit: John Z h_odd = [n for i in range(N - 1) if check(n := (odd := 0b101010) ^ 3 << i)] h_even = [n for i in range(N - 1) if check(n := (even := 0b010101) ^ 3 << i)] # determine valid vertical swaps (sum of rows remains 63 after swap) vs = [(n := 0b101010 ^ 1 << i, 0b111111 - n) for i in range(N)] # value of unaltered row may not lie between vertically swapped row values vs = [(x, y) for x, y in vs if all(check(a) for a in [x, y]) and (min(x, y) > even or max(x, y) < odd)] nums = [-1] * N # process positions of unaltered rows for u in [0, 2, 4] * check(odd) + [1, 3, 5] * check(even): nums[u] = even if u % 2 else odd # determine valid starting rows for vertical swaps for v1, v2 in vs: # process valid vertical top row positions for r in [r for r in range(v1 < v2, 6, 2) if r + 1 != u]: # break if vertical swap takes place to low if r > u and (v1 > nums[u] or v2 > nums[u]): break nums[r:r + 2] = [v1, v2] if v1 > v2 else [v2, v1] # perform three horizontal swaps for ns in solve(3, nums, [i for i in range(6) if i not in {u, r, r + 1}]): print("answer:", ns) nums[r:r + 2] = -1, -1 # backtrack nums[u] = -1 # backtrack |