Teaser 3041: The best game played in 1966
From The Sunday Times, 3rd January 2021 [link] [link]
For Christmas 1966 I got 200 Montini building blocks; a World Cup Subbuteo set; and a Johnny Seven multi-gun. I built a battleship on the “Wembley pitch” using every block, then launched seven missiles at it from the gun. The best game ever!
Each missile blasted a different prime number of blocks off the “pitch” (fewer than remained). After each shot, in order, the number of blocks left on the “pitch” was:
(1) a prime;
(2) a square;
(3) a cube;
(4) (a square greater than 1) times a prime;
(5) (a cube greater than 1) times a prime;
(6) none of the aforementioned; and
(7) a prime.The above would still be valid if the numbers blasted off by the sixth and seventh shots were swapped [with each other].
How many blocks remained on the “pitch” after the seventh shot?
[teaser3041]
Geoff, 
Frits, and 3 others are discussing. 
GeoffR are discussing. 
John Crabtree, 
Tony Brooke-Taylor, 
Hugh Casement and 
S2T2 
Jim Randell 10:14 pm on 31 December 2020 Permalink |
This Python program runs in 45ms.
from enigma import (irange, inf, primes, is_square, is_cube, printf) # primes less than 200 primes.expand(200) # test x is of the form (a^k)p where p is prime and a >= m def test(x, k, m=2): for a in irange(m, inf): (p, r) = divmod(x, a**k) if p < 2: return False if r == 0 and p in primes: return True # tests t1 = primes.is_prime # a prime t2 = is_square # a square t3 = is_cube # a cube t4 = lambda x: test(x, 2) # (a square) times (a prime) t5 = lambda x: test(x, 3) # (a cube) times (a prime) t6 = lambda x: not any(f(x) for f in (t1, t2, t3, t4, t5)) # none of the above t7 = t1 # a prime tests = (t1, t2, t3, t4, t5, t6, t7) # remove different prime amounts from <t>, remaining amounts satisfying <tests> # return the amounts removed def solve(t, tests, ns=[]): # are we done? if not tests: yield ns else: # remove less than half of t for n in primes: t_ = t - n if not (n < t_): break if n not in ns and tests[0](t_): yield from solve(t_, tests[1:], ns + [n]) # find solutions for ns in solve(200, tests): r = 200 - sum(ns) # where the tests still work with the last 2 amounts swapped if t6(r + ns[-2]): printf("remaining={r} {ns}")Solution: There were 47 blocks remaining on the pitch after the seventh shot.
There are six possible sequences that satisfy all the conditions of the puzzle, and they can be grouped into three pairs that give the same total number of blocks remaining:
Each sequence is the same for the first 5 shots, and only the middle pair consists of sequences where the final two amounts are swapped over, so this gives our solution.
LikeLike
Robert Brown 12:54 pm on 1 January 2021 Permalink |
Since the sixth & seventh shots can be interchanged, they both take a prime value which doesn’t affect the rest of the puzzle. So I can’t see how we can decide which is which. Surely it would have been better if he had asked for the number of bricks remaining after the fifth shot?
LikeLike
Jim Randell 1:14 pm on 1 January 2021 Permalink |
@Robert: For any set of numbers chosen for the seven shots the number of blocks remaining after they have all been taken does not depend on the order they were taken in. So there is a unique answer for the number of blocks remaining, even though we don’t know what order the last two shots were taken in.
LikeLike
Robert Brown 6:10 pm on 1 January 2021 Permalink |
Thanks for that Jim. I realised after I posted my comment that I had misunderstood what the teaser said. The 6th shot prime must be chosen so that the balance remaining isn’t a square, a cube, a square times a prime or a cube times a prime. This gives 3 options, leading to a selection of possible 7th shot values.
LikeLiked by 1 person
Frits 6:11 pm on 2 January 2021 Permalink |
Things are not necessarily efficient (I didn’t want to copy Jim’s test function or the approach at PuzzlingInPython).
@Jim, I consider ” (fewer than remained)” also as part of “above would still be valid”, see last 2 checks.
from enigma import SubstitutedExpression, is_prime, is_square, is_cube, \ seq_all_different # is number product of a prime and a square (k=2) / cube (k=3) def is_primeprod(n, k): # primes up to (200 / 2^2) P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] if k == 3: # primes up to (200 / 2^3) P = P[:9] for p in P: (d, r) = divmod(n, p) if d < 2: return False if r == 0 and ((k == 2 and is_square(d)) or (k == 3 and is_cube(d))): return True # the alphametic puzzle p = SubstitutedExpression( [ "is_prime(200 - AB)", "is_square(200 - AB - CD)", # fewer than remained "2 * CD < 200 - AB", "is_cube(200 - AB - CD - EF)", # fewer than remained "2 * EF < 200 - AB - CD", # (a square greater than 1) times a prime "is_primeprod(200 - AB - CD - EF - GH, 2)", # fewer than remained "2 * GH < 200 - AB - CD - EF", # (a cube greater than 1) times a prime "is_primeprod(200 - AB - CD - EF - GH - IJ, 3)", # fewer than remained "2 * IJ < 200 - AB - CD - EF - GH", # none of the aforementioned "not is_prime(200 - AB - CD - EF - GH - IJ - KL)", "not is_cube(200 - AB - CD - EF - GH - IJ - KL)", "not is_square(200 - AB - CD - EF - GH - IJ - KL)", "not is_primeprod(200 - AB - CD - EF - GH - IJ - KL, 2)", "not is_primeprod(200 - AB - CD - EF - GH - IJ - KL, 3)", # fewer than remained "2 * KL < 200 - AB - CD - EF - GH - IJ", "is_prime(200 - AB - CD - EF - GH - IJ - KL - MN)", # fewer than remained "2 * MN < 200 - AB - CD - EF - GH - IJ - KL", "seq_all_different([AB, CD, EF, GH, IJ, KL, MN])", "all(is_prime(x) for x in [AB, CD, EF, GH, IJ, KL, MN])", # rules are still valid if the numbers blasted off by the sixth and # seventh shots were swapped "not is_prime(200 - AB - CD - EF - GH - IJ - MN)", "not is_cube(200 - AB - CD - EF - GH - IJ - MN)", "not is_square(200 - AB - CD - EF - GH - IJ - MN)", "not is_primeprod(200 - AB - CD - EF - GH - IJ - MN, 2)", "not is_primeprod(200 - AB - CD - EF - GH - IJ - MN, 3)", # fewer than remained (also after swapping) "2 * MN < 200 - AB - CD - EF - GH - IJ", "2 * KL < 200 - AB - CD - EF - GH - IJ - MN", ], answer="(AB, CD, EF, GH, IJ, KL, MN), \ (200 - AB, \ 200 - AB - CD, \ 200 - AB - CD - EF, \ 200 - AB - CD - EF - GH, \ 200 - AB - CD - EF - GH - IJ, \ 200 - AB - CD - EF - GH - IJ - KL, \ 200 - AB - CD - EF - GH - IJ - KL - MN)", distinct="", d2i={}, env=dict(is_primeprod=is_primeprod), verbose=0) for (_, ans) in p.solve(): print(f"{ans}")LikeLike
Jim Randell 6:58 pm on 2 January 2021 Permalink |
@Frits: You’re right. Here is a more rigorous implementation of my original approach.
We collect all possible solutions, and look for a pair that are the same except the final two values are swapped over:
from enigma import (irange, inf, primes, is_square, is_cube, group, printf) # primes less than 200 primes.expand(200) # test x is of the form (a^k)p where p is prime and a >= m def test(x, k, m=2): for a in irange(m, inf): (p, r) = divmod(x, a**k) if p < 2: return False if r == 0 and p in primes: return True # tests t1 = primes.is_prime # a prime t2 = is_square # a square t3 = is_cube # a cube t4 = lambda x: test(x, 2) # (a square) times (a prime) t5 = lambda x: test(x, 3) # (a cube) times (a prime) t6 = lambda x: not any(f(x) for f in (t1, t2, t3, t4, t5)) # none of the above tests = (t1, t2, t3, t4, t5, t6, t1) # remove different prime amounts from <t>, remaining amounts satisfying <tests> # return the amounts removed def solve(t, tests, ns=[]): # are we done? if not tests: yield ns else: # remove less than half of t for n in primes: t_ = t - n if not (n < t_): break if n not in ns and tests[0](t_): yield from solve(t_, tests[1:], ns + [n]) # collect solutions, with the final two values ordered d = group(solve(200, tests), by=(lambda x: tuple(x[:5] + sorted(x[5:])))) # find a pair of solution values for (k, vs) in d.items(): if len(vs) > 1: printf("remaining={r}; {vs}", r=200 - sum(k))LikeLike
Frits 12:01 pm on 8 January 2021 Permalink |
Coding the seq_all_different and is_prime clauses for each missile separately will bring the run time down from 1 second to 47ms.
LikeLike
Tony Brooke-Taylor 9:52 am on 7 January 2021 Permalink |
My original solution looked very messy but I was seeking to reduce the amount of looping over primes by starting in the middle – noting that there are only 4 cubes below 200, I wanted to generate and test cubes rather than primes initially.
Being a Python novice, I am learning a lot from reviewing solutions on here (Jim’s or others’), so once I had solved the puzzle I came to look at this thread. Then as a test I tried to implement my algorithm using as much of Jim’s code as possible. I have not researched properly the relative time cost of looping through primes and testing other properties, as opposed to engineering the other properties and then testing if prime (which involves at least a look-up which itself must require looping). However, by starting with the square/cube pairs implied by tests 2 and 3, then working back to 200 in one direction and forwards using Jim’s code in the other, I reduced the average run-time on my machine from 0.90ms to 0.38ms.
I won’t post all my code because I am using a few long-hand functions instead of the Enigma library. However, I think the following chunk should make it clear how I adapted Jim’s code to give a list of possible solutions from which to find the pair with interchangeable d5 and d6:
convert "power" test into powers generator generates (a^k) up to and including x, from a minimum root m def powers(x,k,m=2): for a in range(m, int(x**(1/k))+1): yield a**k ... #Control program #Store long-list of primes n0=200 primes = list(Primes(n0)) #Start with all possible pairs of squares and cubes separated by a prime nsd = {} for n3 in powers(n0,3,3):# N3>cube of 2 since we need at least one cube for N5 for n2 in powers(n0,2): d3 = n2 - n3 if d3>n2/2:continue elif is_prime(d3): nsd[(n2,n3)]=d3 #For each of these pairs, run back up to n0 to find possible prime steps ns = [] for n2, n3 in nsd.keys(): for d2 in primes: if d2 > min((n0-n2),n2):break#we don't know n1 yet, so cap d2 as if d1=0 else: n1=n2+d2 d1=n0-n1 d3=nsd[(n2,n3)] if is_prime(n1) and is_prime(d1) and len(set([d1,d2,d3]))==3: #And then run downwards to apply the remaining tests (per JR approach) for solution in solve((n0-sum([d1,d2,d3])), (t4, t5, t6, t1) , [d1,d2,d3]): ns.append(solution)LikeLike
Frits 12:53 pm on 8 January 2021 Permalink |
@Tony,
Interesting idea.
I am not coding in Python for a very long time.
I like to use list comprehensions so I would have used something like this:
nsd1 = [(s2, c3) for s in range(2, 15) for c in range(2, 6) if is_prime(d := (s2 := s*s) - (c3 := c*c*c)) and 2 * d < s2]As you can calculate d3 from n2 and n3 you don’t need to use a dictionary to store the squares and cubes.
LikeLike
GeoffR 8:21 am on 8 January 2021 Permalink |
My approach was to simulate the game, finding the blocks left (B1..B7) after firing the missiles in sequence (M1..M7).
The programme produces outputs for the number of blocks remaining as 53, 41 and 47.
However, only an output of 47 blocks remaining , after the 7th missile, allows the 6th and 7th missiles (shots) to be interchanged, so this is the answer to the teaser.
% A Solution in MiniZinc include "globals.mzn"; int:blocks = 200; % list of missiles in sequence fired var 2..79:M1; var 2..79:M2; var 2..79:M3; var 2..79:M4; var 2..79:M5; var 2..79:M6; var 2..79:M7; % all missiles are different (and prime numbers) constraint all_different ([M1, M2, M3, M4, M5, M6, M7]); % list of blocks remaining after each missile (shot) var 2..197:B1; var 2..197:B2; var 2..197:B3; var 2..197:B4; var 2..197:B5; var 2..197:B6; var 2..197:B7; % set of primes less than 200 set of int :primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199}; % sets of squares and cubes less than 200 set of int: cubes = { x * x * x | x in 2..5 }; set of int: squares = { x * x | x in 2..14 }; % set of all integers between 1 and 200 set of int: all_int = {x | x in 1..200}; % set of squares times primes set of int: sq_x_pr = {i * j | i in squares, j in primes where i * j < 200}; % set of cubes times primes set of int: cb_x_pr = {i * j | i in cubes, j in primes where i * j < 200}; % set of integers, none of the aforementioned set of int : none_of_afore = all_int diff primes diff cubes diff squares diff sq_x_pr diff cb_x_pr; % 1st Missile M1 leaves Blocks B1, displacing M1 blocks constraint B1 == blocks - M1 /\ M1 < B1 /\ M1 in primes /\ B1 in primes; % 2nd Missile M2 leaves Blocks B2 constraint B2 = blocks - (M1 + M2) /\ M2 < B2 /\ M2 in primes /\ B2 in squares; % 3rd Missile M3 leaves Blocks B3 constraint B3 = blocks - (M1 + M2 + M3) /\ M3 < B3 /\ M3 in primes /\ B3 in cubes; % 4th Missile M4 leaves Blocks B4 constraint B4 = blocks - (M1 + M2 + M3 + M4) /\ M4 < B4 /\ M4 in primes /\ B4 in sq_x_pr; % 5th Missile M5 leaves Blocks B5 constraint B5 = blocks - (M1 + M2 + M3 + M4 + M5) /\ M5 < B5 /\ M5 in primes /\ B5 in cb_x_pr; % 6th Missile M6 leaves Blocks B6 constraint B6 = blocks - (M1 + M2 + M3 + M4 + M5 + M6) /\ M6 < B6 /\ M6 in primes /\ B6 in none_of_afore; % 7th Missile M7 leaves Blocks B7 constraint B7 = blocks - (M1 + M2 + M3 + M4 + M5 + M6 + M7) /\ M7 < B7 /\ M7 in primes /\ B7 in primes; solve satisfy; output [" Missile sequence: " ++ show(M1),", ", show(M2), ", ", show(M3),", ", show(M4),", ", show(M5),", ", show(M6), ", ", show(M7) ++ "\n" ++ " Blocks left: " ++ show(B1),", ", show(B2), ", ", show(B3),", ", show(B4),", ", show(B5),", ", show(B6), ", ", show(B7) ]; % Missile sequence: 3, 53, 19, 13, 31, 11, 17 % Blocks left: 197, 144, 125, 112, 81, 70, 53 % ---------- % Missile sequence: 3, 53, 19, 13, 31, 11, 23 % Blocks left: 197, 144, 125, 112, 81, 70, 47 <<< ans % ---------- % Missile sequence: 3, 53, 19, 13, 31, 11, 29 % Blocks left: 197, 144, 125, 112, 81, 70, 41 % ---------- % Missile sequence: 3, 53, 19, 13, 31, 23, 5 % Blocks left: 197, 144, 125, 112, 81, 58, 53 % ---------- % Missile sequence: 3, 53, 19, 13, 31, 23, 11 % Blocks left: 197, 144, 125, 112, 81, 58, 47 <<< ans % ---------- % Missile sequence: 3, 53, 19, 13, 31, 23, 17 % Blocks left: 197, 144, 125, 112, 81, 58, 41 % ---------- % ==========LikeLike
Frits 11:13 am on 8 January 2021 Permalink |
Adding this will only print the 2 solutions
LikeLike
Frits 12:09 pm on 8 January 2021 Permalink |
@GeoffR, I am not sure if the limit of 79 for missiles is correct.
The minimum for 6 missiles is 41 (2+3+5+7+11+13) –> (200 – 41) / 2 = 79.5 ???
I don’t immediately see why the first missile can’t be 83.
LikeLike
Geoff 12:30 pm on 10 January 2021 Permalink |
I don’t understand. What do the words in brackets mean – (fewer than remained) – I took this to mean that each of the 7 prime numbers where smaller than the number of blocks left on the pitch. So if 53 are kicked off on the second go, don’t we need more than 53 left on the pitch? Or does it mean fewer than remained after that particular shot?
LikeLike
Jim Randell 12:40 pm on 10 January 2021 Permalink |
@Geoff: I took it to mean that at each stage the number of blocks knocked off is less than the number of blocks remaining after that shot. (So the number knocked off is less than half the number of blocks available).
So at the beginning there are 200 blocks available, so in the first shot we can knock off between 1 and 99.
If we knock off 3 with the first shot, there are 197 blocks remaining, so the second shot can knock off between 1 and 98.
If we knock off 53 with the second shot, there are 144 blocks remaining, so the third shot can knock off between 1 and 71.
And so on, until all 7 shots are taken.
LikeLike