Enigmatic Code

Programming Enigma Puzzles

Enigma 1050: Find the link

From New Scientist #2206, 2nd October 1999 [link]

I was trying to construct a chain of 2-digit and 3-digit perfect squares such that each square in the chain had at least two digits in common with each of its neighbours (or with its sole neighbour, if it was at either end of the chain). If a square had a repeated digit that digit only counted more than once in calculating the number of digits that the square had in common with another square if it also appeared more than once in the other square; so 121 had only one digit in common with 100, but 100 had two [digits] in common with 400.

I found that I could construct three totally different chains each consisting of at least five squares; and I made each of these chains as long as possible, consistent with the stipulation that no square should be used more than once. But I could not link these chains into a single long chain until I used one particular 4-digit square as the means of linking one end of my first chain to one end of my second chain and also the other end of my second chain to one end of my third chain. In each place where it was used, this 4-digit square had at least two digits in common with each of its chain neighbours.

(1) Identify this 4-digit square.
(2) Which were the squares at opposite ends of the single long chain?

[enigma1050]

3 responses to “Enigma 1050: Find the link

  1. Jim Randell 6 August 2018 at 8:01 am

    I took the phrasing “I made each of these chains as long as possible …”, to mean that individually the three shorter chains cannot be extended with any of the 2,3-digit squares that do not already occur in the chain. This let me build a list of “unextendable” chains, and I could then choose three of them that do not share any numbers and do not fit together to form a composite chain, but can be formed into a composite chain with the same 4-digit square link interposed between them.

    This Python 3 program runs in 5.9s.

    Run: [ @repl.it ]

    from collections import Counter
    from itertools import product, permutations
    from enigma import irange, uniq, join, Accumulator, distinct_values, printf
    
    # squares (as strings and Counter objects)
    def squares(a, b):
      for i in irange(a, b):
        n = str(i * i)
        yield (n, Counter(n))
    
    # 2,3-digit and 4-digit squares
    squares23 = list(squares(4, 31))
    squares4 = list(squares(32, 99))
    
    # what do the 2-,3- digit squares link to
    link = dict((n, set()) for (n, _) in squares23)
    for ((a, Ca), (b, Cb)) in product(squares23, squares23 + squares4):
      if a != b and sum((Ca & Cb).values()) > 1:
        link[a].add(b)
    
    # remove any unlinkable items
    for i in irange(len(squares23) - 1, 0, step=-1):
      (n, _) = squares23[i]
      if not any(len(v) < 4 for v in link[n]):
        del squares23[i]
        del link[n]
    
    # generate unextendable chains from ns
    def chains(ns, s=[]):
      # try to extend the chain
      for (i, n) in enumerate(ns):
        if not(s) or (n in link[s[-1]]):
          for z in chains(ns[:i] + ns[i + 1:], s + [n]): yield z
      else:
        # chain cannot be extended
        if s: yield s
    
    # but we only need to consider one chain with the same start, end, content
    content = lambda s: tuple(sorted(s))
    check = lambda chain: (content(chain[0]), content(chain[-1]), content(chain))
    
    # collect unextendable chains of 2,3-digit squares, length at least 5
    ns = list(n for (n, _) in squares23)
    ss = list(s for s in uniq(chains(ns), fn=check) if len(s) > 4)
    
    # output a chain
    def output(t, n, left, middle, right):
      fmt = lambda chain: join(chain, sep="-")
      printf("{t}: ({left}) -{n}- ({middle}) -{n}- ({right})", left=fmt(left), middle=fmt(middle), right=fmt(right))
    
    # maximum number of squares used in the composite chain
    r = Accumulator(fn=max)
    
    # find a suitable middle section of chain
    for middle in ss:
      if not(middle[0] < middle[-1]): continue
    
      # find 4-digit square that links at both ends
      for n in link[middle[0]].intersection(link[middle[-1]]):
        if len(n) < 4: continue
    
        # find a suitable left chain
        for left in ss:
          if not(n in link[left[-1]] and distinct_values(left + middle)): continue
    
          # and a suitable right chain
          for right in ss:
            if not(n in link[right[0]] and distinct_values(left + middle + right) and left[0] < right[-1]): continue
    
            # check the chains cannot be linked together without the 4-digit square
            if any(l[-1] in link[m[0]] and m[-1] in link[r[0]] for (l, m, r) in permutations((left, middle, right))): continue
    
            # count the number of squares used
            t = len(left) + len(middle) + len(right)
            r.accumulate(t)
            if r.value == t: output(t, n, left, middle, right)
    
    printf("maximum composite length = {r.value}")
    

    Solution: (1) The 4-digit square is 1849; (2) The squares at the end of the long chain are 36 and 676.

    The composite chain uses 21 of the available 24 possible 2,3-digit squares (the remaining 4 squares – 49, 64, 121, 324 – cannot be linked to any other squares, so can’t appear in a chain).

    The resulting chain is not unique, but each of the shorter chains keeps the same content. Here is an example solution:

    (36-361-16-169-196-961) -1849- (144-441-484-784-841-81) -1849- (289-729-529-25-225-256-625-576-676)

    Obviously the whole chain can simply be reversed, as can just the central short chain. But also numbers with the same digit content can be interchanged. So in the left chain we have (169, 196, 961) any of the three can appear in any of the corresponding positions. In the middle chain we have (144, 441), and in the right chain we have (256, 625).

    In the left chain (16-169-196-961) all link together with 1 and 6, so the numbers can appear in any order (but 16 cannot occur at the end as a 9 is needed to link to 1849).

    Similarly the right chain has (25-225-256-625) which all have 2 and 5 in common.

    Also the middle chain can be split into (144-441-484-784)-(841-81), and the first part of this chain can be reversed, as 784 also links with 1849.

    Altogether I think that makes 3456 possible composite solution chains.

    Fortunately the numbers at the non-attached ends of the composite chain are unique by digit content, so whatever chains we use there will always be 36 at one end of the composite chain and 676 at the other end. (In the program I order the chains so the number on the left unattached end is smaller than the number on the right unattached end (when the numbers are considered as strings)).

    We can make composite chains that use 20 of the available squares and are linked with 1089, 1764, 1849, 4761, 8649, 9801. But 1849 is the only linking square that gives a composite chain that uses 21 squares.

    • Jim Randell 8 August 2018 at 7:14 am

      It wasn’t until I drew out a diagram of the graph showing the links between the 2-,3- digit squares that I realised that they form distinct clusters that cannot link outside themselves.

      Each of (49), (64), (121) and (324) forms their own singleton cluster (my program above removes these from consideration, as they can’t link to any other squares) and (100, 400, 900) form a cluster of size 3, so that too can be discarded, as we can’t form a chain with at least 5 elements from it.

      The remaining clusters are:

      (36, 361, 16, [169, 196, 961])
      (81, 841, 784, 484, [144, 441])
      (676, 576, [256, 625], 225, 25, 529, 289, 729)

      Now the part of the puzzle text that talks about making the three chains as long as possible makes sense. For each of these three clusters we can make chains that include all elements of the cluster.

      In fact for each cluster there are only a few possible maximal length chains that can be constructed. And in each cluster there is an element that only links to one other element (36, 81, 676), so they must appear at one end of each maximal chain.

      By examining how these end numbers can link to the 4-digit squares it becomes apparent that there is only one cluster that can form the middle of the composite chain, and then we can find suitable ends from the maximal paths of the remaining clusters to complete a composite chain.

      The following Python program forms the clusters the 2-,3-digit squares and the proceeds to find composite chains. It runs in 95ms.

      from collections import Counter, defaultdict
      from itertools import product
      from enigma import irange, uniq, join, Accumulator, printf
      
      # squares (as strings and Counter objects)
      def squares(a, b):
        for i in irange(a, b):
          n = str(i * i)
          yield (n, Counter(n))
      
      # 2,3-digit squares
      squares23 = list(squares(4, 31))
      
      # link objects in source to objects in target
      def graph(source, target):
        link = dict((n, set()) for (n, _) in source)
        for ((a, Ca), (b, Cb)) in product(source, target):
          if a != b and sum((Ca & Cb).values()) > 1:
            link[a].add(b)
        return link
      
      # graph linking the 2-,3- digit squares
      link = graph(squares23, squares23)
      
      # form the squares into connected clusters
      def cluster(x, link):
        g = f = set([x])
        while f:
          g1 = g.union(*(link[x] for x in f))
          (f, g) = (g1.difference(g), g1)
        return g
      
      # find non-extendable paths
      def paths(p, link):
        xs = link[p[-1]].difference(p)
        if not xs:
          yield p
        else:
          for x in xs:
            for r in paths(p + [x], link):
              yield r
      
      content = lambda s: tuple(sorted(s))
      
      # find maximal length paths
      def maximal(g, link):
        # accumulate paths by length
        d = defaultdict(list)
        # choose a start element
        for s in g:
          for p in paths([s], link):
            d[len(p)].append(p)
        k = max(d.keys())
        # we only need one maximal path with the same endpoints
        return list(uniq(d[k], (lambda p: content((content(p[0]), content(p[-1]))))))
      
      # find clusters with at least 5 elements
      # and record their maximal paths
      ks = set(link.keys())
      chains = list()
      while ks:
        k = ks.pop()
        g = cluster(k, link)
        if len(g) > 4:
          chains.append(maximal(g, link))
        ks.difference_update(g)
      
      # consider elements of clusters
      # return (i, chain) where <chain> is in cluster <i>
      # exclude = indices of clusters to exclude
      # reverse = also consider the reversed chain
      def clusters(chains, exclude=None, reverse=0):
        for (i, cs) in enumerate(chains):
          if exclude and i in exclude: continue
          for c in cs:
            yield (i, c)
            if reverse: yield (i, c[::-1])
      
      # link 2-,3- digit squares to 4-digit squares
      squares4 = list(squares(32, 99))
      link4 = graph(squares23, squares4)
      
      # output a chain
      fmt = lambda chain: join(chain, sep="-")
      
      # find maximum number of squares used in the composite chain
      r = Accumulator(fn=max)
      
      # now choose potental clusters for the middle chain
      for (j, middle) in clusters(chains):
        # choose a 4-digit square that links to either end of the middle chain
        for n in link4[middle[0]].intersection(link4[middle[-1]]):
      
          # find a suitable left chain
          for (i, left) in clusters(chains, exclude=[j], reverse=1):
            if not(n in link4[left[-1]]): continue
      
            # and a suitable right chain
            for (_, right) in clusters(chains, exclude=[i, j], reverse=1):
              if not(n in link4[right[0]] and left[0] < right[-1]): continue
      
              # count the number of squares used
              t = len(left) + len(middle) + len(right)
              r.accumulate(t)
              if r.value == t:
                printf("{t}: ({left}) -{n}- ({middle}) -{n}- ({right})", left=fmt(left), middle=fmt(middle), right=fmt(right))
      
      printf("maximum composite length = {r.value}")
      
  2. Brian Gladman 7 August 2018 at 4:07 pm

    @Jim. That is a neat trick around lines 38 to 44 to cut down the number of chains that need to be considered. The running time of my first version, without this, was measured in minutes. After adopting your trick, but using only the length of the sequence rather than its content to eliminate ‘duplicates’, my run time is now less than half a second on my machine.

    from collections import defaultdict
    from itertools import combinations, permutations
    
    # two and three digit squares
    sq23 = tuple(str(x * x) for x in range(4, 32))
    # four digit squares
    sq4 = tuple(str(x * x) for x in range(32, 100))
    
    # map 3-digit squares to those that can follow them
    s3_to_ss3 = defaultdict(set)
    # map 3-digit squares to the 4-digit squares that can follow them
    s3_to_ss4 = defaultdict(set)
    # consider all pairs of 3/4-digit squares
    for a, b in combinations(sq23 + sq4, 2):
      # look for two or more matching digits 
      cdgts = set(a).intersection(b)
      r = sum(min(a.count(d), b.count(d)) for d in cdgts)
      if r >= 2:
        if a in sq23:
          if b in sq23:
            s3_to_ss3[a].add(b)
            s3_to_ss3[b].add(a)
          else:
            s3_to_ss4[a].add(b)
    
    # build a chain of linked 3-digit squares
    def chain(cs_to_scs, s=tuple()):
      for sq in cs_to_scs[s[-1]] if s else cs_to_scs.keys():
        if sq not in s:
          yield from chain(cs_to_scs, s + (sq,))
        elif len(s) >= 5:
          yield s
    
    # we only need to consider one example of those sequences that
    # have the same start and end values and the same length (also
    # the order of the digits in the start and end don't matter)
    ch, seen = [], set()
    for c in chain(s3_to_ss3):
      t = (tuple(sorted(c[0])), tuple(sorted(c[-1])), len(c))
      if t not in seen:
        seen.add(t)
        ch.append(c)
    
    # for finding maximum length sequences
    mx_l = 0
    # consider the middle sequence
    for m in ch:
      if m[0] < m[-1]:
        sm = set(m)
        # find squares that can go at both its ends 
        for s4 in s3_to_ss4[m[0]] & s3_to_ss4[m[-1]]:
          
          # look for a sequence that can preceed middle
          for f in ch:
            if sm.intersection(f) or s4 not in s3_to_ss4[f[-1]]:
              continue
            smf = sm.union(f)
            
            # look for a sequence that can follow middle
            for l in ch:
                if smf.intersection(l) or s4 not in s3_to_ss4[l[0]]:
                  continue
    
                # the total length of all three sequences
                ln = len(f) + len(m) + len(l)
                # find the maximum length sequence
                if ln > mx_l:
                  mx_l = ln
                  u, v, w = '\u2192'.join(f), '\u2192'.join(m), '\u2192'.join(l)
                  print(f'{ln} ({u})\u2192{s4}\u2192({v})\u2192{s4}\u2192({w})')
    

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: