Enigmatic Code

Programming Enigma Puzzles

Enigma 1765: Repeating digits

From New Scientist #2933, 7th September 2013 [link]

I have before me some positive whole numbers, each consisting of a single digit, which may be repeated. The digit is different for each number, and the number of times it is repeated is also different for each number.

The sum of my numbers is a number in which each digit is larger than the digit on its left, and it is the largest number for which this is possible, given the constraints described above.

What is the sum of my numbers?

[enigma1765]

Advertisements

23 responses to “Enigma 1765: Repeating digits

  1. Jim Randell 4 September 2013 at 6:38 pm

    Here’s my first stab at a solution. It takes 18.7s to run (under PyPy) so it’s not fast, but it does give the (surprisingly small) answer.

    # the largest possible sum is 123456789
    # so we only have to deal 1 repeated up to 9 times
    # and 2-9 repeated up to 8 times
    
    from itertools import permutations
    from enigma import Accumulator, subsets, irange, printf
    
    r = Accumulator(fn=max)
    
    # consider subsets of the numbers of digits
    for s in subsets(irange(1, 9)):
      # if 9 is chosen as a repeat it can only apply to the digit 1
      if 9 in s:
        (ns0, ds, s) = ([111111111], irange(1, 8), s[:-1])
      else:
        (ns0, ds) = ([], irange(1, 9))
      # map the repeats to possible digits
      for rs in permutations(ds, len(s)):
        # make the numbers
        ns = ns0 + list(int(str(r) * d) for (r, d) in zip(rs, s))
        # determine the sum
        t = sum(ns)
        # is the sum composed of increasing digits?
        ts = str(t)
        if not all(ts[i] < ts[i + 1] for i in irange(0, len(ts) - 2)): continue
        r.accumulate_data(t, ns)
    
    printf("max sum = {r.value} {r.data}")
    

    Solution: The sum of the numbers is 689.

    • Jim Randell 4 September 2013 at 7:55 pm

      A recursive version is faster (but still takes 12.7s to do the exhaustive search), and probably a bit clearer.

      from enigma import Accumulator, irange, printf
      
      digits = '0123456789'
      
      # ns - numbers
      # rs - repeats used
      # d - digit we are working on
      # r - accumulator for results
      def solve(ns, rs, d, r):
        # are we done?
        if d == 10:
          # find the sum
          t = sum(ns)
          # is it increasing digits
          s = str(t)
          if all(s[i] < s[i + 1] for i in irange(0, len(s) - 2)):
            r.accumulate_data(t, ns)
          return
        # add in the next digit
        for n in irange(1, (9 if d == 1 else 8)):
          if n not in rs:
            solve(ns + [int(digits[d] * n)], rs.union([n]), d + 1, r)
        solve(ns, rs, d + 1, r)
       
      r = Accumulator(fn=max)
      solve([], set(), 1, r)
      printf("max sum = {r.value} {r.data}")
      
      • Jim Randell 4 September 2013 at 10:59 pm

        And here’s a recursive version that uses a different approach and runs in only 81ms.

        # we start with a set of single digits (each one will be repeated some
        # different number of times to make one of the numbers used in the
        # sum)
        #
        # the rightmost digit of the total is the sum of all digits in this set
        #
        # for the next digit of the total we need the carry from the previous
        # digit of the total plus the sum of the digits in the set with maybe
        # one of them removed
        #
        # and so on, until we exhaust the digits in the set
        #
        # each digit of the total must be less than the preceding digit
        
        from enigma import Accumulator, subsets, nconcat, irange, printf
        
        # s - set of digits
        # c - carry from previous column
        # ss - digits of the sum
        # ds - digits of the numbers
        def solve(s, c, ss, ds, r):
          # are we done?
          if len(s) == 0:
            # final carry
            if c < ss[0]:
              n = nconcat(c, *ss)
              r.accumulate_data(n, ds)
            return
          # sum the digits (and carry) to get the next digit
          (c, d) = divmod(sum(s) + c, 10)
          # check the digits are decreasing
          if ss and not(d < ss[0]): return
          # try removing one of the digits 
          for x in s:
            solve(s.difference([x]), c, [d] + ss, ds + [x], r)
          # and removing none of them
          solve(s, c, [d] + ss, ds + [0], r)
          
        
        r = Accumulator(fn=max)
        for s in subsets(irange(1, 9), min_size=1):
          solve(set(s), 0, [], [], r)
        printf("max sum = {r.value} [{ns}]", ns=' + '.join(str(d) * (i + 1) for (i, d) in enumerate(r.data) if d > 0))
        

        I think this might be worth adding to the Notable Enigmas, as I did have to come up with a different approach to get an algorithm that runs in a satisfactory time. (And it will also end the joint largest drought in Notable Enigmas, without it setting a new record).

        • Brian Gladman 7 September 2013 at 10:46 am

          It is interesting that the modification of your code to allow more than one number of each length doesn’t cost much in performance on the enigma itself whilst providing a more general solution (I noticed that powerset had changed :-). I think with this modification to allow the more general solution (e.g. with a command line option), this would make a sensible notable enigma. The various solutions are interesting and, as you have said, the answer for the enigma itself is surprisingly small.

  2. Brian Gladman 4 September 2013 at 9:50 pm

    My version is almost identical to your second solution so its not worth publishing. I was also surprised at how small the answer was – so much so that i thought that I must have made a mistake.

  3. saracogluahmet 4 September 2013 at 9:53 pm
    A,lis,num=[9,8,7,6,5,4,3,2,1],[],0
    
    def Subset(N,total,itemC):
        global num
    
        for i in range(9):
            total=total+A[i]
            lis.append(A[i])
            
            if itemC<itemcount:
                Subset(N,total,itemC+1)
            elif total==N:
                Len=len(lis)
                if len(set(lis))==Len:
                    TLen=Len
                    #print(lis)
                    Max=0
                    for j in range(Len):
                        Max=Max+int(str(lis[j])*TLen)
                        TLen-=1
                    #print(Max)
                    if Max>num:
                        num=Max
                    
            total-=A[i]
            lis.pop()
    
    
    for number in range(9,2,-1):
        for itemcount in range(4):
            Subset(number,0,0)
        print(num)
        #TheMost-=1
    
    
    
    • saracogluahmet 4 September 2013 at 9:55 pm

      I think this is fast, I have not measured it, though

      • saracogluahmet 5 September 2013 at 7:12 am

        This is my first attempt, I did solve in 15 minutes, before coding this, I did solve it on the paper, sure I did a good analysis, I did measure the time as 35 ms, sure this can be speeded up, but I guess no need.

        Although I do not know Python so much, I guess that is not necessary, I can use it to solve this one in an effective way

        • Jim Randell 5 September 2013 at 11:13 am

          Very good. I did a comparative timing and your program comes out at 73ms.

          If I understand your code you are looking at the possible decompositions of the digits in the total starting with the rightmost digit (so a digit 9 may be 1 + 2 + 6, 1 + 3 + 5, 2 + 3 + 4), and then moving leftwards on to lower digits.

          My third program also works by considering the digits of the total. Although it goes through subsets of the digits which sum to derive digits of the total. My code also considers carries from the column previously calculated. Although I think I’ve been able to persuade myself that with the restrictions of the problem carries between columns cannot happen, so we would only need to consider subsets of up to three digits (as the smallest subset sum of size 4 is 1+2+3+4 = 10), and we drop one of the digits from the set at each recursive step. It looks like you’ve used a similar analysis for your program. If I apply this analysis to my program the runtime can be reduced significantly (to 39ms).

          • Brian Gladman 5 September 2013 at 11:29 am

            As is often the case, however, once you do this analysis the answer pretty well falls out without a program. So we end up with the usual issue of how much domain analysis should be incorporated into a programmed solution. I liked your third version because it is fast but still does a complete search of the puzzle space.

              • saracogluahmet 5 September 2013 at 11:42 am

                I think you have meant Jim’s code, yeah that is fast enough; my algorithm does a complete search too if you have said something about my algorithm.

                • Brian Gladman 5 September 2013 at 2:16 pm

                  Ahmet, In my view your search is incomplete since you have assumed without proof that carries are not possible and you limit the number of items to three or less. You may be able to justify (or even prove) these assumptions but you certainly have not done so.

                  It is very easy to make a program fast by making assumptions that cut the search space but this does not lead to sensible speed comparisons unless the assumptions can be justified. After all ‘print(689)’ gives a solution which is faster than any so far provided that we don’t care about the need to justify the assumptions on which our solutions depend.

                  • saracogluahmet 5 September 2013 at 2:27 pm

                    That is your view, Brian, I do not agree with you!,if you know a little about pigeonprinciple, you might understand my code, that is very clear, I guess you do not want to undertand it.

                    As to the example, are you ok? Then there are so many integer, how do I predict the result is 689?

                    you had better write your own code, if possible, I am open to criticism, and I guess you are too, then you should write your code and that gives us the result in a reasonable time?

                    print(“689”) Ha ha ha, you have not understood the algorithm, as I have expected, I have been solving too many problems everywhere, recently I solved a prime number question, that has 31 digits, if you can, go on, can it be coincidence?

                    • saracogluahmet 5 September 2013 at 2:33 pm

                      All the same, despite your bad intention, I will explain my algorithm a little! Try to understand it, I start from the last digit of the number, as that can be 9, the rightmostdigit of the number can be 9, any objection to this? Maybe you have an objection!

                      if the last digit was 9, all numbers digits are different given in the puzzle, I am searching the subset of 9. what can be the maximum length of the subset? All are different digits.

                      Try to understand this part first, then I keep on my algorithm!

                  • saracogluahmet 5 September 2013 at 2:41 pm

                    the second paragraph of your text does not make any sense!

                    A small advice for you, before you start to do the programming for something, first you should do analysis, I guess you have not!

                    because you said that you had not the predicted the result would be very small!

                    Then you should solve it on the paper first, sure, if you can!, after you write, print(“689”)

                    • Brian Gladman 5 September 2013 at 3:35 pm

                      I understand exactly what your code does and the assumptions that you make (despite the ongoing lack of comments).

                      Firstly, you have not justified your claim that the sum of the uinits digits must be 9. This sum could be 9, 19, 29 … (you have not shown that there cannot be a carry).

                      Secondly, you have not shown that the units digit of the maximum sum can only be 9.

                      If your code is based on assumptions and/or analysis, it is good practice to add comments to this effect so that the reader can understand what these are and whether they are justified.

                    • saracogluahmet 5 September 2013 at 3:42 pm

                      digits sum might be 9, this is the limit value, not must!, I did not use “must”, I am talking about the last digit, not talking about the carry! I can prove that why the carry must be zero!

                    • saracogluahmet 5 September 2013 at 4:44 pm

                      Why the rightmost digits sum can not be greater than 10, specifically can not be 19, because, no matter how many items add up to 19, at least 3, and 4, …., as we are moving to the leftmost digits, for example when the subset length of 19 is 3, then there are 3 numbers in the list, there comes a situation like this: XX+X, and vice versa, as there are 3 different numbers, and X+X must be greater 10, because 19 can be cut into two pieces, one of the pieces have sum greater than 10, the other is lower than 10, then, this means, there must be a carry, what does it mean? The greatest numbers digit can be 1 as minumum, then the sum of the two digits before the leftmostdigit of the biggest number is 10, it ends with 0, this is lower than the left of the neighbour and conflict, going on with 2, then the other digit can be 8 or 9, and always come across this, the leftmost digit of the number is being the greatest than the right one. These are valid for the other subsets (varying length) of the numbers greater than with 10.

            • Jim Randell 5 September 2013 at 12:20 pm

              Yes. I was happy with the third version. But I wondered if I could come up with a reasonable excuse for dropping the carry stuff, as it does make it a bit messy. But after examining it a bit I think I’m happy to leave it in as it does demonstrate an exhaustive search of the problem space, and it’s much faster than my original version.

              • saracogluahmet 5 September 2013 at 12:35 pm

                I agree with you Jim about this one which should be added to notable enigmas section, I think this puzzle is good enough and as you said, your third approach is similar to mine, I am happy with my code too.

  4. saracogluahmet 7 September 2013 at 12:46 pm

    In this version, although it is impossible to have a carry which is greater than 0, I have proved that the carry must be zero, I did this stuff pretending the carry not equal zero.

    A,lis,num,Max=[],[],0,0
    
    def ObeyRule(number):
    
        global Max
        
        Len=len(number)
    
        if Len==1:
            return True
            
        
        for i in range(Len-1):
             num=number[i]
             for j in range(i+1,Len):
                if num<=number[j]:
                    return False
        total,base=0,1
    
        for i in range(Len):
            total=total+(number[i]*base)
            base*=10
    
        if total>Max:
            Max=total
            print(Max)
        
        return True
    
    def carrytest():
    
        Sum,Len,carry=[],len(lis),0
    
        
    
        if len(set(lis))!=Len:
            return False
    
        for i in range(Len):
            TLen=Len-i
            total=0
    
            for j in range(TLen):
                total=total+lis[j]
            total+=carry
        
    
            carry=total//10
            Sum.append(total%10)
            
            
        
        return ObeyRule(Sum)
        
        
        
    
    def Subset(N,total,itemC):
        
    
        for i in range(9,0,-1):
            total=total+i
            lis.append(i)
    
            if itemC<itemcount and carrytest():
                Subset(N,total,itemC+1)
    
            total-=i
            lis.pop()
    
    
    
    for itemcount in range(2,7):
        Subset(9,0,0)
    
        
    
    
    
    
    
  5. Jim Randell 18 October 2013 at 4:51 pm

    In the end I decided not to place this problem on the Challenging Puzzles section of the Notable Enigmas page. I think the fact that it is fairly straightforward to encode the problem as a program, and get a solution out without too much waiting means it’s not too challenging to program. A bit more thought gives a program that runs pretty much instantaneously. And a bit of analysis removes the need for writing a program all together.

    What I have done is enabled Ratings for the Enigma puzzles, so contributors can now rate any puzzle from 1 to 5 stars. I’ve already rated some of the 529 puzzles on the site, and I’ll rate new puzzles as I add them. I give problems that can be solved with a trivial program 1 star. The most challenging puzzles get 4 or 5 stars. All of the puzzles on the Challenging Puzzles list have got 4 or 5 stars.

    If you want to rate a puzzle look for the Rate this: section below the puzzle statement.

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: