Skip to content

Sunday Times Teaser 2842 – The Best Policy

by Danny Roth

Published March 12 2017 (link)

George and Martha’s home insurance policy number is a six-figure number consisting of six different digits. George commented that the number was divisible by each of its digits and also by the sum of its digits.

Martha then added that, if you deleted the left-hand digit, then you were left with a five-figure number divisible by the sum of its five digits. If you then deleted that number’s left-hand digit, then you were left with a four-figure number divisible by the sum of its four digits, and so on all the way down.

What is their policy number?

6 Comments Leave one →
  1. Brian Gladman permalink

  2. geoffrounce permalink

    Brian, That is a very fast, neat recursive solution.

    I found it easier to find a solution in MiniZinc

  3. Before I thought about writing a program for this I plugged it into the alphametic solver from the enigma.py library.

    This executes in 78ms, so it didn’t seem worth writing a specialised program.

    (The enigma.py library is available at [ http://www.magwag.plus.com/jim/enigma.html ]).

    • Brian Gladman permalink

      You are raising an interesting point here, Jim, in that ‘worth’ involves a judgement of what benefit is achieved in doing something.

      In most cases for alphametics the time cost of programming a dedicated solver is high when compared with that involved in creating the driver program for a solver. And, given that alphametics are for the most part boring anyway, the case for solver based solutions is overwhelming (for me, the same applies to football teasers although I haven’t got round to duplicating your solver here).

      But for this teaser, without the cost of adding comments, it took me less time to write a dedicated solver than it would have done writing a driver for your solver. And the result is also a lot faster in run time (I use ‘profile’ based timing as I want to time my code not the interpreter load time).

      And, perhaps most important of all, for me the ‘worth’ is in enjoying the programming challenge for its own sake, which often means that I will create a dedicated program even when I know it would take less time using a solver.

      And in website terms, since the aim of this site is about promoting interest in Python rather than in the teasers themselves (where my google based Sunday Times Teaser site puts the focus), this means that solver based solutions do less for the site’s objective than actual Python code that gives people insights into language features and how they can be used to good effect.

      • For me, when I first look at a problem I’m usually concerned with getting the solution with minimal effort using the tools I have available. For this puzzle I had a solution written and executed using the alphametic solver in under two minutes, before I was really awake enough to start thinking about writing a specific solution from scratch.

        I did go on to write a recursive program to solve the problem, which turned out quite similar to the program you posted, so I thought it would be more interesting to post an alternative approach. The recursive program took me 5-10 minutes, and overall execution time is only slightly faster, so in time terms (both overall and development time) the alphametic solution won hands down – although if I didn’t already have the alphametic solver available I wouldn’t have written it to solve this problem.

        The alphametic solver takes the expressions you give it and turns them into a program that it then executes to solve the problem. I measured the internal execution time (without the start up time of the Python interpreter) of the generated program and got a run times of 392us. This compares with an internal execution time of 462us for the recursive program. So using the alphametic solver not only allowed me to come up with a solution more quickly, that solution also executes faster (albeit only slightly) than my specialised program.

        The program that the alphametic solver generates is following the same steps (looking for numbers of increasing length by adding digits to the front, such that each suffix is divisible by the sum of its digits, and then finally checking the divisibility of the individual digits on the final number). The difference being that the alphametic solver generates a program that solves the problem iteratively rather then recursively, and I understand that recursion is not really considered “Pythonic” so perhaps it’s not that surprising that the iterative program runs a bit faster than a recursive version.

        If the puzzle had said that the policy number was the largest possible number with the specified properties, instead of saying it was a 6 digit number, then I wouldn’t have been tempted to use the alphametic solver on it, and would have stuck with my programmed solution. The answer is the same as the original puzzle, and I think it makes it a tiny bit more interesting.

        Also, I’m not sure what you mean about the need to write a “driver” for the alphametic solver. You can pass the arguments directly to the enigma library on the command line. But if there are several I usually find it more convenient to put them all in a file (as posted) and then pass that filename to the library. In this case the similarity of the expressions makes it easy to write them in an editor by copying and editing the previous expression.

        • Brian Gladman permalink

          @Jim. I was using the term driver to mean whatever I would have to do to feed the problem into your enigma library.

          Not surprisingly, using your library comes as second nature for you, since you know its capabilities instinctively. But, since I want to solve these problems through my own efforts, I don’t make much, if any, direct use of it. As a result, if I were to set out to use it, I would first have to work out how (which applies even in using the command line). And in this case I am certain that this would have taken me significantly longer than it took me to write and run my first working solution. This is not a criticism of your efforts on the library which I frequently look at it for inspiration when writing Python code.

          On timing, my primary interest is not in overall time (development plus run time) but in run time alone, especially in working out which of several different approaches to the same problem is the fastest (although elegance will often trump speed). And since many of these programs run in sub-millisecond times, profile or internal timing offers the only effective solution.

Leave a Reply

Note: HTML is allowed. Your email address will not be published.

Subscribe to this comment feed via RSS