Sunday Times Teaser 3047 – Some Permutations
by Howard Williams
Published Sunday February 14 2021 (link)
I gave Robbie three different, single digit, positive whole numbers and asked him to add up all the different three-digit permutations he could make from them. As a check for him, I said that there should be three threes in his total. I then added two more digits to the number to make it five digits long, all being different, and asked Robbie’s mother to add up all the possible five-digit permutations of these digits. Again, as a check, I told her that the total should include five sixes.
Given the above, the product of the five numbers was as small as possible.
What, in ascending order, are the five numbers?
14 Comments
Leave one →
Erling:
it would be simpler and one line shorter without the intermediate variable ‘z’.
Thanks John
Yes, skip line 12 and let line 11 be
I should have done that. (The z appeared to shorten line 11 before I introduced the ‘dgs’ for the set if digits — spending yet another line (line 4) by that..)
Built for speed (based on Jim Randell’s analysis).
Results with CPython:
How about:
instead of:
and staying in the integer ‘domain’?
@John,
I really don’t want to make speed contests a regular event here as I would much prefer that we focus on code quality and elegance rather than speed, especially so where pretty well any solution will run in a few milliseconds or less.
But once I have a solution approach I am happy with, I do play with Python alternatives such as the one you suggest to find which is the faster choice. And after starting with (10^n – 1) // 9 I moved to int(‘1’ * n) because it was a lot faster.
My code uses the same approach as Brian’s and Erling’s but instead of building a list of solutions and finding a minimum once the list is complete, each possible solution is compared, when it is found, to the previous minimum and replaces the previous found solution if it is ‘smaller’.
Curiously, average compute time reduces asymptotically as the number of repetitions is increased with 1000 repetitions giving a compute time about 7% greater than the compute time for 10000 repetitions. Could this be an idiosyncracy of my Windows laptop?
@John,
There are a host of difficulties in doing accurate timing on modern processors and modern operating systems because a lot is going on. At processor level, modern processors have major problems in removing heat so they have sophisticated thermal management that will reduce the speed of processor cores when the load is heavy, which will make speed apparently reduce if you run too many repeats. There is then the issue of how single threaded code is mapped to processor cores – is the same core is used for each repeat or do the repeats run on different cores which hence stay cooler? Third, we have the problem of memory caching. In a multi-level cache (i.e. most modern machines) it takes time to fully fill the cache so speed will be slow on the initial run while the cache is adjusting to the way the code is using memory.
Then on top of this we have things that the OS does such as the impact of background processes that will sometimes interrupt running code. And Python itself has a feature called the Global Interpreter Lock (GIL) and memory ‘garbage collection’ that can suddenly stall the Python interpreter.
We can get round some of these problems by measuring the minimum time for a run (which I do in Timed) but others are not so easy to avoid. I have modified my own machines BIOS settings to limit the short term impact of thermal management and this has improved the consistency of my results but I wouldn’t expect many users to do this.
So all in all, it a wonder that we get any consistency in our results at all! Its doubtful that what you are seeing is specific to your machine.
Thanks for that interesting interesting explanation of factors affecting execution time of Python code.
A few things have surprised me execution-time-wise:
how little penalty there is for using str() and int()
the large overhead associated with function calls and particularly recursive functions
how slow set operations are
how fast certain imported functions such as ‘combinations’ are
and as you pointed out the hit-and-miss nature of some tweaks made in the hope of more speed.
I couldn’t resist another Teaser-solution-in-a-print-statement:
One statement without imports:
Frits:
it is not necessary to masquerade an intermediate ‘if’ as a ‘for’ in your code; an ‘if’ in the position of the ‘for dum’ line works – at least on my setup: Windows with IDLE 3.9.0 Python. The Python language reference paragraph 6.2.4 allows nesting of ‘for’ and ‘if’ blocks without restriction in a comprehension.
Thanks, for some reason I thought it was not allowed.