Programming Praxis

2 Responses to “Prime Chains”

1. Paul said

   July 5, 2017 at 7:10 AM

   In Python. This is taken from the book Python Algorithms by Hetland. In the book code is given for finding chains of words from a dictionary. I only had to change the method “variants”. The A* method is used to find the shortest path with a distance heuristic that counts the number of mismatches in the numbers.

   def a_star(G, s, t, h):
       P, Q = {}, [(h(s), None, s)]                # Pred and queue w/heuristic
       while Q:                                    # Still unprocessed nodes?
           d, p, u = heappop(Q)                    # Node with lowest heuristic
           if u in P: continue                     # Already visited? Skip it
           P[u] = p                                # Set path predecessor
           if u == t: return d - h(t), P           # Arrived! Ret. dist and preds
           for v in G[u]:                          # Go through all neighbors
               w = G[u][v] - h(u) + h(v)           # Modify weight wrt heuristic
               heappush(Q, (d + w, u, v))          # Add to queue, w/heur as pri
       return inf, None                            # Didn't get to t
   
   class PrimeChain(object):
   
       def __init__(self):
           self.M = {}
   
       def variants(self, strn):
           va = list(strn)
           for i, c in enumerate(va):
               digits = "123456789" if i == 0 else "0123456789"
               for d in digits:
                   if d == c:
                       continue
                   va[i] = d
                   newstrn = "".join(va)
                   if is_prime(int(newstrn)):
                       yield newstrn
                   va[i] = c
   
       def __getitem__(self, strn):
           if strn not in self.M:
               self.M[strn] = dict.fromkeys(self.variants(strn), 1)
           return self.M[strn]
   
       def heuristic(self, u, v):
           return sum(a != b for a, b in zip(u, v))
   
       def chain(self, s, t, h=None):
           if h is None:
               def h(v):
                   return self.heuristic(v, t)
           _, P = a_star(self, s, t, h)
           if P is None:
               return [s, None, t]
           u, p = t, []
           while u is not None:
               p.append(u)
               u = P[u]
           p. reverse()
           return p
   
   G = PrimeChain()
   print(G.chain("71549", "10067"))
   p1 = 76520965667
   p2 = 59340926171
   print(G.chain(str(p1), str(p2)))
   
   """
   ['71549', '71569', '71069', '11069', '10069', '10067']
   ['76520965667', '70520965667', '70540965667', '79540965667', '79040965667',
   '79040965657', '79040965651', '79040966651', '79040966671', '59040966671',
   '59040926671', '590409261 71', '59340926171']
   """
   
2. Rutger said

   July 6, 2017 at 12:11 PM

   Hi,

   Created a Depth-First search algorithm. This, off-course, goes bananas without a proper heuristic on getting closer to the target prime. This was done using the Hamming distance. Also set a limit of max depth (best) = 100 due to recursion depth limits.

   Also found out that the is_prime function has many calls with the same argument, so cached the results using memoization.

   I recon BFS would be a better approach judging from your solutions, anyway here’s my result:

   import random
   import string
   
   def memoize(f):
       memo = {}
       def helper(x):
           if x not in memo:            
               memo[x] = f(x)
           return memo[x]
       return helper
   
   @memoize
   def is_prime(number):
     # wheel / trial division
     for i in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199):
       if not (number % i):
         return False
     i = 203
     while i <= number**0.5:
         if not (number % i):
             return False
         i += 2
     return True
   
   digits_with_0 = string.digits
   digits_without_0 = string.digits.replace("0", "")
   
   
   def prime_neighbours(number):
     n = str(number)
     result = []
     for i,v in enumerate(n):
       if i == 0:
         digits = digits_without_0
       else:
         digits = digits_with_0
       for d in digits:
         neighbour = list(n)
         if d != neighbour[i]:
           neighbour[i] = d
         p = int("".join(neighbour))
         if is_prime(p):
           result.append(p)
     return result
   
   best = 100
   
   def find_chain(current_chain, target, solutions):
     global best
     # if random.random() < 0.1:
       # print(best, current_chain)
     solutions = []
     n = prime_neighbours(current_chain[-1])
     # add hamming distance for sorting
     z = [(sum(c1 == c2 for c1, c2 in zip(list(str(p1)), list(str(target)))), p1) for p1 in n]
     z.sort(reverse=True)
     for dummy, p2 in z:
       if len(current_chain) + 1 < best and p2 not in current_chain:
         if p2 == target:
           solutions.append(current_chain + [p2])
           print("#", len(solutions[-1]), solutions[-1])
           best = len(current_chain)+1
         else:
           for s in find_chain(current_chain+[p2], target, solutions):
             solutions.append(s)
     return solutions
   
   
   
   start = 71549
   end = 10067
   
   print(find_chain([start], end, []))