Enigmatic Code

Programming Enigma Puzzles

Enigma 1450: Triangular dominoes

From New Scientist #2611, 7th July 2007

Using a standard set of dominoes, I laid out the chain 0-0 0-1 1-1 1-2 2-2 in one direction so that the total number of “pips” in the chain reached every one of the triangular numbers 1 3 6 10 … in turn up to the greatest possible triangular number.

If there was a choice of routes from one triangular number to the following one (as for example in the next one to that shown, which might be 2-0 0-3 or 2-3), I preferred the route using the smaller or smallest number of dominoes that allowed me to continue. Having reached the highest triangular number that I could in this manner, I found that I had more than five dominoes in my hand left unused.

Which were these dominoes?

[enigma1450]

Advertisements

One response to “Enigma 1450: Triangular dominoes

  1. Jim Randell 17 March 2013 at 9:52 am

    This Python program solves the problem recursively. It runs in 36ms.

    from collections import defaultdict
    from enigma import irange, flatten, Accumulator, printf
    
    # dominoes by number of pips
    ds = defaultdict(set)
    for a in irange(0, 6):
      for b in irange(0, a):
        ds[a + b].add((b, a))
    
    # find all chains of dominoes that sum n (ignore 0-0 to make things easier)
    # n - desired sum
    # p - number of pips at the end of the chain
    # ds - dominoes (indexed by number of pips)
    # chain - chain of dominoes used so far
    # returns chains as a list of (<chain>, <number of pips at end of chain>)
    def dominoes(n, p, ds, chain):
      r = []
      # find dominoes that can start the chain
      for i in irange(1, n):
        for d in ds[i]:
          if d not in chain and p in d:
            # q is the other end of the domino
            q = d[d.index(p) ^ 1]
            if p + q == n:
              r.append(([d], q))
            else: 
              for (c2, q2) in dominoes(n - (p + q), q, ds, chain + [d]):
                r.append(([d] + c2, q2))
      # return chains of minimal length
      if len(r) < 1: return []
      m = min(len(x[0]) for x in r)
      return list(x for x in r if len(x[0]) == m)
    
    # output a chain (although without matching the ends of the dominoes)
    def output(chain):
      return ' '.join(str(d[0]) + '-' + str(d[1]) for d in chain)
    
    # add dominoes to the chain that sum n
    # chain - the chain created so far
    # n - number of pips to add to the chain
    # p - number of pips at the end of the chain
    # ds - dominoes (indexed by number of pips)
    # m - accumulator for results
    def solve(chain, n, p, ds, m):
      # find minimal next chains
      cs = dominoes(n, p, ds, chain)
      if cs:
        for (c, q) in cs:
          solve(chain + c, n + 1, q, ds, m)
      else:
        # the chain cannot be extended further, find the remaining dominoes
        r = set(flatten(ds.values())).difference(chain)
        # if there are more than 5 we have a possible solution
        if len(r) > 5: m.accumulate_data(n - 1, (r, chain))
        printf("[{n} / {chain} / {r}]", n=n-1, chain=output(chain), r=output(sorted(r)))
    
    m = Accumulator(fn=max)
    # start with the initial chain given
    solve([(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)], 5, 2, ds, m)
    
    # output the chain to the largest triangular number
    (n, (r, chain)) = (m.value, m.data)
    printf("{n} / {chain} / {r}", chain=output(chain), r=output(sorted(r)))
    

    Solution: The six unused dominoes are 0-2, 0-4, 0-6, 1-4, 1-6 and 2-6.

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: