S2T2

Jim Randell 9:49 am on 28 September 2021 Permalink Reply
Tags: by: Graham Smithers ( 82 )   

• 

  Jim Randell 9:50 am on 28 September 2021 Permalink | Reply

  This Python program runs in 245ms.

  Run: [ @replit ]

  from enigma import group, unpack, powers, inf, is_duplicate, ordered, nsplit, intersect, nconcat, subsets, is_prime, find, update, printf
  
  # collect numbers by digit content
  def numbers(s):
    def generate():
      for n in s:
        if n > 9876543210: break
        # only collect numbers with distinct digits
        if is_duplicate(n): continue
        yield (ordered(*nsplit(n), reverse=1), n)
    return group(generate(), by=unpack(lambda ds, n: ds), f=unpack(lambda ds, n: n))
  
  cubes = numbers(powers(0, inf, 3))
  squares = numbers(powers(0, inf, 2))
  
  divides = lambda n, ds: sum(d != 0 and n % d == 0 for d in ds)
  
  # select distinct elements from each set
  def select(ss, xs):
    i = find(xs, None)
    if i == -1:
      yield xs
    else:
      # choose an elements from ss[i]
      for x in ss[i]:
        if x not in xs:
          yield from select(ss, update(xs, [(i, x)]))
  
  # look for keys common to squares and cubes
  for ds in intersect(s.keys() for s in (squares, cubes)):
    k = len(ds)
  
    # find rearrangements (we need at least 6)...
    rs = set(nconcat(*s) for s in subsets(ds, size=k, select="P") if s[0] > 0)
    if len(rs) < 6: continue
  
    # ... divisible by k
    r1s = set(n for n in rs if n % k == 0)
    if not r1s: continue
  
    # ... divisible by all but one of the digits in ds
    r2s = set(n for n in rs if divides(n, ds) == k - 1)
    if not r2s: continue
  
    # ... primes
    r3s = set(n for n in rs if is_prime(n))
    if not r3s: continue
  
    # select distinct members for each set
    n = nconcat(*ds)
    for xs in select([[n], cubes[ds], squares[ds], r3s, r1s, r2s], [None] * 6):
      printf("password = {n}")
      printf("-> cubes = {rs}", rs=cubes[ds])
      printf("-> squares = {rs}", rs=squares[ds])
      printf("-> primes = {r3s}")
      printf("-> divisible by {k} = {r1s}")
      printf("-> divisible by all but one of {ds} = {r2s}")
      printf("-> selected = {xs}")
      break  # only need one example
  

  Solution: The password is 9721.

  The program ensures five different rearrangements of the password satisfying the conditions can be made, for example:

  9721 = password
  2197 = cube
  7921 = square
  2179 = prime
  7912 = divisible by 4 (length of password)
  1792 = divisibly by 7, 2, 1 (but not 9)

  In fact there are 50 different sets of rearrangements that we could choose for this particular password.

  ---

  We can do some analysis to reduce the number of passwords considered by looking at digital roots (which are unchanged by rearrangement):

  the digital root of a square is 1, 4, 7, 9
  the digital root of a cube is 1, 8, 9
  the digital root of prime (except 3) is 1, 2, 4, 5, 7, 8

  So we need only consider passwords with a digital root of 1. (At this point considering cubes leads to 12 candidate passwords).

  Also, there must be at least 6 different rearrangements, so we need at least 3 digits, but it cannot have exactly 3 digits, as then the requirement for a rearrangement divisible by the number of digits would require a rearrangement that is divisible by 3, which would also have a digital root that was divisible by 3. (At this point considering cubes leads to 10 candidate passwords).

  Similarly, the number cannot have 9 digits, as it would have to have a rearrangement with a digital root of 9. Nor 10 digits, as again, the digital root would have to be 9.

  And if the password had length 6, it would have to have a rearrangement divisible by 6, which would require the rearrangement to be divisible by 3, and so its digital root would also be divisible by 3.

  So the password has 4, 5, 7, or 8 digits, and a digital root of 1. (At this point considering cubes leads to 6 candidate passwords).

  Additionally the password is not divisible only one of its digits, and it cannot be divisible by 0, 3, 6, 9, so no more than one of those four digits can occur in it.

  This is enough to narrow the password down to a single candidate, which gives the answer to the puzzle. (Although for completeness we should check that the appropriate rearrangements can be made).

  LikeLike

• 

  Hugh Casement 1:36 pm on 28 September 2021 Permalink | Reply

  All six rearrangements ending in 2 are integer multiples of 4 (and of course of 1 and 2).
  1279, 1297, 2179, 2719, 2791, 2917, 2971, 7129, 7219, 9127, 9721 are all prime.
  I have certainly known more satisfying Teasers.

  LikeLike

• 

  Frits 12:02 pm on 4 October 2021 Permalink | Reply

  The singles and lst2 logic is not really needed as Jim’s select function is sufficient.
  The program runs in 15ms.

   
  from enigma import is_cube, is_square, is_prime, find, update
  from itertools import permutations as perm
  
  # select distinct elements from each row
  def select(ss, xs):
    i = find(xs, None)
    if i == -1:
      yield xs
    else:
      # choose an elements from ss[i]
      for x in ss[i]:
        if x not in xs:
          yield from select(ss, update(xs, [(i, x)]))
  
  def check(n):
    # we need 6 arrangements
    
    # 0: I can rearrange the digits to form a perfect cube.
    # 1: A further rearrangement gives a perfect square.
    # 2: Another rearrangement gives a prime number.
    # 3: A rearrangement that is divisible by the number of digits.
    # 4: A rearrangement that is divisible by all but one of its digits.
    # 5: original number
  
    s = str(n)
    ndigits = len(s)
    lst = [[] for _ in range(5)]
    
    # check all permutations of original number
    for p in perm(s):
      m = int("".join(p)) 
      
      if m == n: continue
    
      if is_cube(m): 
        lst[0] += [m]
      if is_square(m): 
        lst[1] = lst[1] + [m]
      if is_prime(m): 
        lst[2] += [m]
      if m % ndigits == 0: 
        lst[3] += [m]
      if sum(x != '0' and m % int(x) == 0 for x in p) == ndigits - 1: 
        lst[4] += [m]
        
    # if any row is empty return False
    if any(not x for x in lst): return False
    
    # add 6th arrangement (original number)
    lst += [[n]]
    
    singles = [x[0] for x in lst if len(x) == 1]
    
    # build list of non-singles with numbers not occurring in singles
    lst2 = [[y for y in x if y not in singles] for x in lst if len(x) > 1]  
    lngth = len(lst2)
    
    # if each remaining row contains enough items return True
    if all(len(x) >= lngth for x in lst2):
      return True
    
    # select distinct members for each row
    for x in select(lst, [None] * 6):
      return True
    
    return False
  
  # add digit to each number in the list so that order remains decreasing
  def addLastDigit(li=range(1, 10)):
    lngth = len(str(li[0])) if li else 0
    return [10 * n + i for n in li for i in range(10 - lngth) if i < (n % 10)]
        
        
  # list of 3-digit numbers with different digits written in decreasing order
  nums = addLastDigit(addLastDigit())
  
  while True:
    for n in nums:
      if check(n):
        print("password:", n)
        break  # only need one example
    else:  # no break
      if len(str(nums[0])) > 9: break
      # add another digit
      nums = addLastDigit(nums)
      continue
      
    break    # break if nested break occurred 
  

  LikeLike