S2T2

Jim Randell 4:56 pm on 12 February 2021 Permalink Reply
Tags: by: Howard Williams ( 43 )   

• 

  Jim Randell 5:10 pm on 12 February 2021 Permalink | Reply

  (See also: Teaser 2863).

  This Python program runs in 64ms.

  Run: [ @repl.it ]

  from enigma import irange, subsets, nconcat, nsplit, diff, multiply, group, printf
  
  # total all permutations of a set of distinct digits
  psum = lambda ds: sum(nconcat(*s) for s in subsets(ds, size=len, select="P"))
  
  # count occurrences of digit d in number n
  dcount = lambda n, d: nsplit(n).count(d)
  
  # generate solutions
  def solve():
    # permissible digits
    digits = irange(1, 9)
  
    # choose the initial set of 3 digits
    for ds3 in subsets(digits, size=3):
      t3 = psum(ds3)
      # there should be three 3 digits in the total
      if not(dcount(t3, 3) == 3): continue
  
      # now add 2 more digits to the mix
      for ds in subsets(diff(digits, ds3), size=2):
        ds5 = ds3 + ds
        t5 = psum(ds5)
        # there should be five 6 digits in the total
        if not(dcount(t5, 6) == 5): continue
  
        printf("[{ds3} -> {t3}; {ds5} -> {t5}]")
        yield ds5
  
  # group solutions by product
  d = group(solve(), by=multiply)
  
  # output solutions
  if d:
    k = min(d.keys())
    for ds5 in d[k]:
      printf("{ds3} + {ds2}; product = {k}", ds3=ds5[:3], ds2=ds5[3:])
  

  Solution: The five digits are: 1, 2, 5, 8, 9.

  There are two scenarios with a minimal product of 720:

  (1) Robbie was given: 1, 5, 9; Additional digits: 2, 8.
  (2) Robbie was given: 2, 5, 8; Additional digits: 1, 9.

  The sum of all 3-digit permutations is 3330 (= 222 × 15).

  The sum of all 5-digit permutations is 6666600 = (266664 × 25).

  In total there are 16 candidate solutions, each with the same sums for the 3-digit and 5-digit permutations.

  ---

  In general, if we have a set of k different digits, then they can be rearranged in factorial(k) different ways, to form different numbers.

  And when these numbers are summed, each digit will appear factorial(k) / k = factorial(k − 1) times in each column.

  So we can calculate the total of all permutations without having to generate them all:

  from enigma import factorial, repdigit
  
  def psum(ds):
    k = len(ds)
    return factorial(k - 1) * repdigit(k) * sum(ds)
  

  In particular, for 3-digit numbers this simplifies to [[ 222 * sum(ds) ]] and for 5-digit numbers it simplifies to [[ 266664 * sum(ds) ]].

  The program above can be adapted using this analysis to give a solution with a run time of 51ms:

  from enigma import irange, subsets, nsplit, diff, multiply, Accumulator, inf, factorial, repdigit, printf
  
  # return multiplier for total sum of all permutations of a set of distinct digits
  psum = lambda k: factorial(k - 1) * repdigit(k)
  psum3 = psum(3)
  psum5 = psum(5)
  
  # count occurrences of digit d in number n
  dcount = lambda n, d: nsplit(n).count(d)
  
  # collect minimal products
  r = Accumulator(fn=min, value=inf, collect=1)
  
  # choose the set of 5 digits
  for ds5 in subsets(irange(1, 9), size=5):
    p = multiply(ds5)
    if p > r.value: continue
  
    # there should be five 6 digits in the total
    t5 = psum5 * sum(ds5)
    if not(dcount(t5, 6) == 5): continue
  
    # choose a subset of 3 digits
    for ds3 in subsets(ds5, size=3):
      t3 = psum3 * sum(ds3)
      # there should be three 3 digits in the total
      if not(dcount(t3, 3) == 3): continue
  
      # record the initial set of 3 digits, and the additional 2 digits
      r.accumulate_data(p, (ds3, diff(ds5, ds3)))
  
  # output solutions
  if r.count:
    for (ds3, ds2) in r.data:
      printf("{ds3} + {ds2}; product = {r.value}")
  

  LikeLike

  • 

    Tony Brooke-Taylor 3:11 pm on 13 February 2021 Permalink | Reply

    I think it is possible to simplify the problem to a point where the solution can be found manually. I admit I only spotted the simplifications once I had written an algorithm similar to yours Jim.

    In the 3-digit problem we can work out manually what the total must be: there is only one multiple of 222 that has three 3’s in it. Eight sets of three digits sum to the correct cofactor, of which four are symmetrical around the value 5.

    In the 5-digit problem we can also work out what the total must be: there is only one multiple of 266664 that has five 6’s in it, and I believe this is more obvious if we look at multiples of 11111. Thus we have a unique cofactor in this problem too, and the sum of the extra two digits must be the difference between the two cofactors. Only four pairs of digits make up this sum.

    If we combine the four pairs with the eight trios and deduplicate, we get ten possible sets of 5, of which six are symmetrical around the value 5.

    By trigonometry, the solution with the minimum product has the greatest distances between the central number and the others. My leap of faith is that we could also have applied this at the 3-digit stage to reduce the number of trios we needed to test.

    LikeLike

    • 

      Jim Randell 12:07 pm on 17 February 2021 Permalink | Reply

      @Tony: Once we’ve got the 8 pairs of triples that sum to 15, and we are extending them with a pair that sums to 10 (= (1,9) (2,8) (3, 7) (4,6)), then we only need to consider the first viable pair, as later ones will give a larger product.

      So we can exhaustively check the solution space by calculating only 7 products.

      ---

      Here’s some code that uses this analysis:

      from enigma import irange, Accumulator, printf
      
      # collect minimal product
      r = Accumulator(fn=min, collect=1)
      
      # look for sets of 3 digits (a, b, c) that sum to 15
      for a in irange(1, 4):
        for b in irange(a + 1, 6):
          c = 15 - (a + b)
          if not(b < c < 10): continue
      
          # and now add (d, e) that sum to 10
          for d in irange(1, 4):
            e = 10 - d
            if len({a, b, c, d, e}) != 5: continue
      
            # collect minimal product
            r.accumulate_data(a * b * c * d * e, ((a, b, c), (d, e)))
            break # only need to check the first viable (d, e) pair
      
      # output solutions
      if r.count:
        for (ds3, ds2) in r.data:
          printf("{ds3} + {ds2}; product = {r.value}")
      

      LikeLike

  • 

    Frits 10:31 am on 15 February 2021 Permalink | Reply

    @Jim,

    If you replace line 23 “t5 = psum(ds5) ” with

    t5 = 0
    for v, w, x, y, z in permutations(ds5):
      t5 += v * 10000 + w * 1000 + x * 100 + y * 10 + z
    

    your code is approx. 4.5 times faster (with Python 3.9.0).

    Maybe nconcat is not efficient if called multiple times?
    Subsets only seems to have minor overhead.

    LikeLike

    • 

      Jim Randell 12:40 pm on 15 February 2021 Permalink | Reply

      @Frits: In a program that runs pretty much instantaneously I am less concerned about coding for execution speed as I am that the program itself should be concise, clear and easy to modify (and, above all, correct).

      So using a general utility function like [[ nconcat() ]] makes it clear that I am turning a sequence of digits into a number, even if it is not the fastest way to achieve this.

      Although with a bit of analysis we find that we don’t have to construct numbers corresponding to all the permutations of the digits in order to arrive at the sum (and gives a general principle for attacking similar problems), which lets us write a program that runs even faster.

      But that is not to say I’m not at all interested in execution speed. I’ll have a look at improving [[ nconcat() ]], and another advantage of using utility functions is that if an improvement is made, every program that uses them gets the benefit.

      LikeLike

• 

  Frits 11:23 am on 13 February 2021 Permalink | Reply

  Basic version, not really optimized for speed.

  from itertools import permutations, combinations
  
  sol = set()
  for a, b, c in combinations(range(1, 10), 3):
    t1 = 0
    for x, y, z in permutations([a, b, c]):
      t1 += x * 100 + y * 10 + z
   
    # there should be three 3's in the total
    if str(t1).count("3") == 3:
      for d in [q for q in range(1, 9) if q not in {a, b, c}]:
        for e in [q for q in range(d + 1, 10) if q not in {a, b, c}]:
          t2 = 0
          for v, w, x, y, z in permutations([a, b, c, d, e]):
            t2 += v * 10000 + w * 1000 + x * 100 + y * 10 + z
          
          # there should be five 6's in the total
          if str(t2).count("6") == 5:
            # put product up front so we can use if for sorting
            sol.add(tuple([a * b * c * d * e] + sorted([a, b, c, d, e])))
    
  if len(sol):  
    print(f"answer = {sorted(sol)[0][1:]}")   
  

  LikeLike

• 

  Frits 2:07 pm on 18 February 2021 Permalink | Reply

  Partly based on Tony’s comments.

  from math import prod
  
  # Suppose a < b < c < d < e and (a + b + c + d + e) is a constant
  #
  # a * b * c * d * e is minimal 
  # if sum of distances with respect to c is maximal.
  # 
  # Proof:
  # 
  # sum of distances = (c - a) + (c - b) + (d - c) + (e - c) = d + e - a - b
  # 
  # Suppose we allow d or e to decrease with one and a or b to increase with 
  # one, so the sum stays the same. Say d' = d - 1 and b' = b + 1
  # 
  # b' * d' = (b + 1) * (d - 1) = b * d + (d - b) - 1
  # as c is between b and d we can say d - b > 1, thus d' * b' > d * b
  # so new product a * b' * c * d' * e  >  old product a * b * c * d * e
  
  # decompose number <t> into <k> different numbers from sequence <ns> 
  # so that  sum(<k> numbers) equals <t>
  # the result is already sorted on product !!
  def decompose(t, k, ns, s=[]):
    if k == 1:
      if t in ns:
        yield s + [t]
    else:
      for (i, n) in enumerate(ns):
        if not(n < t): break
        yield from decompose(t - n, k - 1, ns[i + 1:], s + [n])
  
  digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
  
  # sum permutations of 3 different digits is 222 * sum(digits)
  # last digit of sum can never be a 3 
  # so first 3 digits of sum must be all 3's
  s3 = 3340 // 222                   # sum of 3 digits
  if (s3 * 222) // 10 != 333: 
    exit()                           # no solution
  
  # sum permutations of 5 different digits is 266664 * sum(digits)
  sum5 = [x for x in range(s3 + 3, min(s3 + 18, 36)) 
          if str(266664 * x).count("6") == 5] 
          
  sol = []        
  
  for s5 in sum5:
    # we look for 5 digits a, b, c, d, e which sum to <s5>
    # and where three of them sum to <s3>
    # (a * b * c * d * e must be minimal)
  
    # choose <a> as low as possible and <e> as high as possible
    a = max(1, s5 - 30)
    e = min(9, s5 - 10)
    # d - b must be maximal
    b = max(2, s5 - 25 - a + 1)
    d = min(8, max(4, s5 - 15))
    c = s5 - (a + b + d + e)
    
    # check optimal solution 
    if len(list(decompose(s3, 3, [a, b, c, d, e]))) > 0:
      sol.append([prod([a, b, c, d, e]), (a, b, c, d, e)])
    else:
      for abcde in decompose(s5, 5, digits): 
        if len(list(decompose(s3, 3, abcde))) > 0:
          sol.append([prod(abcde), abcde])
          break  # decompose returns entries sorted on product!
    
  if len(sol) > 0:  
    sol.sort()   # sort on product
    print("answer = ", sol[0][1])
  

  LikeLike