# Sunday Times Teaser 2901 – Square Deal

*by Danny Roth*

#### Published April 29 2018 (link)

George and Martha have five daughters who have periodically appeared in my teasers over the years. They are all working for the same company and have perfect-square four-digit telephone extensions, in all five cases. The letters **ABCDEFGHIJ** stand for the digits 0-9 but in no particular order. The extensions are as follows:

Andrea **IBHC**

Bertha **DJJC**

Caroline **BAFH**

Dorothy **GFID**

Elizabeth **GAEE**

What are the five extensions?

3 Comments
Leave one →

My original posting allowed for coding the extensions in the order given in the teaser. It resulted in a (4, 4, 2) three stage permutation for the 10 digits and ran in 21 milliseconds (using Python profile). This was fast enough but I thought that it would be interesting to see how much faster it could be made.

A large speed improvement was obtained by initially permuting the two extension numbers with duplicate digits, resulting in a (3, 3, 2, 2) stage permutation. Although there are more stages, the first two stages each involve smaller permutations and give only a few valid squares. In consequence there is much less work in finding the remaining three squares.

Another improvement in speed was obtained by replacing the “is_sq” function with a check for a valid square by testing whether a number was in a pre-computed set of four digit squares. This change also had the added benefit of eliminating the need to check the leading digits and the lengths of the five squares.

These changes, shown in the code below, reduced the run time using Python’s profiler from 21 milliseconds to 1 millisecond.