Bobbing for Kernels

See Bob. See Bob bob. Bob, Bob, bob!

Same Five Digits

Posted by kernelbob on March 20, 2011

Enigma is a weekly column in New Scientist.  Every week it has a new puzzle.  Some of the Enigma puzzles could be solved using a computer.

This week’s puzzle, Enigma number 1638, is in that category.  Here are the facts of the problem.

  • I am thinking of three numbers.
  • Each number is a perfect square.
  • Each number has five digits.
  • Five different digits occur in all three numbers.
  • Each of the five digits occurs a different number of times.
  • The five numbers of times is the same as the five digits.
  • No digit occurs its own number of times.  (E.g., 4 is not used 4 times.)
  • If you knew which digit occurs once, you could uniquely identify the numbers.

Your task is to write a program that finds and prints the three perfect squares I am thinking of.

I chose to use Python 3 to solve this problem.

The brute force solution is to enumerate all the perfect squares with five digits.  Then try them in all combinations taken three at a time.

from itertools import combinations, count, takewhile

squares = filter(lambda s: len(s) == 5,
                 takewhile(lambda s: len(s) <= 5,
                           (str(s**2) for s in count())))

for a, b, c in combinations(squares, 3):
    # ...

Each trio of numbers has to meet three criteria.

C1. five different digits occur in the trio.
C2. each digit occurs a different number of times (has a different frequency).
C3. the five frequencies are the same as the five digits.

A digit frequency histogram would help with all of those.  Let’s define a function to build it.

from collections import defaultdict

def histogram(s):
    d = defaultdict(int)
    for c in s:
        d[c] += 1
    return d

That returns a dictionary mapping each digit to the number of times it occurs.  For example, hist(‘31415′) would return {1: 2, 3: 1, 5: 1}, meaning 1 occurs twice and 3 and 5 each occur once.

Now we can test for the three criteria like this.

    hist = histogram(a + b + c)
    digits = set(hist.keys())
    frequencies = set(hist.values())
    if   (len(digits) == 5 and                     # five different digits
          digits == frequencies and                # digits == frequencies
          not any(hist[k] == k for k in hist)):    # k does not occur k times.
        # then a, b, c meet the criteria.

We need to find all trios that meet the criteria, then find the one whose singleton digit is unique.  So we’ll build a map from singleton digit to the set of trios with that singleton.

matches = defaultdict(list)
for a, b, c in combinations(squares, 3):
    # ...
    if «criteria met»:
        inverse_hist = dict((hist[k], k) for k in hist)
        singleton = inverse_hist[1]
        matches[singleton].append((a, b, c))

Now we need to find the entry in matches that has length one.  We’ll do that by creating yet another map, this time from number of matches to the list of matches.  Then we can extract the answer directly.

match_counts = dict((len(ls), ls) for ls in matches.values())
print(*match_counts[1][0])

Here is the whole program.

#!/usr/bin/python3

from collections import defaultdict
from itertools import combinations, count, takewhile

def histogram(s):
    d = defaultdict(int)
    for c in s:
        d[int(c)] += 1
    return d

squares = filter(lambda s: len(s) == 5,
                 takewhile(lambda s: len(s) <= 5,
                 (str(s**2) for s in count())))

matches = defaultdict(list)
for a, b, c in combinations(squares, 3):
    hist = histogram(a + b + c)
    digits = set(hist.keys())
    frequencies = set(hist.values())
    if    (len(digits) == 5 and
           digits == frequencies and
           not any(hist[k] == k for k in hist)):
        inverse_hist = dict((hist[k], k) for k in hist)
        singleton = inverse_hist[1]
        matches[singleton].append((a, b, c))

match_counts = dict((len(ls), ls) for ls in matches.values())
print(*match_counts[1][0])

A note on efficiency.  This programs runs for about 30 seconds on my computer.  You can reason about the problem and reduce the amount of work it does by a factor of 10,000 or so.  I’ll leave that as an exercise. (-:

About these ads

Leave a Reply

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

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: