Enigmatic Code

Programming Enigma Puzzles

Enigma 1746: Square in common

From New Scientist #2914, 27th April 2013 [link]

Harry and Tom each chose two four-digit perfect squares (with no leading zero) which used eight different digits. Each of them told me which two digits were not used in his squares, and that information enabled me to deduce with certainty which two squares each of them had chosen. They had not made the same choice of squares, but their choices did have one square in common.

What was the square that both of them chose?

[enigma1746]

Advertisements

3 responses to “Enigma 1746: Square in common

  1. Jim Randell 24 April 2013 at 6:30 pm

    This Python program runs in 44ms.

    from itertools import combinations
    from collections import defaultdict
    from enigma import irange, is_duplicate, printf
    
    # 4-digit squares with no repeated digits
    squares = list(x for x in (str(i * i) for i in irange(32, 99)) if not is_duplicate(x))
    
    # find pairs with two digits left over
    digits = set('0123456789')
    r = defaultdict(list)
    for (s1, s2) in combinations(squares, 2):
      d = digits.difference(s1, s2)
      if len(d) != 2: continue
      r[tuple(sorted(d))].append((s1, s2))
    
    # find pairs of remaining digits that each identify a unique pair of squares
    for (h, t) in combinations((k for (k, v) in r.items() if len(v) == 1), 2):
      # and that have one of the squares in common
      (H, T) = (r[h][0], r[t][0])
      i = set(H).intersection(T)
      if len(i) != 1: continue
    
      printf("common={i} [H={H} / T={T}]", i=list(i)[0], H=','.join(H), T=','.join(T))
    

    Solution: The common square is 3721 (= 61²).

  2. Brian Gladman 24 April 2013 at 7:23 pm

    Close to the same!:

    from itertools import combinations
    from collections import defaultdict
    
    # four digit squares without duplicated digits
    sq = [x ** 2 for x in range(32, 100) if len(set(str(x ** 2))) == 4]
    
    # a dictionary for pairs of squares indexed on the
    # digits that they do not contain between them
    d = defaultdict(list)
    # form all pairs
    for s1, s2 in combinations(sq, 2):
      # find the digits that they each use
      set_s1, set_s2 = set(str(s1)), set(str(s2))
      # if they share no common digits
      if not set_s1 & set_s2:
        # find the unused digits
        left = sorted(set('0123456789') - (set_s1 | set_s2))
        # and list the pair of squares indexed on these
        d[tuple(left)] += [frozenset((s1, s2))]
    
    # filter out any unused digits that map to more than
    # one pair of squares
    d = {k:v[0] for k, v in d.items() if len(v) == 1}
    # consider all combinations of two pairs
    for p1, p2 in combinations(d, 2):
        # find any squares that they have in common
        t = tuple(d[p1] & d[p2])
        # and output those that share exactly one square
        if len(t) == 1:
          print('The common square is', t[0])
    
  3. arthurvause 24 April 2013 at 7:27 pm

    My variation:

    from itertools import combinations
    
    digits = '0123456789'
    squares = [x*x for x in xrange(32,100) if len(set(str(x*x)))==4]
    
    pairs = ['Top'] + \
            sorted([(list(set(digits)-set(str(s)+str(t))),set((s,t))) 
             for s,t in combinations(squares,2)
                    if len(set(str(s)+str(t)))==8 ]) + \
            ['Tail']
    
    candidates = [pairs[n] for n in xrange(1,len(pairs)-1)
                  if pairs[n-1][0]<>pairs[n][0]
                  and pairs[n][0]<>pairs[n+1][0]] 
    
    print [x&y for (a,x),(b,y) in combinations(candidates,2)
                 if len(x|y)==3]
    

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: