Enigmatic Code

Programming Enigma Puzzles

Enigma 1625: Diagonal diversion

From New Scientist #2790, 11th December 2010 [link]

A niece, Amy, asks me to help her revise some arithmetic, her favourite subject, so we make 25 cards numbered consecutively from 1 to 25, which we shuffle and deal out in a 5-by-5 grid. She then multiplies together the numbers in each row and writes the product at the end of the row; we call these products A to E, top to bottom. Amy then repeats the process for the columns, and these are the products F to J, left to right. Having got all these correct, she decides to find the product for the leading diagonal (top left to bottom right), and she calls this K.

Given that A = 483840, B = 604032, C = 90440, D = 57960, F = 193375, G = 1530144, H = 288000, I = 258552, what value should Amy obtain for K?

[enigma1625]

Advertisements

One response to “Enigma 1625: Diagonal diversion

  1. jimrandell 14 December 2011 at 2:35 pm

    The following Python code runs in 55ms:

    from enigma import multiply
    
    N = range(1, 26)
    pN = multiply(N)
    
    # row products
    pR = [483840, 604032, 90440, 57960]
    pR.append(pN // multiply(pR))
    
    # column products
    pC = [193375, 1530144, 288000, 258552]
    pC.append(pN // multiply(pC))
    
    # compute possible factorisations
    def factorisations(p, n, i = 1):
      if n == 1:
        return [[p]] if i <= p < 26 else []
      fs = []
      while i <= 25:
        (d, r) = divmod(p, i)
        if r == 0:
          fs.extend(([i] + x for x in factorisations(d, n - 1, i + 1) if i not in x))
        i += 1
      return fs
    
    
    # choose an element from each list that covers N
    def covers(l, c = []):
      if len(l) == 0:
        yield c
      else:
        s = set().union(*c)
        for i in l[0]:
          if len(s.intersection(i)) > 0: continue
          # NOTE: we need this extra iterator to make yield() work in a recursive function
          # NOTE: (Python 3.3 fixes this with "yield from ...")
          for tmp in covers(l[1:], c + [i]):
            yield tmp
    
    # find all possible column and row factorisations
    fC = covers([factorisations(p, 5) for p in pC])
    fR = covers([factorisations(p, 5) for p in pR])
    
    
    # check each row element occurs in exactly one column
    # NOTE: it's easier to code this as a function, so we can use return to exit multiple loops
    def check(cs, rs):
      for c in cs:
        s = set(c)
        for r in rs:
          if len(s.intersection(r)) != 1: return False
      return True
    
    # output the result
    def output(cs, rs):
      # output the grid
      for r in rs:
        s = set(r)
        for c in cs:
          print("{:2d} ".format(s.intersection(c).pop()), end='')
        print()
      print()
    
      # compute the diagonal
      d = [set(cs[i]).intersection(rs[i]).pop() for i in range(5)]
      print("p{d} = {pd}".format(d=d, pd=multiply(d)))
      print()
    
    for cs in fC:
      for rs in fR:
        if check(cs, rs):
          output(cs, rs)
    

    Solution: K = 32340.

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: