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 |
# primes less than 70 primes = [2, 3, 5, 7] primes += [x for x in range(11, 70, 2) if all(x % p for p in primes)] # locks: list of distances between locks # distances: distances from start to each lock # left: unused (prime) lock distances # pub_at: distance to the pub def place(locks, distances, left, pub_at): if distances[-1] < 70: # place another lock for nxt in left: # its distance from the start l = distances[-1] + nxt # check that its distance from all other locks # is prime whenever it is odd for x in distances: if (l - x) % 2 and l - x not in primes: break else: # place more locks place(locks + [nxt], distances + [l], left - set((nxt,)), pub_at) # if we have reached the destination via the pub elif distances[-1] == 70 and pub_at in distances: # the maximum distance between locks must be # immediately after the pub if locks[distances.index(pub_at)] == max(locks): fs = 'lock gaps {:s}, at {:s}, pub {:d}' print(fs.format(tuple(locks), tuple(distances), pub_at)) for pub in primes: # the pub is over half way and its distances from the # start and the finish are both prime if pub > 35 and 70 - pub in primes: # primes for distances between adjacent locks - the maximum distance # between locks is less than half the total distance lock_primes = set(p for p in primes if p < 35) - set((pub, 70 - pub)) # place the locks place([], [0], lock_primes, pub) |