### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,123)
- misc (2)
- project euler (2)
- puzzle (31)
- site news (43)
- tantalizer (31)
- teaser (3)

### Site Stats

- 168,282 hits

Programming Enigma Puzzles

4 September 2013

Posted by on ** From New Scientist #2933, 7th September 2013** [link]

I have before me some positive whole numbers, each consisting of a single digit, which may be repeated. The digit is different for each number, and the number of times it is repeated is also different for each number.

The sum of my numbers is a number in which each digit is larger than the digit on its left, and it is the largest number for which this is possible, given the constraints described above.

What is the sum of my numbers?

[enigma1765]

Advertisements

%d bloggers like this:

Here’s my first stab at a solution. It takes 18.7s to run (under PyPy) so it’s not fast, but it does give the (surprisingly small) answer.

Solution:The sum of the numbers is 689.A recursive version is faster (but still takes 12.7s to do the exhaustive search), and probably a bit clearer.

And here’s a recursive version that uses a different approach and runs in only 81ms.

I think this might be worth adding to the Notable Enigmas, as I did have to come up with a different approach to get an algorithm that runs in a satisfactory time. (And it will also end the joint largest drought in Notable Enigmas, without it setting a new record).

It is interesting that the modification of your code to allow more than one number of each length doesn’t cost much in performance on the enigma itself whilst providing a more general solution (I noticed that powerset had changed :-). I think with this modification to allow the more general solution (e.g. with a command line option), this would make a sensible notable enigma. The various solutions are interesting and, as you have said, the answer for the enigma itself is surprisingly small.

My version is almost identical to your second solution so its not worth publishing. I was also surprised at how small the answer was – so much so that i thought that I must have made a mistake.

I think this is fast, I have not measured it, though

This is my first attempt, I did solve in 15 minutes, before coding this, I did solve it on the paper, sure I did a good analysis, I did measure the time as 35 ms, sure this can be speeded up, but I guess no need.

Although I do not know Python so much, I guess that is not necessary, I can use it to solve this one in an effective way

Very good. I did a comparative timing and your program comes out at 73ms.

If I understand your code you are looking at the possible decompositions of the digits in the total starting with the rightmost digit (so a digit 9 may be 1 + 2 + 6, 1 + 3 + 5, 2 + 3 + 4), and then moving leftwards on to lower digits.

My third program also works by considering the digits of the total. Although it goes through subsets of the digits which sum to derive digits of the total. My code also considers carries from the column previously calculated. Although I think I’ve been able to persuade myself that with the restrictions of the problem carries between columns cannot happen, so we would only need to consider subsets of up to three digits (as the smallest subset sum of size 4 is 1+2+3+4 = 10), and we drop one of the digits from the set at each recursive step. It looks like you’ve used a similar analysis for your program. If I apply this analysis to my program the runtime can be reduced significantly (to 39ms).

As is often the case, however, once you do this analysis the answer pretty well falls out without a program. So we end up with the usual issue of how much domain analysis should be incorporated into a programmed solution. I liked your third version because it is fast but still does a complete search of the puzzle space.

🙂

I think you have meant Jim’s code, yeah that is fast enough; my algorithm does a complete search too if you have said something about my algorithm.

Ahmet, In my view your search is incomplete since you have assumed without proof that carries are not possible and you limit the number of items to three or less. You may be able to justify (or even prove) these assumptions but you certainly have not done so.

It is very easy to make a program fast by making assumptions that cut the search space but this does not lead to sensible speed comparisons unless the assumptions can be justified. After all ‘print(689)’ gives a solution which is faster than any so far provided that we don’t care about the need to justify the assumptions on which our solutions depend.

That is your view, Brian, I do not agree with you!,if you know a little about pigeonprinciple, you might understand my code, that is very clear, I guess you do not want to undertand it.

As to the example, are you ok? Then there are so many integer, how do I predict the result is 689?

you had better write your own code, if possible, I am open to criticism, and I guess you are too, then you should write your code and that gives us the result in a reasonable time?

print(“689”) Ha ha ha, you have not understood the algorithm, as I have expected, I have been solving too many problems everywhere, recently I solved a prime number question, that has 31 digits, if you can, go on, can it be coincidence?

All the same, despite your bad intention, I will explain my algorithm a little! Try to understand it, I start from the last digit of the number, as that can be 9, the rightmostdigit of the number can be 9, any objection to this? Maybe you have an objection!

if the last digit was 9, all numbers digits are different given in the puzzle, I am searching the subset of 9. what can be the maximum length of the subset? All are different digits.

Try to understand this part first, then I keep on my algorithm!

the second paragraph of your text does not make any sense!

A small advice for you, before you start to do the programming for something, first you should do analysis, I guess you have not!

because you said that you had not the predicted the result would be very small!

Then you should solve it on the paper first, sure, if you can!, after you write, print(“689”)

I understand exactly what your code does and the assumptions that you make (despite the ongoing lack of comments).

Firstly, you have not justified your claim that the sum of the uinits digits must be 9. This sum could be 9, 19, 29 … (you have not shown that there cannot be a carry).

Secondly, you have not shown that the units digit of the maximum sum can only be 9.

If your code is based on assumptions and/or analysis, it is good practice to add comments to this effect so that the reader can understand what these are and whether they are justified.

digits sum might be 9, this is the limit value, not must!, I did not use “must”, I am talking about the last digit, not talking about the carry! I can prove that why the carry must be zero!

Why the rightmost digits sum can not be greater than 10, specifically can not be 19, because, no matter how many items add up to 19, at least 3, and 4, …., as we are moving to the leftmost digits, for example when the subset length of 19 is 3, then there are 3 numbers in the list, there comes a situation like this: XX+X, and vice versa, as there are 3 different numbers, and X+X must be greater 10, because 19 can be cut into two pieces, one of the pieces have sum greater than 10, the other is lower than 10, then, this means, there must be a carry, what does it mean? The greatest numbers digit can be 1 as minumum, then the sum of the two digits before the leftmostdigit of the biggest number is 10, it ends with 0, this is lower than the left of the neighbour and conflict, going on with 2, then the other digit can be 8 or 9, and always come across this, the leftmost digit of the number is being the greatest than the right one. These are valid for the other subsets (varying length) of the numbers greater than with 10.

Yes. I was happy with the third version. But I wondered if I could come up with a reasonable excuse for dropping the carry stuff, as it does make it a bit messy. But after examining it a bit I think I’m happy to leave it in as it does demonstrate an exhaustive search of the problem space, and it’s much faster than my original version.

I agree with you Jim about this one which should be added to notable enigmas section, I think this puzzle is good enough and as you said, your third approach is similar to mine, I am happy with my code too.

In this version, although it is impossible to have a carry which is greater than 0, I have proved that the carry must be zero, I did this stuff pretending the carry not equal zero.

In the end I decided not to place this problem on the

Challenging Puzzlessection of theNotable Enigmaspage. I think the fact that it is fairly straightforward to encode the problem as a program, and get a solution out without too much waiting means it’s not too challenging to program. A bit more thought gives a program that runs pretty much instantaneously. And a bit of analysis removes the need for writing a program all together.What I have done is enabled

Ratingsfor the Enigma puzzles, so contributors can now rate any puzzle from 1 to 5 stars. I’ve already rated some of the 529 puzzles on the site, and I’ll rate new puzzles as I add them. I give problems that can be solved with a trivial program 1 star. The most challenging puzzles get 4 or 5 stars. All of the puzzles on theChallenging Puzzleslist have got 4 or 5 stars.If you want to rate a puzzle look for the

Rate this:section below the puzzle statement.