### 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,355 hits

Programming Enigma Puzzles

13 June 2012

Posted by on **From New Scientist #2869, 16th June 2012** [link]

I have before me six different six-digit numbers, whose sum also contains six digits. Each of the 42 digits has one of only two values. If I told you the sum, you would be able to identify all six numbers.

What is the sum?

[enigma1702]

Advertisements

%d bloggers like this:

Here’s my first stab at a solution in Python. It runs in 6.2s.

Solution:The sum is 818181.Here is mine:

I think it’s easy to eliminate the case of the second digit being 6 with a bit of analysis. If it is there can be no carry to the leftmost column in the sum, so the previous column must all be 1s. Then the same reasoning applies to the previous column to that, and so on. So all six numbers would be 111111, but we are asked to find six different numbers. Combined with your reasoning it follows that the second digit must be 8.

Thanks Jim, I gave up the analysis too quickly – coding in Python is just too tempting!

I like to try and do the minimum amount of analysis that lets me write a program that runs in a reasonable amount of time.

My first program started considering all possible pairs of digits, but it was clearly not going to come up with a solution in a reasonable time (in the end it took 2h4m, and found the same solution), so while it was running I had a bath and a think, and it seemed fairly obvious to me that the six 6-digit numbers must all start with the digit 1, and that the sum must start with the other digit.

In fact, it only takes 9s to run a program that tries all possible second digits, but it seemed just as obvious that the first digit of the sum must be 6 + some carry, so I let Python take it from there. It only took 6s so I was happy to post it as a solution.

Even though it doesn’t seem much of a leap to eliminate 6 it’s always nice to have the program confirm that cases you think you have eliminated analytically don’t, in fact, give a solution!

I got to the point of deducing that one digit has to be one and the other digit has to be 6 or 8, then fired up IDLE with this code. Not the fastest, but concise.

I think your is far too long Arthur ðŸ™‚

Except that it is different ðŸ˜¦

Corrected:

A really succinct piece of code, Brian.

or maybe

I can cram it all into a single expression (excluding imports) by using a

Counterobject:Although I’m not sure it helps with readability.

And it seems that reducing line or character counts in programs is not good for performance either ðŸ™‚

my original code: 42 function calls in 0.866 seconds

my five liner: 124 function calls (120 primitive calls) in 0.784 seconds

your one liner: 906333 function calls (906329 primitive calls) in 1.962 seconds

A lot of function calls are evidently not good news, although I didn’t expect my five liner to beat my original code (all of these only consider the case with 8 as the second digit).

Interestingly Python3 seems to count function calls differently from Python2, I get the following running the programs under Python 3.2, for what I think are the same programs:

906232 function calls in 1.689 seconds

906260 function calls in 1.131 seconds

1812546 function calls (1812536 primitive calls) in 1.485 seconds

They all seem to be performing pretty similarly. My last one gets twice the count because it uses

set.issubset(), rather than equality to check the required digits are used, as I decided that this was a strictly more correct interpretation of the conditions. (Although it is easy to see that the sum must contain both the digits).My timings were with pypy-1.9 but checking on Python 3.2 on x64 Windows gives completely different rankings:

my original: 906271 function calls in 1.975 seconds

my five liner: 906395 function calls (906383 primitive calls) in 1.392 seconds

your one liner: 1812561 function calls (1812549 primitive calls) in 0.287 seconds

But if I go back to pypy and replace issubset(ds) with == ds, I then get:

141 function calls (137 primitive calls) in 0.003 seconds

So it seems that you might be paying a high price in performance for your principles ðŸ™‚

Hi Arthur, I did it the other way as I was trying to exactly duplicate your output without adding another line. But I didn’t find any way of doing it ðŸ˜¦

My change to the last line was just to eliminate a syntax error message from the line

[print(v) for v in s if s.count(v) == 1]

Would the message be due to the version I am running (Python 2.7.3 on 64 bit Windows 7)?

Yes, I am running 3.2.3, which has a number of new features that I want to get used to. But it still has limited support if you make a lot of use of external libraries.

Hi folks. Just a thank you for an interesting site with stimulating comments. I sometimes write embarassingly clumsy programs in BBC Basic to solve these problems. Your pretty little programs make me want to push myself to learn Python.

Hi Liam. Glad you like the site. I’ve solved a few of the puzzles using BBC BASIC (running on an BBC Emulator), see

Enigma 45,Enigma 1561andEnigma 1696. Although really those are all re-codings of Python programs.Once you get used to the idea that Python uses indentation to identify blocks, you can write some pretty readable, compact code. Especially if you make use of the wealth of built-in libraries. I’ve been using Python for a few years now and find it an excellent general purpose language.