S2T2

Jim Randell 6:14 pm on 1 June 2022 Permalink Reply
Tags: by: Stephen Hogg ( 63 )   

• 

  Jim Randell 6:41 pm on 1 June 2022 Permalink | Reply

  The following Python program runs in 70ms. (Internal run time is 9.7ms).

  Run: [ @replit ]

  from enigma import (irange, divisors, filter2, div, reverse, singleton, printf)
  
  # generate <k> increasing values from <vs> with product <v>
  def decompose(v, k, ds, ss=[]):
    if k == 1:
      if v in ds:
        yield ss + [v]
    elif not (len(ds) < k):
      for (i, d) in enumerate(ds):
        v_ = div(v, d)
        if v_ is not None:
          yield from decompose(v_, k - 1, ds[i + 1:], ss + [d])
  
  # generate candidate values for geometric mean <gm>
  def generate(gm):
    # find the remaining values
    ds = list(d for d in divisors(gm, 6) if 9 < d < 100 and d != gm)
    for vs in decompose(gm**6, 6, ds):
      # there are 2 values less than gm (and 4 values greater)
      (lt, gt) = filter2((lambda x: x < gm), vs)
      if len(lt) != 2: continue
      # there is a gm/3 value, but not a gm/2 value
      if (gm // 3 not in lt) or (div(gm, 2) in lt): continue
      # there is a gm*2 value, but not a gm*3 value
      if (gm * 2 not in gt) or (gm * 3 in gt): continue
      # return the sequence, Mo - Su
      yield reverse(gt) + [gm] + reverse(lt)
  
  # consider values for the geometric mean: gm/3 and gm*2 are 2-digit values
  for gm in irange(30, 49, step=3):
    # is there only a single candidate solution?
    ns = singleton(generate(gm))
    if ns:
      # output solutions
      printf("{ns}")
  

  Solution: The numbers are (Mon – Sun): 96, 72, 64, 54, 48, 32, 16.

  The geometric mean is 48, and there is a value twice the geometric mean (98), but not three times (144). There is also a value one third of the geometric mean (16), but not one half (24).

  ---

  This is the only possible sequence with a geometric mean of 48.

  However there are other possible sequences with a geometric mean of 42:

  (98, 84, 81, 49, 42, 14, 12)
  (98, 84, 54, 49, 42, 18, 14)
  (84, 63, 56, 49, 42, 27, 14)
  (84, 63, 54, 49, 42, 28, 14)

  LikeLike

  • 

    Jim Randell 6:49 am on 2 June 2022 Permalink | Reply

    And here is an even faster version:

    If g is the geometric mean we have a decreasing sequence of values (Mon – Sun):

    (a, b, c, d, g, e, f)

    Such that:

    g^7 = a × b × c × d × g × e × f

    And we know one of the values greater than g (i.e. one of (a, b, c, d)) has a value of 2g, and one of the values less than g (i.e. one of (e, f)) has a value of (g / 3) (which tells us g is a multiple of 3).

    Hence:

    (3/2)(g^4) = [3 of (a, b, c, d)] × [1 of (e, f)]

    Which tells us g is also a multiple of 2.

    Furthermore (g / 3) is a 2-digit value, so g ≥ 30, and 2g is also a 2-digit value, so g < 50.

    This Python program considers possible values for the geometric mean, and finds the three remaining values higher than the mean, and the value lower than the mean. If a mean leads to a single possible set of values, then we have found the solution.

    It runs in 54ms. (Internal runtime is 167µs).

    Run: [ @replit ]

    from enigma import (irange, div, diff, singleton, printf)
    
    # reversed sort
    rsort = lambda x: sorted(x, reverse=1)
    
    # find <k> increasing values from <ds> whose product divide into <v>
    # return: (<ns>, <r>) where <r> is the remainder
    def decompose(v, k, ds, ns=[]):
      if k == 0:
        yield (ns, v)
      elif not (len(ds) < k):
        for (i, d) in enumerate(ds):
          v_ = div(v, d)
          if v_ is not None:
            yield from decompose(v_, k - 1, ds[i + 1:], ns + [d])
    
    # generate candidate sequences for geometric mean <gm>
    def generate(gm):
      # find 2-digit divisors of (3/2)gm^4 greater than gm
      v = 3 * div(gm**4, 2)
      ds = diff((d for d in irange(gm + 1, 99) if v % d == 0), {2 * gm, 3 * gm})
      for (gt, r) in decompose(v, 3, ds):
        # there is no gm/2 value
        if (not 9 < r < gm) or 2 * r == gm or 3 * r == gm: continue
        # return the sequence (in decreasing order)
        yield rsort(gt + [2 * gm]) + [gm] + rsort([r, gm // 3])
    
    # consider values for the geometric mean, gm is a multiple of 6
    for gm in irange(30, 49, step=6):
      # is there only a single candidate solution?
      ns = singleton(generate(gm))
      if ns:
        # output solutions
        printf("[Mon - Sun] = {ns}")
    

    LikeLike

    • 

      Frits 1:30 pm on 2 June 2022 Permalink | Reply

      Using divisors_tuples() is slower than the decompose() method.

         
      from enigma import divisors_tuples
      
      # return entry where column <col> is unique
      def unique_col(seq, col=0):
        d = dict()
        for s in seq:
             d[s[col]] = s[col] in d
         
        return [s for s in seq if not d[s[col]]]
      
      # there is a gm/3 value and there is a 2*gm value
      # gm must also be even as gm^7 is even 
      
      sol = []
      # consider values for the geometric mean: gm/3 and gm*2 are 2-digit values
      for gm in range(30, 50, 6):
        # generate seven 2-digit numbers that multiply to gm^7
        nums = [sorted(x + (gm // 3, gm, 2 * gm), reverse = True) 
               for x in divisors_tuples(3 * (gm**4 // 2), 4) 
               if all(9 < y < 100 for y in x) 
                  and gm // 2 not in x 
                  and 3 * gm not in x]
       
        # store valid solutions
        sol += [x for x in nums if len(set(x)) == 7 and x[4] == gm]
      
      print("answer =", *unique_col(sol, 4))
      

      A basic SubstitutedExpression program takes about 5 seconds (with PyPy).

      LikeLike

• 

  Frits 2:58 pm on 2 June 2022 Permalink | Reply

  Program runs in 75ms (with PyPy).

     
  from enigma import SubstitutedExpression
  
  # the alphametic puzzle
  p = SubstitutedExpression(
    [
     # there is a gm/3 value and there is a gm*2 value
     # gm must also be even as gm^7 is even so E is even
     "(G + M) % 3 == 0",
     
     # 1.5 * GM**4 is the product 4 unknown sorted numbers AB, CD, EF and PQ
    
     "AB < GM",
     "CD > GM",
     "EF > GM",
     "CD < EF",
     
     "div(3 * GM**4 // 2, AB * CD * EF) = PQ",
     "PQ > EF",
     
     # seven different numbers
     "len(set([AB, CD, EF, PQ, GM, 2 * GM, GM // 3])) == 7",
     # friday's value equalling the geometric mean
     "sorted([AB, CD, EF, PQ, GM, 2 * GM, GM // 3])[2] == GM",
     
     # there is no 3*gm or gm/2 value
     "3 * GM not in {AB, CD, EF, PQ, GM, 2 * GM, GM // 3}",
     "GM // 2 not in {AB, CD, EF, PQ, GM, 2 * GM, GM // 3}",
     
    ],
    answer="sorted([AB, CD, EF, PQ, GM, 2 * GM, GM // 3], reverse=1)",
    d2i=dict([(0, "GACEP")] + 
             [(1, "GCEM")] +                       
             [(2, "GCE")] +
             [(3, "M")] +
             [(5, "AGM")] +
             [(6, "AG")] +
             [(7, "AGM")] +
             [(8, "AG")] +
             [(9, "AGM")]),
    distinct="",
    reorder=0,
    verbose=0,    # use 256 to see the generated code
  )
  
  # store answers
  d = dict()
  for (_, ans) in p.solve():
    d[ans[4]] = d.get(ans[4], []) + [ans]
    
  for v in d.values():
    if len(v) == 1:
      print(*v) 
  

  LikeLike