Enigmatic Code

Programming Enigma Puzzles

Enigma 1478: Yours squarely

From New Scientist #2640, 26th January 2008

I asked some friends to see whether they could find four perfect squares each greater than zero with not more than four digits which between them contained all 10 digits just once. Peter and Quentin found sets that had just two squares in common, but Rose had a set with no squares in common with either of these. Stanley found yet another set.

What four squares did Stanley find?

[enigma1478]

Advertisements

One response to “Enigma 1478: Yours squarely

  1. Jim Randell 3 December 2012 at 9:44 am

    The following Python program runs in 47ms.

    from itertools import combinations
    from enigma import irange, printf
    
    # find squares without repeated digits
    squares = []
    for n in irange(1, 99):
      s = str(n * n)
      if len(s) != len(set(s)): continue
      squares.append(s)
    
    # generate pan-digital sub-sequences
    # ns - the list of numbers to use
    # i - index we are considering
    # ss - sub-sequence we are accumulating
    # ds - digits remaining
    # r - accumulator for results
    def solve(ns, i, ss, ds, r):
      l = len(ds)
      # are we done?
      if l == 0 and len(ss) == 4: r.append(set(ss))
      if l == 0 or len(ss) == 4: return
      # otherwise try to add in another number
      for j in range(i + 1, len(ns)):
        n = ns[j]
        if len(n) > l: break
        if not ds.issuperset(n): continue
        solve(ns, j, ss + [n], ds.difference(n), r)
    
    # find pan-digital sequences of squares
    r = []
    for (i, s) in enumerate(squares):
      solve(squares, i, [s], set('0123456789').difference(s), r)
    
    # P, Q have exactly two squares in common
    for (P, Q) in combinations(r, 2):
      if len(P.intersection(Q)) != 2: continue
      # R has no squares in common with P or Q
      PQ = P.union(Q)
      for R in r:
        if R.intersection(PQ): continue
        # S is different from P, Q, R
        for S in r:
          if S in (P, Q, R): continue
          # display a solution
          s = lambda x: ' '.join(sorted(x, key=int))
          printf("S = {S} [P/Q = {P} / {Q}, R = {R}]", P=s(P), Q=s(Q), R=s(R), S=s(S))
    

    Solution: Stanley’s four squares are: 9, 16, 784 and 3025.

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: