### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,149)
- misc (2)
- project euler (2)
- puzzle (38)
- site news (44)
- tantalizer (40)
- teaser (3)

### Site Stats

- 175,242 hits

Advertisements

Programming Enigma Puzzles

19 June 2013

Posted by on **From New Scientist #2922, 22nd June 2013** [link]

My textbook lists the two-letter symbols for chemical elements, including both old and new abbreviations for some of them, as:

Ac Ag Al Am Ar As At Au Ba Be Bh Bi Bk Br Ca Cd Ce Cf Cl Cm Co Cr Cs Cu Db Ds Dy Er Es Eu Fe Fm Fr Ga Gd Ge Ha He Hf Hg Ho Hs In Ir Kr La Li Lr Lu Lw Md Mg Mn Mo Mt Na Nb Nd Ne Ni No Np Os Pa Pb Pd Pm Po Pr Pt Pu Ra Rb Re Rf Rg Rh Rn Ru Sb Sc Se Sg Si Sm Sn Sr Ta Tb Tc Te Th Ti Tl Tm Xe Yb Zn Zr.

Using letters no more than once, I have written as many as possible around a circle such that, if you look at any adjacent pair of letters, then reading them clockwise they are one of the above elements. How many letters have I written?

This brings the total number of Enigmas on the site to 439, which is just over 25% of all published Enigmas – phew! (25.03% to be (more) precise).

[enigma1754]

Advertisements

%d bloggers like this:

Here’s my first stab at a programmed solution. This Python program runs in 2.8s.

There are many possible maximal solutions.

Solution:You have written 18 letters.Here’s a slightly tweaked (but longer) version. It runs in 629ms.

It examines the elements to build a mapping of letters to possible next letters, and removes letters that can’t appear in a chain (because they can’t form either the first or second letter of an element). Like my previous program it looks for chains starting with the earliest letter, but this program stops the search when there aren’t enough letters left to beat the current maximum. We also don’t drag the “used” letters around – they’re the same as the sequence we’ve collected so far!

I have a more ‘honest’ solution than the one I posted below but it is too similar to your own so I haven’t posted it. But my code didn’t initially have the ‘x < s[0]’ on line 30 or the extra stuff on line 26. The latter dosn't speed it up much but the addition on line 19 makes a big difference. My first thought was that your ‘x < s[0]’ could equally be ‘x > s[0]’ but the speed up is nowhere near as dramatic – do you have a rationale for this choice or am I being stupid and not understanding what this term does?

The reason that check is there is to reduce duplication in the rings the program finds. It means that it only looks at rings where the earliest letter is at the beginning (obviously we could start the ring at any of the letters in it).

It also means that we can reduce the number of letters we start with, because as we step through the possible first letters we quite quickly have find rings of sufficient length that there aren’t enough letters to come later in the alphabet to beat it.

Thanks Jim, I thought that this was the reason but I was expecting it would give the same speed advantage if we made the latest letter at the beginning but it was a lot slower.

This seems to be slower than your version (assuming you are using CPython), I am not sure why.

My timing of 2.8s was using PyPy 2.0.2. Using CPython 2.7.4 I get a runtime of about 18s.

For your code I get a runtime of 761ms using CPython 2.7.4.

For reference, I should mention that my code only works becasue the longest sequence can start with an ‘A’. This is a bit naughty!

I found the answer fairly easily on paper by finding an upper bound and then an example of that length.

I would like to know how many maximal sequences exist without (a) E (b) K (c) O.

I wonder how easy it would be to adapt the above programs to answer this. I do not intend to try on paper.

If I have got this right, out of the 333 different maximal length sequences of 18 letters 36, 216 and 81 don’t contain E, K and O repectively.

Of the 26 letters in English Alphabet J,Q,V,W,X,Z and U does not meet the condiitons mentioned in the enigma as well as Au,Cu,Eu,Lu,Lw,Pu,Ru,Xe,Zn and Zr .

So the maximum number of letters that can be put into the circle is 19.

Knowing this maximum I worked it out just one of the many possibilities which obey the given conditions

Hi Ahmet, You are making hard work of this! I might have got this wrong, but I think your code can be simplified as follows:

Yeah, you did understand my code well, I sat in front of the computer, and I did write it at once, and as soon as I did get the result, I uploaded it here, there are obviously other ways of coding this puzzle

In fact, the harder way of coding this one is to simulate the recursion with the stack array, I did it here before somewhere, I can not remember now

Hi Ahmet, Looking at Brian’s rewritten version of your code, I think you have found an excellent algorithm to solve this teaser – in my view it is the easiest algorithm to understand of all the methods used to solve this teaser. I also like the way your solution prints out increasing sequence of letters until it gets to the maximum number of letters.

In fact, your solution prompted me to easily explore other solutions for the maximum number of letters by changing the first element in the Elements table eg:

# with Cf as the first element

CFERA 5

CFERAGDBHOS 11

CFERAGDBHOSINPMT 16

CFERAGDYBHOSINPMT 17

CFERALINPTMGDYBHOS 18

This prompts an addendum to the teaser :

—————————————————

– what is the minimum number of iterations to get to the maximum number of letters ? – I have 5 iterations above.

I think Brian’s rewriting of your code has made your coding much more easily understandable. It shows how important it to use meaningful variable names and to use liberal comments to help other readers understand code better and help them improve their own code. Just a final constructive comment – please accept it as such.

I would like to thank you very much regarding the algorithm, and I take your constructive comments, and I am going to try write comments on my code for it to be more understandable from now on.

Well done guys, if I knew which language you were writing in I might have a better chance of understanding it 🙂 But your suggestions on the use of comments are very true.. I used to write in Fortran in 1974 🙂

But I did it last night in about an hour and a half on a couple of pieces of paper. Surprisingly Enigma-like scribbles on my paper.. ha ha..

Welcome to Enigmatic Code.

As mentioned in my first comment I solved this puzzle using a Python program (see python.org), and all the other programs posted for this puzzle have also been Python programs. The language lends itself nicely to concise and relatively easy to read programs and is freely available on many platforms (although it’s not the fastest language out there). The vast majority of my solutions to Enigma puzzles are now coded in Python.

But if you want to post a program in another language you’re welcome to. I can’t guarantee I know every programming language out there, but I’ll have a stab at understanding it!