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]

Advertisements

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:
        d[e[0]].add(e[1])
      
      # 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())
    
  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.

  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
          # already in the sequence
          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!

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: