Conversión de números primos

Question

Duplicar posible:
Help with algorithm problem from SPOJ

Encontramos este pregunta de la entrevista. Dado dos números primos de n dígitos, convierta el primer número primo en el segundo cambiando un dígito a la vez. Los números intermedios también deben ser primos. Esto debe hacerse en la cantidad mínima de pasos (verificar la primalidad y cambiar un dígito se consideran pasos)

P. ej. convertir 1033 a 8179 (1033-> 1733-> 3733 -> .......-> 8179)

Answer 1

bonito reto para un lluvioso lunes por la noche (es aquí, de todos modos!). Esto se puede hacer usando Dijkstra's algorithm. El primer paso es crear un graph que contenga todos los números primos de 4 dígitos. Luego use el algoritmo de Dijkstra para encontrar la ruta más corta entre los primos de inicio/final. Aquí hay una implementación en Python:

#! /usr/bin/python -tt 

# run as: findpath start end 

import sys 

(start, end) = map(int, sys.argv[1:3]) 

# http://primes.utm.edu/lists/small/10000.txt 
f = open("10000.txt", "r") 
lines = f.readlines() 
f.close 
lines = lines[4:-1] # remove header/footer 
all = "".join(lines) # join lines 
all = all.split() 
all = map(int, all) 

# only want the 4-digit primes 
fourdigit = [p for p in all if 1000 <= p and p <= 9999] 

# returns digits in a number 
digits = lambda x: map(int, str(x)) 

# cache of digits for each prime 
digits_for_nums = {} 

# returns digits in a number (using cache) 
def digits_for_num(x): 
    global digits_for_nums 
    if x not in digits_for_nums: 
     digits_for_nums[x] = digits(x) 
    return digits_for_nums[x] 

# returns 1 if digits are same, 0 otherwise 
diff = lambda pair: 1 if pair[0] == pair[1] else 0 

# computes number of identical digits in two numbers 
def distance(a, b): 
    pair = (a, b) 
    pair = map(digits_for_num, pair) 
    pair = zip(pair[0], pair[1]) 
    pair = map(diff, pair) 
    same = sum(pair) 
    return same 

# adjacency list representation of graph of primes 
edges = {} 

# construct graph 
for a in fourdigit: 
    edges[a] = [] 
    for b in fourdigit: 
     if distance(a, b) == 3: 
      edges[a].append(b) 

infinity = sys.maxint 

def smallest(): 
    global dist, Q 
    minimum = infinity 
    which = None 
    for v in Q: 
     if dist[v] <= minimum: 
      which = v 
      minimum = dist[v] 
    return which 

# Dijkstra's algorithm 
dist = {} 
previous = {} 
Q = edges.keys() 
for v in Q: 
    dist[v] = infinity 
    previous[v] = None 
dist[start] = 0 
while len(Q) > 0: 
    u = smallest() 
    if dist[u] == infinity: 
     break 
    Q.remove(u) 
    for v in edges[u]: 
     alt = dist[u] + 1 
     if alt < dist[v]: 
      dist[v] = alt 
      previous[v] = u 

# get path between start/end nodes 
num = end 
path = [num] 
while num != start: 
    num = previous[num] 
    path.insert(0, num) 
print path 

Answer 2

Este es (un caso especial de) el problema de ruta más corta. Está buscando una ruta mínima entre dos vértices especificados, a través del gráfico donde los vértices son los primos, y los vértices están conectados por un borde si y solo si difieren exactamente en un dígito cuando se expresan en la base 10. Todos los bordes tienen peso 1.

En ausencia de una mejor idea para la estructura particular de este caso especial: para 4 dígitos esto seguramente se puede completar en un tiempo insignificante con su algoritmo favorito de búsqueda de ruta.

Editar: Vaya, solo noté que "verificar la primalidad" es un paso.

Ya no entiendo la pregunta. ¿Cuántos números tiene que "verificar la primalidad" para producir la cadena 1033 -> 1733 -> 3733? Si uso un tamiz para encontrar todos los números primos menores que 10000, ¿cuántos "pasos" se han tomado?

Answer 3

El mejor enfoque es probablemente depth-first search with iterative deepening, ya que se solicita el número mínimo de pasos. La profundidad inicial sería la cantidad de dígitos que son diferentes entre los dos números.

Answer 4

Esto se puede considerar como un problema de gráfico. Intentaría algo así:

• Generar todos los números primos de N digitos (P) sin el comienzo de la prima (A) y el final de la prima (B).
• Calcula la distancia de Hamming de A a todos los P, selecciona los que tienen una distancia de 1, configúralos como secundarios de A.
• Repite esto hasta que todos los primos de P hayan sido colocados en el gráfico o se haya encontrado un camino hacia B. .
• tomar el camino más corto desde A a B.