Sunday Times Teaser 3164 – Touching Base
by Andrew Skidmore
Published Sunday May 14 2023 (link)
Liam has a pack of twenty cards; each card has a number printed on it as a word rather than figures.
There are two cards with ONE, two cards with TWO etc, up to two cards with TEN. He has taken four of the cards to construct an addition sum. The largest value card he has used is the sum of the values of the other cards, eg, ONE + ONE + TWO = FOUR.
If I now work in the base equal to that sum (ie, base 4 in the example), and consistently replace letters with single digits, this gives a correct sum. All of the possible digits in that base are used.
Leaving the answer in the working base, what is the total of my addition sum?
11 Comments Leave one →
Here is a solution using my Alphasum solver. A blind search solver in Python is easy to write but it would be disastrously slow which means a more intelligent approach is necessary. This would amount to an equivalent of what Alphasum does.
@Brian, you don’t seem to check ONE + ONE + TWO = FOUR. Is that because it was given as an example?
No, I just set the minimum one too low, it should be four.
Brute force, disastrously slow?
But you have analysed the problem in some detail and used that analysis to write a program that is no longer brute force – it is now a guided search.
Here is a brute force search with as little as possible analysis of the problem:
This takes 48 seconds on my PC in CPython to complete the full search for the answer. Compared with the 7 milliseconds for my version above , this is a ratio of around 7000 to 1, which I consider to be in the disastrous zone. And, of course, there is still some intelligence here that cuts down the total possible search space so its time offers only a lower bound on the true cost of a fully blind search.
Having said all that, your use of maketrans() to create the letter to digit map is certainly interesting and appears to make it pretty fast for a permutation based approach.
Hi Erling, Your use of string replacement for converting letters to digits is a nice idea but seems a bit more complex than it needs to be. How about this for the second part:
I also think your base to decimal conversion can be done more simply with:
I have understood most of what you suggest but I need to study some technicalities in it before I’m comfortable with uploading an improved version as mine.
(For no good reason I have been out of it for a while, and need to refresh even basic skills..)
My definitive version. A bit of redundant calculation in the print section but the hour is late.
There is a bug in line 34 of my code. Can anyone spot it? The outcome is not affected.
I have implemented Brians suggestions: