Sunday Times Teaser 3115 – Germometric Mean
by Stephen Hogg
Published Sunday June 05 2022 (link)
On Whit Monday, Zak began self-isolating upstairs. At lunchtime Kaz shouted up, “What’s a Geometric Mean?” “It’s the Nth root of the product of N values,” Zak replied.
On TV, Teaseside hospital’s “geovid” admissions for the seven days prior were listed alongside their Geometric Mean. Kaz stated that chronologically the numbers comprised a decreasing set of two-figure values, Friday’s value equalling the Geometric Mean. She added that, curiously, there was a value double the Geometric Mean, but not triple, whereas the Geometric Mean was triple a data value, but not double a data value. She then told Zak just the Geometric Mean.
Zak worked out the unique data set.
Give the seven numbers in chronological order.
With speed improvement suggested by Frits below.
@Brian, removing elements 2 * G and 3 * G from divs looks to be more efficient.
Shouldn’t you theoretically also check that the last element of v4 is less than G (as you have removed the Friday check)?
Good point on the absent check, I’ll add that. I have previously checked the
alternative approach you suggest and found there was no significant speed
difference, both being under 200 microseconds on my system with CPython.
Posted using crayon
You have forgotten the fv * 3 exclusion (if fv is 30).
Thanks Frits. And you’re right I missed that constraint. I should have parsed the Teaser more carefully.
line 28 should be:
This does not however change the result.
Here is a simplified and certainly easier to understand version of my previous code. It is not necessarily faster though as it calls factors() 364 times.
I time your original as 3.2 milliseconds and this one at 4 milliseconds. The
calls to factors() are relatively expensive and can be avoided by using
in place of lines 12 to 16 to improve the speed to 2.4 milliseconds.
Well spotted, Brian, clearly a necessary condition for the ‘if’ statement in line 24 to be True. You’ve factored out ‘factors()’ completely. Reverting to manual multiplication instead of prod() might help with speed: it’s called 3997 times.
Here is a solution with a difference suggested by GeoffR using Jim Randell’s minizinc.py interface to the MiniZinc constraint modelling language.
The seemingly odd constraint on line 31 is needed in order to avoid MiniZinc’s 64-bit limit on integer size.
You also could have used:
The answer is not a decreasing set of numbers.
It does if you leave line 15 in.
What I mean is that what you print is not a decreasing sequence.
You print A, B, C, D, E, F and what is asked is A, B, C, D, G, E, F.
Ah, I hadn’t noticed that.
You will have to install packages z3 and z3-solver.
It is quite slow (13 seconds), without the exclusions it is very slow.
I tried quite a few constraint solvers but not z3. It is interesting and seems very flexible. There is a small amount of coverage of such techniques here already (although I don’t want to diverge too far from the Python theme).
Another, a lot more efficient (90 ms).