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]
Jim Randell 10:14 pm on 31 December 2020 Permalink |
This Python program runs in 45ms.
Run: [ @repl.it ]
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.
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:
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:
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:
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.
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