Sunday Times Teaser 3237 – Oranges and Lemons
by Danny Roth
Published Sunday October 06 2024 (link)
George and Martha attend a local club where there is a “fruit machine”. There are three dials, each with five “fruits” but here the “fruits” are numbers. On the first dial are the numbers 1-5; on the second there are the numbers 5-9. On the third, 5 appears again but with four different [1] two-digit numbers.
You put £1 in the machine, then pull a handle which spins the dials, and the numbers on the dials appear completely at random. The jackpot payout for three 5s is £52. Otherwise the machine pays £2 if the three displayed numbers sum to a prime total. If the machine pays out 80 per cent of its intake on average, what are the lowest possible values for the four two-digit numbers?
[1] correction added post publication in the Sunday Times.
The run time of this version is less than 1/3 of the run time of the version I posted above. This is achieved by taking combinations of 2 digit numbers 3 at a time rather than 4 at a time. The last 2 digit number is the ‘for’ loop value of the maximum 2 digit number.
Hi John,
That is a significant speed gain but using ‘sum’ with a generator inside a ‘sum’ has cost you a lot of time. Using Python’s profiler here are the numbers of calls being made:
This shows that almost all of the time (see tottime) cost is consumed in the code on line 19.
By avoiding all uses of sum in the loop as in:
we can get another factor of four in speed:
However, timing the two versions by other means indicates that profile based timing exaggerates the speed gain which is closer to two rather than four.
Brian, you’re right. It stands to reason that two successive additions of integer values will be faster than a sum on an iterable. I’ve rewritten my code to remove all repetitive ‘sum’ calls. The ‘len’ does the same thing as the outer sum in line 19 but much faster. And looking at your code, I realized that my assumption that the first solution found was the correct one, was unsafe and I corrected that.