# Sunday Times Teaser 3043 – An Odd Selection

*by Victor Bryant*

#### Published Sunday January 17 2021 (link)

I wrote an odd digit in each of the sixteen cells of a four-by-four grid, with no repeated digit in any row or column, and with each odd digit appearing three or more times overall. Then I could read four four-figure numbers across the grid and four four-figure numbers down. I calculated the average of the four across numbers and the larger average of the four down numbers. Each was a whole number consisting entirely of odd digits, and each used an odd number of different odd digits.

What were those two averages?

14 Comments
Leave one →

This used to find 56 solutions in under 100 milliseconds. But with the improvement found by John (see below) it now runs in 60 milliseconds. Well done John!

@Brian Last digit of p4 has to be 1, 5 or 9. Then the average will always be a whole number.

In the past I have tried to write clever permutation routines that used such analysis but it was always slower than itertools permutation.

@Frits I really doubt that the extra coding needed to add this constraint would

produce a significantly faster result.

A bit faster. I have chosen for an indent level of 1 due the many loops.

@Frits Thanks for posting (I agree that indents of one are better than overflowing the right margin!).

This is faster than my old version but I have now updated mine using an analysis from a contributor on the Sunday Times Teasers Discussion Group (Jim Randell uses the same analysis in his second version).

Here is a somewhat clunky solution. I reused the structure of a bit of software that I used to solve a row / column problem many moons ago. This stops after finding one grid that gives the correct averages.

This program finds just two averages, the greater value being the column average and the lesser the row average. It also prints the 5th row – a feature of this method of solution

Here is another version that uses the MiniZinc constraint solver via Jim Randell’s minizinc.py wrapper:

Nice,

It runs really fast with Cpython (faster than PyPy).

I had to upgrade MiniZinc from 2.43 to 2.53 to get it working (as you used “var set comprehensions”).

The upper limits of row_sum and col_sum seem to have been designed for 5 rows/cols.

Maybe using a name like “odigits” iso “digits” would make lines 46-49 more clear (averages all have odd digits). I first thought you had forgotten to code a constraint.

@Frits Yes, you are right that it is long enough to forget that the digits

are all odd so I have changed this. I used 1..4 because this is the human

way that the rows and columns would be numbered and it hence makes the

model more appropriate for anyone reading it It would, of course, be

likely to be faster if I generated the averages before the grid as I did

in my first version.

Hi Brian,

Taking line 20 of the code from your first solution:

I wrote three alternative if statements (commented out below) which may or may not be more efficient than yours – is it even worth worrying about? They do have the advantage of eliminating the need for the ‘r’ variable. Here they are:

You thoughts?

Hi John

A very nice investigation! Your first alternative runs in about the same time as my construction but is certainly nicer. I would be inclined to adopt it. Your second alternative runs a bit slower than your first and my own. But your third is very good and is a clear winner on speed with a significant improvement from about 58 milliseconds to 40 milliseconds, a major improvement. So your number three is the one I shall now adopt!

Well done for finding such a large speed improvement!

Brian:

Thanks for you feedback.

here are two further touch-ups to the paintwork that might squeeze a further few milliseconds

from the run time:

removing line 43 and replacing line 44 with:

Replacing line 16 with:

allows the variable ‘ r ‘ to be removed from the parameter list of ‘ build_rows ‘

Looking forward to 3044.

@John Z

Thanks for your further suggestions, neither of which make any measurable difference to the speed. Nevertheless, your test is nicer than mine so I shall adopt it!