S2T2

Jim Randell 4:32 pm on 21 July 2023 Permalink Reply
Tags: by: Edmund Marshall ( 10 )   

• 

  Jim Randell 5:10 pm on 21 July 2023 Permalink | Reply

  This Python program runs in 65ms. (Internal run time is 4ms).

  Run: [ @replit ]

  from enigma import (irange, subsets, gcd, is_duplicate, printf)
  
  # possible ages (no repeated digits)
  ages = list(n for n in irange(65, 99) if n % 11 > 0)
  
  # find pairs of ages with different digits that are coprime
  pairs = list((x, y) for (x, y) in subsets(ages, 2) if gcd(x, y) == 1 and not is_duplicate(x, y))
  
  # extend the pairs to triples
  triples = list()
  for (x, y) in pairs:
    for z in ages:
      if z > y and gcd(x, z) == 1 and gcd(y, z) == 1 and not is_duplicate(x, y, z):
        triples.append((x, y, z))
  
  # choose <k> more pairs from <ps>
  def choose(k, ps, ns, rs):
    if k == 0:
      yield rs
    else:
      # choose the next pair
      for (i, (a, b)) in enumerate(ps):
        # check numbers are all different
        if a in ns or b in ns: continue
        # and are pairwise coprime
        if not all(gcd(a, n) == 1 and gcd(b, n) == 1 for n in ns): continue
        # solve for remaining pairs
        yield from choose(k - 1, ps[i + 1:], ns + (a, b), rs + [(a, b)])
  
  # solve the puzzle
  def solve():
    # consider back rows in order (largest sum to smallest sum)
    for r1 in sorted(triples, key=sum, reverse=1):
      # find 4 more pairs to go with these
      yield from choose(4, pairs, r1, [r1])
  
  # find the first solution
  for rs in solve():
    printf("rows = {rs}")
    break  # we only need one solution
  

  Solution: The age of the eldest passenger on the back row is 95.

  The ages in the rows are:

  (73, 86, 95) (back row)
  (67, 91)
  (71, 89)
  (79, 81) or (79, 83)
  (83, 97) or (81, 97)

  The sum of the ages in the back row being 254.

  LikeLike

• 

  Frits 1:52 pm on 24 July 2023 Permalink | Reply

  from math import gcd
  
  diffdgts = lambda *ns: len(set(s := ''.join(str(n) for n in ns))) == len(s)
  
  # check that element <a> is coprime with elements in <s>
  cp = lambda a, s: all(gcd(a, x) == 1 for x in s)
                    
  # decompose <t> into <k> increasing numbers from <ns> with all different digits
  def decompose(t, k, ns, s=[]):
    if k == 1:
      if t in ns and t > s[-1] and diffdgts(*(s_ := s + [t])):
        yield s_
    else:
      for (i, n) in enumerate(ns):
        if not diffdgts(*(s_ := s + [n])): continue
        yield from decompose(t - n, k - 1, ns[i + 1:], s_)
  
  #  A B
  #  C D
  #  E F
  #  G H
  # I J K
  
  sols = set()
  # check sum of ages from (90+80+70+6+5+3) to (80+70+60+0+1+3)
  for soa in range(254, 213, -1):
    # back row
    for I, J, K in decompose(soa, 3, [x for x in range(65, 99) if x % 11]):
      # check if I, J and K are coprime
      if not cp(I, [J]): continue
      if not cp(K, [I, J]): continue
      
      for A in range(65, 85):
        if not cp(A, sA := [I, J, K]):  continue
        for B in range((A // 10 + 1) * 10, 99):
          if not cp(B, sB := sA + [A]) or not diffdgts(A, B): continue
          for C in range(A + 1, 86):
            if not cp(C, sC := sB + [B]):  continue
            for D in range((C // 10 + 1) * 10, 99):
              if not cp(D, sD := sC + [C]) or not diffdgts(C, D): continue
              for E in range(C + 1, 87):
                if not cp(E, sE := sD + [D]):  continue
                for F in range((E // 10 + 1) * 10, 99):
                  if not cp(F, sF := sE + [E]) or not diffdgts(E, F): continue
                  for G in range(E + 1, 88):
                    if not cp(G, sG := sF + [F]):  continue
                    for H in range((G // 10 + 1) * 10, 99):
                      if not cp(H, sG + [G]) or not diffdgts(G, H): continue
                      # don't assume there is a unique answer
                      sols.add(K)
              
    if sols:
      print(f"answer: {', '.join(str(s) for s in sols)} in years")
      break   # we don't need to check a lower sum of ages   
  

  LikeLike