Enigmatic Code

Programming Enigma Puzzles

Enigma 1712: Each digit twice

From New Scientist #2879, 25th August 2012 [link]

Find the set of perfect squares that between them use each of the digits 0 to 9 exactly twice and whose sum is as small as possible. Your squares must all be different, and 0 may not be a leading digit.

What is the sum of your set of squares?

[enigma1712]

Advertisements

11 responses to “Enigma 1712: Each digit twice

  1. Jim Randell 22 August 2012 at 5:22 pm

    This struck me as being somewhat similar to Enigma 1536, so I attacked it in a similar way. It runs in 285ms.

    from enigma import irange, split, printf
    
    valid_digits = set('012')
    
    class Puzzle:
    
      # consider squares up to n^2, and increase in chunks of i
      def __init__(self, n=50, i=50):
        self.chunk = i
        self.sum = pow(10, 20)
        self.extend(n)
    
      # extend the list of squares up to n^2
      def extend(self, n):
        self.max = n
        # make the list of squares
        self.squares = list(i * i for i in irange(n, 1, -1))
        # count the digits in each square
        self.digits = list(sum(pow(10, i) for i in split(s, int)) for s in self.squares)
    
      # find sets of squares
      # ds - digit count
      # i - current index into list of squares
      # s - sum of squares
      # ss - list of squares
      def solve(self, ds=0, i=0, s=0, ss=[]):
        # are we done?
        if ds == 2222222222:
          if s < self.sum: self.sum = s
          printf("sum={s} squares={ss}", ss=list(reversed(ss)))
          return
        # find the next candidate square
        for j in range(i, self.max):
          c = self.squares[j]
          # skip sums that are larger than the current smallest
          if s + c > self.sum: continue
          d = self.digits[j]
          # check we have not overused any of the digits
          if not set(split(ds + d)).issubset(valid_digits): continue
          self.solve(ds + d, j + 1, s + c, ss + [c])
    
      def run(self):
        m = self.max
        while True:
          # choose the largest square
          for i in irange(m - 1, 0, -1):
            s = self.squares[i]
            # if it's larger than the current sum we're done
            if not(self.squares[0] < self.sum):
              printf("MIN = {self.sum}")
              return
            # try to find a set including this square
            self.solve(self.digits[i], i + 1, s, [s])
          # if we've exhausted the list, extend it
          n = self.max + self.chunk
          printf("extending max square from {self.max} to {n}")
          self.extend(n)
          m = self.chunk
    
    p = Puzzle()
    p.run()
    

    Solution: The sum of the set of squares is 2439.

    • Jim Randell 23 August 2012 at 10:02 am

      The chunking is a bit over the top – it’s much easier to compute the next square then it is the next prime, so it would be cleaner to just go up one square at a time.

      Here’s some code that lets you specify the digit count pattern you are looking for, and it keeps a record of the smallest sum it’s found for each digit count as it goes along. So, to solve the original puzzle you would specify the digit count as 2222222222 (which is the default).

      from itertools import count
      from enigma import irange, split, printf
      
      import sys
      done = 2222222222 if len(sys.argv) < 2 else int(sys.argv[1])
      valid_digits = set(str(x) for x in irange(0, max(split(done, int))))
      
      # map digit count to the smallest sum seen so far
      ms = dict()
      ms[0] = 0
      
      # go through squares in order
      for i in count(1):
        s = i * i
      
        # have we completed the exhaustive search?
        if done in ms and not(s < ms[done]):
          printf("MIN = {m}", m=ms[done])
          break
      
        # compute a digit count
        d = sum(pow(10, d) for d in split(s, int))
      
        # see if we can improve on any of the current sums
        ms2 = ms.copy()
        for k, v in ms.items():
          dc = k + d
          # check we haven't overused any of the digits
          if not set(split(dc)).issubset(valid_digits): continue
          # see if we already have a smaller sum for this digit count
          s2 = s + v
          if not(dc in ms and ms[dc] < s2): ms2[dc] = s2
        ms = ms2
      

      You can use it to determine that the minimum sum using each of the digits 0-9 three times is 6714 and using each of the digits four times the minimum sum is 12528. And (if you have the patience and the RAM) that using each of the digits five times the minimum sum is 17685.

      • Jim Randell 5 September 2012 at 9:02 am

        Brian further improved this algorithm by encoding the digit count in hexadecimal, rather than decimal, and then using a neat bit of coding to check for overallocation of digits allows the elimination of superfluous intermediate results. So once the sum and largest square is found it becomes viable to re-run the algorithm with a modified digit count to find the next largest square, and so on until the required sequence of squares is determined.

        Here is the result of our combined efforts:

        from itertools import count
        import sys
        
        done = 0x2222222222 if len(sys.argv) < 2 else int(sys.argv[1], 16)
        
        def solve(done, maxs):
          # map digit count to the smallest sum seen so far
          ms = dict()
          ms[0] = (0, 0)
        
          # go through squares in order
          for i in count(1):
            s = i * i
        
            # have we completed the exhaustive search?
            if done in ms and not(s < ms[done][0] and s < maxs):
              return ms[done]
        
            # compute a digit count
            d = sum(pow(16, int(d)) for d in str(s))
        
            # see if we can improve on any of the current sums
            ms2 = ms.copy()
            for k, v in ms.items():
              dc = k + d
              # check we haven't overused any of the digits
              if (done - dc) & 0x8888888888: continue
              # see if we already have a smaller sum for this digit count
              s2 = s + v[0]
              if not(dc in ms and ms[dc][0] < s2): ms2[dc] = (s2, s)
            ms = ms2
        
        # set up digit count, largest square, list of squares
        dc, s, ss = done, pow(10, 90), []
        while dc > 0:
          # find the min sum and max square for this digit count
          m, s = solve(dc, s)
          ss.insert(0, s)
          # subtract the digits used in the square from the digit count
          dc -= sum(pow(16, int(d)) for d in str(s))
        print("sum={m} squares={ss}".format(m=sum(ss), ss=ss))
        

        Note that this algorithm will fail when the count of an individual digit exceeds 7, but as the algorithm is quite memory hungry it is more likely that it will run out of memory before this becomes a problem. Particularly when the program is being used to find solutions with homogeneous digit counts (such as required by the original puzzle).

        • Jim Randell 12 September 2012 at 7:41 am

          After quite a bit of messing around here is what will probably be the final version of this algorithm.

          This version packs the digit count into an integer using as few bits as possible, and also includes some tweaks to discard squares where the digit count exceeds the maximum digit count we are looking for. As the main routine is only interested in finding the smallest square for a specific digit count it no longer drags all the squares around, but just records the one for the digit count we’re looking for. And it provides the updates to the dictionary for each pass as a separate dictionary and merges them in at the end of the pass to ensure it doesn’t use a square twice.

          It’s still however something of a memory hungry algorithm.

          It takes command line arguments so you can specify the number of each digit you want to look for (e.g. as “9876543210” if you want each digit to appear its own number of times) and you can optionally specify the maximum square it should look for as a second argument.

          from itertools import count
          from enigma import irange, printf
          
          from math import log, ceil
          from functools import reduce
          import sys
          
          # command line arguments: [<digit-count> [<max-square>]]
          done = '2222222222' if len(sys.argv) < 2 else sys.argv[1]
          done = list(int(d) for d in (done.split(',') if ',' in done else done))
          assert len(done) == 10, "Digit count length should be 10"
          
          maxs = pow(10, sum(done)) if len(sys.argv) < 3 else int(sys.argv[2])
          
          # how many bits per digit?
          maxd = max(done)
          bits = int(ceil(log(1 + maxd, 2)))
          base = pow(2, bits)
          printf("using {bits} bits per digit (base={base})")
          
          done = reduce(lambda a, b: base * a + b, done, 0)
          
          # digit count of a number (but no digit can exceed maxd)
          def digit_count(n):
            dc = dict()
            for d in str(n):
              if d in dc:
                if dc[d] == maxd: return None
                dc[d] += 1
              else:
                dc[d] = 1
            return sum(v * pow(base, int(k)) for k, v in dc.items())
          
          # check if each digit in b is not more than the corresponding digit in a
          def check(a, b):
            m = base - 1
            while b > 0:
              if (b & m) > (a & m): return True
              a >>= bits
              b >>= bits
            return False
          
          def solve(done, maxs):
            # map digit count to the smallest sum seen so far
            ms = dict()
            ms[0] = 0
            sq = None
          
            # go through squares in order
            for i in count(1):
              s = i * i
          
              # have we completed the exhaustive search?
              if done in ms and not(s < ms[done] and s < maxs):
                return ms[done], sq
          
              # is it impossible?
              if not(s < maxs):
                raise ValueError('No Solutions')
          
              # compute a digit count for this square
              d = digit_count(s)
              if d is None or check(done, d): continue
          
              # see if we can improve on any of the current sums
              ms2 = dict()
              for k, v in ms.items():
                # check we haven't overused any of the digits
                if check(done - k, d): continue
                # see if we already have a smaller sum for this digit count
                dc = d + k
                s2 = s + v
                if not(dc in ms and ms[dc] < s2):
                  ms2[dc] = s2
                  if dc == done: sq = s
              ms.update(ms2)
          
          # set up digit count, largest square, list of squares
          dc, s, ss = done, maxs, []
          while dc > 0:
            # find the min sum and max square for this digit count
            m, s = solve(dc, s)
            ss.insert(0, s)
            # subtract the digits used in the square from the digit count
            dc -= digit_count(s)
            # update the maximum allowable digit
            maxd = max(int((dc >> (bits * i)) & (base - 1)) for i in irange(0, 9))
          printf("sum={m} squares={ss}", m=sum(ss))
          
  2. arthurvause 22 August 2012 at 7:07 pm

    This one runs a bit slower, but gets the same answer as Jim

    from itertools import combinations as comb
    
    sq1 = [n*n for n in range(1,4)]
    sq2 = [n*n for n in range(4,10)]
    sq3 = [n*n for n in range(10,32)]
    
    bestsum=99999999
    for c1 in range(4):
      for c2 in range(7):
        if (20-c1-c2*2)%3==0:
          c3=(20-c1-c2*2)//3
          for com3 in comb(sq3, c3):
            for com2 in comb(sq2, c2):
              for com1 in comb(sq1, c1):
                st=com3+com2+com1
                so = ''.join([str(x) for x in st])
                so2 = ''.join(sorted(so))
                if so2=='00112233445566778899':
                  newsum=sum(st)
                  if newsum<bestsum:
                    print st, sum(st)
                    bestsum=newsum
    
  3. arthurvause 22 August 2012 at 9:12 pm

    A faster version:

    from itertools import combinations as comb
    
    sq1 = [n*n for n in range(1,4)]
    sq2 = [n*n for n in range(4,10)]
    sq3 = [n*n for n in range(10,32)]
    
    def notExceed(numlis):
      s=''.join([str(x) for x in numlis])
      for n in range(10):
        if s.count(str(n)) > 2:
          return False
      return True
    
    bestsum=99999999
    for c1 in range(4):
      for c2 in range(7):
        if (20-c1-c2*2)%3==0:
          c3=(20-c1-c2*2)//3
          for com3 in comb(sq3, c3):
            if notExceed(com3):
              for com2 in comb(sq2, c2):
                if notExceed(com3+com2):
                  for com1 in comb(sq1, c1):
                    if notExceed(com3+com2+com1):
                      newsum=sum(com3+com2+com1)
                      if newsum<bestsum:
                        print com3+com2+com1, newsum
                        bestsum=newsum
    
  4. briangladman 22 August 2012 at 10:32 pm

    Here is my version:

    from operator import add 
    
    # square root of the maximum square
    max_sqr = 100
    # minimum sum of squares so far
    min_sum = 10000
    
    # a dictionary of suitable squares indexed on their
    # square root, returning a tuple of digit counts
    sq = { n : tuple(str(n ** 2).count(d) for d in '0123456789')
            for n in range(1, max_sqr) }
    
    # list_srt holds the square roots of the squares used so far
    # dig_cnt is a tuple of the digit counts for these squares
    
    def add_sq(list_srt, dig_cnt):
      global min_sum
      
      top, sqr_sum = list_srt[-1], sum(x * x for x in list_srt)
      while True:
        top += 1
        if top >= max_sqr:
          return
        if top not in sq:
          continue
    
        # new sum with the current square
        new_sum = sqr_sum + top ** 2
        # exit if this is larger than the current minimum
        if new_sum >= min_sum:
          return
        
        # calculate the digit counts if this square is added
        dc = tuple(map(add, sq[top], dig_cnt))
        # skip this square if any digit count is greater than two
        if any(x > 2 for x in dc):
          continue
        
        # check if we have a solution (all diigits used twice)
        if all(x == 2 for x in dc):
          # is its sum below the current minimum?
          if new_sum <= min_sum:
            # if so store the new minimum and print output
            min_sum = new_sum
            print(new_sum, tuple(x * x for x in list_srt[1:] + [top]))
        else:
          # otherwise try to add another value to our list
          add_sq(list_srt + [top], dc)
      
    add_sq([0], [0] * 10)
    
  5. Naim Uygun 23 August 2012 at 1:13 am
    #Here is my version for Enigma 1712
    
    from itertools import combinations
    squares=list()
    x=int(input("How many perfect squares numbers :"))
    for i in range(1,x):
        squares.append(i*i)
      
    for q in range(2,x):
            print(" Checking combination : ",q)
            for c in combinations(squares,q):
                top=sum(c)
                if  top %9 != 0: continue
                s=""
                for i in range(0,q):
                   s=s+str(c[i])
               
                u=len(s)
                if u != 20: continue
    
                l=list(s)
                durum= True
                for i in range(0,10):
                  if l.count(str(i))!=2:
                          durum=False
                          break
                    
                if durum==True:print(c,top)
    
  6. Jim Randell 28 April 2013 at 12:03 am

    If you’re short on time or RAM, and you have PyMathProg installed you can program up a solver to use GLPK to solve this Enigma. The following Python code (similar to my GLPK solution to Enigma 1536) can find solutions for squares using each digit from 1 to 10 times in under 500ms.

    import pymprog
    from enigma import irange, sqrt, printf
    
    # digits
    digits = list(irange(0, 9))
    
    # find a solution for primes up to maxp
    def solve(ds, maxs):
    
      squares = list(i * i for i in irange(1, int(sqrt(maxs))))
    
      # map squares to digit counts
      dc = dict()
      for n in squares:
        s = str(n)
        dc[n] = list(s.count(str(d)) for d in digits)
    
      # create the model
      m = pymprog.model('enigma1712')
    
      # we need a decision variable for each square
      x = m.var(squares, 'x', bool)
    
      # objective: minimise the sum of the squares used
      m.min(sum(n * x[n] for n in squares))
    
      # constraints: each digit is used the required number of times
      m.st([sum(dc[n][d] * x[n] for n in squares) == ds[d] for d in digits])
    
      # find a solution
      try:
        m.solve(int)
      except RuntimeError:
        return None
    
      # which squares are used?
      ss = list(n for n in squares if bool(x[n].primal))
      s = sum(ss)
    
      printf("sum={s} {ss}")
      return s
    
    
    import sys
    ds = '2222222222' if len(sys.argv) < 2 else sys.argv[1]
    ds = list(int(d) for d in (ds.split(',') if ',' in ds else ds))
    assert len(ds) == 10, "Digit count length should be 10"
    
    # increase the max square until it's larger than the best solution
    n = 10000
    while True:
      s = solve(ds, n)
      if s is not None and not(n < s): break
      n *= 10
    
    printf("min sum = {s}")
    
  7. arthurvause 28 April 2013 at 5:16 pm

    Here is a version of 1712 using the technique of my recursive solution to 1536.

    This one constructs the optimal search sequence of digits in code (the sequence being the increasing frequency of the digit in the list of squares).

    The performance is improved significantly by the converting the “containingsingle” and “containingdouble” entries to lists, so that smaller numbers are used first.

    The program runs in about 90 ms

    
    from  itertools import combinations as combs
    
    def notexceed(s):
      set_s = set(s)
      set_s.remove(" ")
      for n in set_s:
          if s.count(n) > 2:
              return False
      return True
    
    squares = [n*n for n in xrange(100) if all(str(n*n).count(str(i))<3 for i in xrange(10)) ]
    containingsingle = [0]*10
    containingdouble = [0]*10
    for n in xrange(10):
        containingsingle[n] = [ str(x) for x in squares if str(x).count(str(n))==1 ]
        containingdouble[n] = [ str(x) for x in squares if str(x).count(str(n))==2 ]
    
    frequencies = sorted([ (len([1 for x in squares if str(x).count(str(n))]),n) for n in xrange(10)])
    seq = [n for (f,n) in frequencies]
    
    def add_digit(n,s,total):
      global besttotal
      
      if total>besttotal:
        return
    
      L = len(s)-s.count(" ")
      if L>20:
          return
    
      if L==20:
        if notexceed(s):
          besttotal=total
          print "result", s, ", Total=",total
        return
    
      if n==10:
        return  
    
      if notexceed(s):
    
        d=seq[n]
        d_sofar = s.count(str(d))
        if d_sofar==0:
          for p,q in combs(containingsingle[d],2):
              add_digit(n+1,s+p+" "+q+" ",total+int(p)+int(q))
    
          for p in containingdouble[d]:
              add_digit(n+1,s+p+" ",total+int(p))
                  
        elif d_sofar==1:  
          for p in containingsingle[d]:
              add_digit(n+1,s+p+" ",total+int(p))
    
        elif d_sofar==2:  
          add_digit(n+1,s,total)
    
        else:
          return
    
    besttotal=100000
    
    add_digit(0,' ',0)
    

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: