S2T2

Jim Randell 6:50 am on 18 May 2025 Permalink Reply
Tags: by: Andrew Skidmore ( 85 )   

• 

  Jim Randell 7:06 am on 18 May 2025 Permalink | Reply

  A brute force approach gives a short and acceptably fast program.

  The following Python program runs in 77ms. (Internal runtime is 8.4ms).

  from enigma import (irange, nconcat, subsets, is_prime, is_square_p, printf)
  
  # shift digits <ds> by increment <i> (modulo <n>)
  shift = lambda ds, i, n=10: ((d + i) % n for d in ds)
  
  # consider possible 3 digit numbers
  for (X, Y, Z) in subsets(irange(1, 9), size=3, select='P'):
    # calculate each of the "other" numbers
    ns = list(nconcat(shift((0, X, Y, Z), i)) for i in irange(1, 9))
    # (exactly) 2 are squares
    if sum(is_square_p(n) for n in ns) != 2: continue
    # none are prime
    if any(is_prime(n) for n in ns): continue
    # output solution
    printf("0{X}{Y}{Z} -> {ns}")
  

  Solution: The number Phil has to remember is 912.

  So the combination is: 0912.

  Of the other numbers visible (1023, 2134, 3245, 4356, 5467, 6578, 7689, 8790, 9801):

  4356 = 66^2
  9801 = 99^2

  There is one other combination that gives 2 squares: 0327.

  Of the other numbers visible (1438, 2549, 3650, 4761, 5872, 6983, 7094, 8105, 9216):

  2549 is prime
  4761 = 69^2
  6983 is prime
  9216 = 96^2

  So this fails the requirement that none of the other numbers is prime.

  And these are the only 2 combinations that give more than one square among the “other” numbers.

  LikeLike

  • 

    Jim Randell 10:39 am on 18 May 2025 Permalink | Reply

    Here is a slightly longer, but faster, alternative approach.

    It considers the possible 4-digit squares, and then looks for 2 that give the same combination number (0xyz).

    It has an internal runtime of 253µs.

    from enigma import (defaultdict, irange, nsplit, nconcat, is_prime, join, printf)
    
    # shift digits <ds> by increment <i> (modulo <n>)
    shift = lambda ds, i, n=10: ((d + i) % n for d in ds)
    
    # count 4-digit squares by the combination (smallest number on the lock)
    m = defaultdict(int)
    for i in irange(32, 99):
      ds = nsplit(i * i)
      if len(set(ds)) != len(ds): continue
      # reduce the first digit to zero
      k = tuple(shift(ds, -ds[0]))
      m[k] += 1
    
    # consider combinations that give exactly 2 squares
    for (k, n) in m.items():
      if n != 2: continue
    
      # construct the 9 "other" numbers
      ns = list(nconcat(shift(k, i)) for i in irange(1, 9))
      # none of them are prime
      if any(is_prime(n) for n in ns): continue
    
      # output solution
      printf("{k} -> {ns}", k=join(k))
    

    LikeLike

    • 

      Frits 11:04 am on 18 May 2025 Permalink | Reply

      Nice, I was also considering possible 4-digit squares but was using the less efficient “itertools.combinations”.

      LikeLike