Enigmatic Code

Programming Enigma Puzzles

Enigma 1469: Triangular ring

From New Scientist #2630, 17th November 2007

I have written all the triangular numbers (1, 3, 6, 10…) below 1000 on cards, and arranged some of them in a ring so that, as seen from within the ring, the right-hand digit on each is the same as the left-hand digit on the card to its right. No card is used upside down, e.g. the 6 cannot be used as a 9.

What is the maximum number of digits I can have in the ring?

[enigma1469]

Advertisements

One response to “Enigma 1469: Triangular ring

  1. Jim Randell 27 January 2013 at 9:09 am

    The following Python program runs in 163ms.

    from collections import defaultdict
    from enigma import irange, trirt, flatten, Accumulator, printf
    
    # find triangular numbers below 1000 (as strings)
    ts = list(str(n * (n + 1) // 2) for n in irange(1, int(trirt(1000))))
    
    # make a map from final digits to numbers
    ns = defaultdict(list)
    for t in ts:
      ns[t[-1]].append(t)
    
    # we can remove numbers that end in '0' as they can't link with anything
    del ns['0']
    
    # create a ring
    def ring(ns, r, m):
      # check for closure
      if len(r) > 0 and r[0][0] == r[-1][-1]:
        # count the digits
        d = sum(len(x) for x in r)
        m.accumulate_data(d, r)
        printf("ring: digits={d} length={n} [{r}]", n=len(r), r=",".join(r))
      # try to extend
      for n in ns[r[0][0]]:
        if n in r: continue
        if n < r[-1]: continue
        ring(ns, [n] + r, m)
    
    # try making rings (with each value as the smallest)
    m = Accumulator(fn=max)
    for t in flatten(ns.values()):
      ring(ns, [t], m)
    printf("max digit length = {m.value} [{r}]", r=', '.join(m.data))
    

    Solution: The maximum number of digits in a ring is 30.

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: