Enigmatic Code

Programming Enigma Puzzles

Enigma 1702: All the sixes

From New Scientist #2869, 16th June 2012 [link]

I have before me six different six-digit numbers, whose sum also contains six digits. Each of the 42 digits has one of only two values. If I told you the sum, you would be able to identify all six numbers.

What is the sum?

[enigma1702]

Advertisements

21 responses to “Enigma 1702: All the sixes

  1. Jim Randell 13 June 2012 at 5:53 pm

    Here’s my first stab at a solution in Python. It runs in 6.2s.

    from itertools import combinations
    from collections import defaultdict
    from enigma import irange, printf
    
    # all six numbers must start with the digit 1 (= a)
    # and the other number (b) must be 6, 7, 8 or 9
    
    r = defaultdict(list)
    a = 1
    for b in irange(6, 9):
      # make the numbers that are combinations of these two digits
      numbers = list(a * int("{:b}".format(32 + i)) + b * int("{:b}".format(31 - i)) for i in range(32))
    
      # pick 6 of the numbers
      ds = set((str(a), str(b)))
      for ns in combinations(numbers, 6):
        s = sum(ns)
        # check the sum uses only the required two digits
        if not set(str(s)).issubset(ds): continue
        print(s, ns)
        r[s].append(ns)
    
    # find unique sums
    for s, ns in r.items():
      if len(ns) != 1: continue
      printf("sum = {s}, numbers = {ns[0]}")
    

    Solution: The sum is 818181.

  2. Brian Gladman 13 June 2012 at 9:51 pm

    Here is mine:

    
    # The highest digits must all be 1, and their sum with any
    # carries must be 6, 7, 8 or 9.   If this digit is d, the
    # sum of the 6 lowest digits is 6 + (d - 1) * n -- so if d
    # is odd, this is even and the lowest digit of the sum is
    # even and cannot be d.  So d is 6 or 8.
    
    from collections import defaultdict
    from itertools import product, combinations
    
    dct = defaultdict(list)
    # the second digit used (the first is 1)
    for d in ('6', '8'): 
      
      # generate numbers with a 1 and five digits of 1 or d
      list_numbers = []
      for t in product(('1', d),repeat=5):
        list_numbers += [100000 + int(''.join(t))]
      
      # now take these six at a time
      for comb in combinations(list_numbers, 6):
        total = sum(comb)
        # look for sums with only our two digits
        if set(str(total)) == set(('1', d)):
          dct[total] += [comb]
    
    # output any with unique sums
    for s in dct:
      if len(dct[s]) == 1:
        print(s, dct[s][0])
    
    • Jim Randell 13 June 2012 at 10:24 pm

      I think it’s easy to eliminate the case of the second digit being 6 with a bit of analysis. If it is there can be no carry to the leftmost column in the sum, so the previous column must all be 1s. Then the same reasoning applies to the previous column to that, and so on. So all six numbers would be 111111, but we are asked to find six different numbers. Combined with your reasoning it follows that the second digit must be 8.

  3. Brian Gladman 13 June 2012 at 10:35 pm

    Thanks Jim, I gave up the analysis too quickly – coding in Python is just too tempting!

    • Jim Randell 14 June 2012 at 2:01 pm

      I like to try and do the minimum amount of analysis that lets me write a program that runs in a reasonable amount of time.

      My first program started considering all possible pairs of digits, but it was clearly not going to come up with a solution in a reasonable time (in the end it took 2h4m, and found the same solution), so while it was running I had a bath and a think, and it seemed fairly obvious to me that the six 6-digit numbers must all start with the digit 1, and that the sum must start with the other digit.

      In fact, it only takes 9s to run a program that tries all possible second digits, but it seemed just as obvious that the first digit of the sum must be 6 + some carry, so I let Python take it from there. It only took 6s so I was happy to post it as a solution.

      Even though it doesn’t seem much of a leap to eliminate 6 it’s always nice to have the program confirm that cases you think you have eliminated analytically don’t, in fact, give a solution!

  4. arthurvause 15 June 2012 at 2:58 pm

    I got to the point of deducing that one digit has to be one and the other digit has to be 6 or 8, then fired up IDLE with this code. Not the fastest, but concise.

    import itertools
    for d in [6,8]:
        s , p =[], []
        for n in range(6):
          p+= [100000 + 10000*x[0]+1000*x[1]+100*x[2]+10*x[3]+x[4]  for x in set(itertools.permutations( [1]*n + [d]*(5-n)))]
        s = [sum(c) for c in itertools.combinations(p,6) if set(str(sum(c)))==set(str(10+d))]
        for v in set(s):
          print v, s.count(v)
    
  5. Brian Gladman 15 June 2012 at 3:54 pm

    I think your is far too long Arthur 🙂

    from itertools import product, combinations 
    for d in (set(('1', '6')), set(('1', '8'))):
      n = [100000 + int(''.join(t)) for t in product(d, repeat=5)]
      s = set(sum(c) for c in combinations(n, 6) if set(str(sum(c))) == d)
      [print(v, len(s)) for v in s]
    
  6. Brian Gladman 15 June 2012 at 4:05 pm

    Except that it is different 😦

  7. Brian Gladman 15 June 2012 at 4:19 pm

    Corrected:

    from itertools import product, combinations 
    for d in (set(('1', '6')), set(('1', '8'))):
      n = [100000 + int(''.join(t)) for t in product(d, repeat=5)]
      s = [sum(c) for c in combinations(n, 6) if set(str(sum(c))) == d]
      [print(v) for v in s if s.count(v) == 1]
    
  8. Brian Gladman 15 June 2012 at 4:20 pm
    from itertools import product, combinations 
    for d in (set(('1', '6')), set(('1', '8'))):
      n = [100000 + int(''.join(t)) for t in product(d, repeat=5)]
      s = [sum(c) for c in combinations(n, 6) if set(str(sum(c))) == d]
      [print(v) for v in s if s.count(v) == 1]
    
    • arthurvause 15 June 2012 at 6:30 pm

      A really succinct piece of code, Brian.

      • arthurvause 15 June 2012 at 6:31 pm

        or maybe

        from itertools import product, combinations 
        for d in (set(('1', '6')), set(('1', '8'))):
          n = [100000 + int(''.join(t)) for t in product(d, repeat=5)]
          s = [sum(c) for c in combinations(n, 6) if set(str(sum(c))) == d]
          print [v for v in s if s.count(v) == 1]
        
        • Jim Randell 16 June 2012 at 10:02 am

          I can cram it all into a single expression (excluding imports) by using a Counter object:

          from itertools import product, combinations
          from collections import Counter
          
          for x in (Counter(t for t in (sum(c) for c in combinations((int('1' + ''.join(p)) for p in product(ds, repeat=5)), 6)) if set(str(t)).issubset(ds)) for ds in (set(s) for s in ['18'])): print("\n".join("{r[0]} => {r[1]}".format(r=r) for r in x.most_common()))
          

          Although I’m not sure it helps with readability.

          • Brian Gladman 16 June 2012 at 11:27 am

            And it seems that reducing line or character counts in programs is not good for performance either 🙂

            my original code: 42 function calls in 0.866 seconds
            my five liner: 124 function calls (120 primitive calls) in 0.784 seconds
            your one liner: 906333 function calls (906329 primitive calls) in 1.962 seconds

            A lot of function calls are evidently not good news, although I didn’t expect my five liner to beat my original code (all of these only consider the case with 8 as the second digit).

            • Jim Randell 16 June 2012 at 12:28 pm

              Interestingly Python3 seems to count function calls differently from Python2, I get the following running the programs under Python 3.2, for what I think are the same programs:

              906232 function calls in 1.689 seconds
              906260 function calls in 1.131 seconds
              1812546 function calls (1812536 primitive calls) in 1.485 seconds

              They all seem to be performing pretty similarly. My last one gets twice the count because it uses set.issubset(), rather than equality to check the required digits are used, as I decided that this was a strictly more correct interpretation of the conditions. (Although it is easy to see that the sum must contain both the digits).

              • Brian Gladman 16 June 2012 at 2:27 pm

                My timings were with pypy-1.9 but checking on Python 3.2 on x64 Windows gives completely different rankings:

                my original: 906271 function calls in 1.975 seconds
                my five liner: 906395 function calls (906383 primitive calls) in 1.392 seconds
                your one liner: 1812561 function calls (1812549 primitive calls) in 0.287 seconds

                But if I go back to pypy and replace issubset(ds) with == ds, I then get:

                141 function calls (137 primitive calls) in 0.003 seconds

                So it seems that you might be paying a high price in performance for your principles 🙂

  9. Brian Gladman 15 June 2012 at 6:59 pm

    Hi Arthur, I did it the other way as I was trying to exactly duplicate your output without adding another line. But I didn’t find any way of doing it 😦

    • arthurvause 16 June 2012 at 7:36 am

      My change to the last line was just to eliminate a syntax error message from the line
      [print(v) for v in s if s.count(v) == 1]
      Would the message be due to the version I am running (Python 2.7.3 on 64 bit Windows 7)?

      • Brian Gladman 16 June 2012 at 9:50 am

        Yes, I am running 3.2.3, which has a number of new features that I want to get used to. But it still has limited support if you make a lot of use of external libraries.

  10. Liam O'Hara 15 June 2012 at 9:08 pm

    Hi folks. Just a thank you for an interesting site with stimulating comments. I sometimes write embarassingly clumsy programs in BBC Basic to solve these problems. Your pretty little programs make me want to push myself to learn Python.

    • Jim Randell 16 June 2012 at 10:30 am

      Hi Liam. Glad you like the site. I’ve solved a few of the puzzles using BBC BASIC (running on an BBC Emulator), see Enigma 45, Enigma 1561 and Enigma 1696. Although really those are all re-codings of Python programs.

      Once you get used to the idea that Python uses indentation to identify blocks, you can write some pretty readable, compact code. Especially if you make use of the wealth of built-in libraries. I’ve been using Python for a few years now and find it an excellent general purpose language.

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: