Sunday Times Teaser 3046 – Square Phone Numbers
by Danny Roth
Published Sunday February 07 2021 (link)
George and Martha run a business in which there are 22 departments. Each department has a perfect-square three-digit extension number, ie, everything from 100 (10²) to 961 (31²), and all five of their daughters are employees in separate departments.
Andrea, Bertha, Caroline, Dorothy and Elizabeth have extensions in numerical order, with Andrea having the lowest number and Elizabeth the highest. George commented that, if you look at those of Andrea, Bertha and Dorothy, all nine positive digits appear once. Martha added that the total of the five extensions was also a perfect square.
What is Caroline’s extension?
9 Comments Leave one →
It’s the rare Teaser that can be solved in a single print statement!
A different approach finds squares for Andrea, Bertha and Dorothy first, followed by squares for Caroline and Elizabeth.
In an unpublished email exchange, Frits has been sharing his results in testing the speed of a number the programs for solving this teaser. His tests involve a number of the programs published both here and on Jim Randell’s S2T2 site. He was surprised at the wide range of run-times, which ranged form about 250 milliseconds to his own version which runs at around 30 microseconds.
Although there is little need to worry about speed for this teaser, it is, nevertheless, an interesting exercise to see how a detailed analysis can make radical improvements in the speed of solutions. This also provided an opportunity for me to update my own speed timing code timer.py.
I have replicated Frits’ fastest code (with some small changes) and added comments to explain the details of the optimisations he has incorporated:
and here is the result of running it three times:
showing that it runs on my system in 22 microseconds. Well done Frits – you have the speed record by a considerable margin!
Here is a faster version of my code based on some of Frits’ optimisations (it uses timer.py for timing):
Replacing the string intersection subroutine with in-line code shaves another two microseconds off the timing for Frits’ code:
Here are three runs of the code:
Interesting. I already knew that continue statements are sometimes a bit slower than nested ifs. I didn’t expect so much improvement with in-line code.
First time I see the for…else construct. As people have mentioned at stackoverflow using “for…else: # no break” makes the code more clear.
Using the is_square code as in-line code also gives a small gain.
We are still far from the PyPy time which is approx 7 microseconds.
To be fair to John, I should explain that he did comment in some detail on the ‘else after for’ clauses he used. But I took them out as I prefer to reserve comments for explaining what the code is doing, not how the language works (which people should either know or be prepared to read the Python documentation to find out).