# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1754: Elementary

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]

### 19 responses to “Enigma 1754: Elementary”

1. Jim Randell 19 June 2013 at 6:53 pm

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

There are many possible maximal solutions.

```from enigma import Accumulator, printf

elements = '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'.split(' ')

def solve(s, used, r):
# are we a ring?
if len(s) > 1 and s[-1] + s[0] in elements:
r.accumulate_data(len(s), s)
# try to extend the ring
for x in set(e[1] for e in elements if e[0] == s[-1] and s[0] < e[1]).difference(used):
solve(s + x, used.union([x]), r)

r = Accumulator(fn=max)
for s in set(e[0] for e in elements):
solve(s, set([s]), r)

printf("max length = {r.value} [{r.data}]")
```

Solution: You have written 18 letters.

• Jim Randell 20 June 2013 at 10:46 am

Here’s a slightly tweaked (but longer) version. It runs in 629ms.

```from collections import defaultdict
from enigma import Accumulator, printf

elements = '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'.split(' ')

# make a map of possible next letters
d = defaultdict(set)
for e in elements:

# and remove items that can't form a chain
while True:
x = set().union(*(d.values())).symmetric_difference(d.keys())
if not x: break
for k in list(d.keys()):
if k in x:
del d[k]
else:
d[k].difference_update(x)

# s - sequence collected so far
# d - map to next letters
# r - accumulator for results
def solve(s, d, r):
# are we a ring?
if len(s) > 1 and s[0] in d[s[-1]]:
r.accumulate_data(len(s), s)
# try to extend the ring
for x in d[s[-1]]:
if x < s[0] or x in s: continue
solve(s + x, d, r)

r = Accumulator(fn=max)
for s in sorted(d.keys()):
# check if we can beat the current max
if r.value and sum(1 for x in d.keys() if x > s) < r.value: break
# solve for this starting letter
solve(s, d, r)

# output the max length, and an example ring
printf("max length = {r.value} [{r.data}]")
```

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!

• Brian Gladman 21 June 2013 at 4:02 pm

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?

• Jim Randell 22 June 2013 at 10:21 am

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.

• Brian Gladman 22 June 2013 at 10:53 am

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.

2. Brian Gladman 20 June 2013 at 12:16 am

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

```from collections import defaultdict

elements = [ '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' ]

# convert to upper case
elements = [x.upper() for x in elements]

# class to save a maximum value and associated data for
# a sequence of (value, data) pairs presented to it
class save_max(object):

def __init__(self, control=0):
self.control = control
self.data = 0

def set(self, control, data):
if control > self.control:
self.control = control
self.data = data

def result(self):
return self.control, self.data

# recursively create a circular sequence of element names in
# 'seq' with the letters used so far in 'used', the maximum
# length sequence seen so far in 'res' and 'd' mapping first
# letters for elements to lists of possible second letters
def solve(seq, used, res, d):
# do we have a circular sequence
if seq[-1] + seq[0] in elements:
# save it if its length is the maximum seen
res.set(len(seq), seq)
# for all possible second letters
for nx in d[seq[-1]] - used:
# extend the sequence
solve(seq + nx, used | set((nx,)), res, d)

# for saving the overall maximum
outer_max = save_max()
# while we have not seen all elements in some sequence
while elements:

# create a map from the first letters in remaining
# elements to the set of possible second letters
m12 = defaultdict(set)
for a, b in elements:
m12[a] |= set((b,))
# for saving the maximum length sequence for this iteration
inner_max = save_max()
# find sequences starting at the first remaining element
solve(elements[0], set(elements[0]), inner_max, m12)
# get the maximum leength sequence on this iteration
ln, val = inner_max.result()
# accumulate all elements in this sequence
l = [elements[0]] + [val[i] + val[(i + 1) % ln] for i in range(ln)]
# remove these elements as we now know their maximum length sequences
elements = [x for x in elements if x not in l]
# save overall maximum length sequence
outer_max.set(ln, val)
# and output result
print(outer_max.result())
```
• Jim Randell 20 June 2013 at 9:34 am

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.

3. tonysmith 22 June 2013 at 3:11 pm

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.

• Brian Gladman 22 June 2013 at 4:03 pm

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.

4. ahmet çetinbudaklar 22 June 2013 at 9:36 pm

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

5. saracogluahmet 23 June 2013 at 9:23 am
```Elementlist=['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']

Max=0

def valid(e1,e2):

te1=e1[-2:]

se1,se2=set(te1),set(e2)

if len(set.intersection(se1,se2))>1:
return False

if te1[1]!=e2[0]:
return False

nitem=e1+e2[1]

if Check(nitem):
return True

return False

def Check(nitem):
counter=[0]*26
lng=len(nitem)

for i in range(lng):
index=ord(nitem[i])-65
counter[index]+=1
if counter[index]>1:
return False

#if (nitem[lng-1]+nitem[0])in Elementlist:
#return True
return True

def Solve(Element,counter,newitem):
global Max
lng=0

for i in range(len(Elementlist)):
item=Elementlist[i]

if valid(newitem,item):
newitem=newitem+item[1]

#if Check(newitem):
lng=len(newitem)
if (lng>Max)and (newitem[-1::]+newitem[0] in Elementlist):
Max=lng
print(newitem,lng)

Solve(item,counter+1,newitem)
newitem=newitem[0:len(newitem)-1]

#print(counter)

def main(i):
Solve(Elementlist[i],0,Elementlist[i])

main(3) #arbitrary

```
• Brian Gladman 23 June 2013 at 11:58 pm

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:

```# the element names in upper case
elements = [x.upper() for x in
( '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' ) ]

maxv = 0
def solve(seq):
global maxv
# for each element
for element in elements:
# we can use this element if its first letter matches the
# last letter of the sequence and its second letter is not
if seq[-1] == element[0] and element[1] not in seq:
# add the last letter of the element to the sequence
seq += element[1]
# if the sequence is circular
if seq[-1] + seq[0] in elements:
# print this sequence if it is the longest seen so far
if len(seq) > maxv:
maxv = len(seq)
print(seq, maxv)
# try to extend the sequence
solve(seq)
# remove the letter we added above
seq = seq[0:-1]

solve(elements[0])
```
• saracogluahmet 24 June 2013 at 6:14 am

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

• saracogluahmet 24 June 2013 at 6:16 am

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

• geoffrounce 24 June 2013 at 11:21 am

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.

• saracogluahmet 24 June 2013 at 12:42 pm

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.

6. David Betts 8 July 2013 at 12:27 pm

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..

• Jim Randell 8 July 2013 at 12:43 pm

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!