Enigmatic Code

Programming Enigma Puzzles

Enigma 1549: Same four digits

From New Scientist #2712, 13th June 2009 [link]

I have written down three different five-digit perfect squares, which between them use four different digits. Each of the four digits is used a different number of times, and the four numbers of times are the same as the four different digits of the perfect squares; I’m not saying whether any of the digits is used its own number of times.

What are my three perfect squares?

[enigma1549]

Advertisements

2 responses to “Enigma 1549: Same four digits

  1. Jim Randell 26 March 2012 at 2:03 pm

    Here’s my original Perl solution. It runs in 2.8s.

    use strict;
    
    my ($i, $n, $t, $u, $x);
    
    # collect the 5 digit squares
    my @squares = ();
    for $i (100..316) {
      $n = $i * $i;
      next if $n =~ /0/; # the digit 0 can't occur
      push @squares, $n;
    }
    $n = @squares;
    
    # find three squares in ascending order
    my ($a, $b, $c);
    for ($a = 0; $a < $n-2; $a++) {
      for ($b = $a+1; $b < $n-1; $b++) {
        for ($c = $b+1; $c < $n; $c++) {
    
          # make an ordered string from the digits
          $t = join '', sort split '', "$squares[$a]$squares[$b]$squares[$c]";
          # remove duplicate digits
          ($u = $t) =~ tr/0-9/0-9/s;
          # only interested if there are exactly 4 digits used
          next unless length $u == 4;
    
          # make an ordered string that counts the digits used
          $x = join '', sort map { rindex($t, $_) - index($t, $_) + 1 } split '', $u;
          # only interest if it's the same as the digits we are using
          next unless $x eq $u;
    
          print "$squares[$a] $squares[$b] $squares[$c] [$t $u]\n";
        }
      }
    }
    

    Solution: The three squares are 26244, 42436 and 43264.

    • Jim Randell 26 March 2012 at 2:06 pm

      And here’s how I would do it now in Python, making use of the Python set and Counter constructs. It runs in 350ms.

      from collections import Counter
      
      # find 5 digit squares (as strings)
      squares = []
      for i in range(100, 317):
        s = str(i ** 2)
        if '0' in s: continue
        squares.append(s)
      n = len(squares)
      
      # find three squares a < b < c that between them use exactly 4 digits
      for i in range(0, n - 2):
        a = squares[i]
        d1 = Counter(list(a))
        if len(d1) > 4: continue
        for j in range(i + 1, n-1):
          b = squares[j]
          d2 = d1.copy()
          d2.update(list(b))
          if len(d2) > 4: continue
          for k in range(j + 1, n):
            c = squares[k]
            d3 = d2.copy()
            d3.update(list(c))
            if len(d3) != 4: continue
      
            # each of the 4 digits are used a different number of times
            s1 = set(d3.values())
            if len(s1) != 4: continue
            # and this is the same as the 4 digits used in the squares
            s2 = set(int(i) for i in d3.keys())
            if s1 != s2: continue
      
            print(a, b, c)
      

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: