El camino más corto para llegar de un primo a otro cambiando un solo dígito a la vez

Dados dos números primos de cuatro dígitos, supongamos 1033 y 8179, necesitamos encontrar el camino más corto de 1033 a 8179 alterando solo un dígito a la vez, de modo que cada número que obtengamos después de cambiar un dígito sea primo. Por ejemplo, una solución es 1033, 1733, 3733, 3739, 3779, 8779, 8179 

Ejemplos:

Input : 1033 8179
Output :6

Input : 1373 8017
Output : 7

Input  :  1033 1033
Output : 0

La pregunta puede ser resuelta por BFS y es bastante interesante de resolver como un problema inicial para principiantes. Primero encontramos todos los números primos de 4 dígitos hasta 9999 usando la técnica de Tamiz de Eratóstenes . Y luego usando esos números formó el gráfico usando la lista de adyacencia . Después de formar la lista de adyacencia, usamos BFS simple para resolver el problema. 

Implementación:

C++

// CPP program to reach a prime number from
// another by changing single digits and
// using only prime numbers.
#include <bits/stdc++.h>
 
using namespace std;
 
class graph {
    int V;
    list<int>* l;
public:
    graph(int V)
    {
        this->V = V;
        l = new list<int>[V];
    }
    void addedge(int V1, int V2)
    {
        l[V1].push_back(V2);
        l[V2].push_back(V1);
    }
    int bfs(int in1, int in2);
};
 
// Finding all 4 digit prime numbers
void SieveOfEratosthenes(vector<int>& v)
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
    int n = 9999;
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++) {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    // Forming a vector of prime numbers
    for (int p = 1000; p <= n; p++)
        if (prime[p])
            v.push_back(p);
}
 
// in1 and in2 are two vertices of graph which are
// actually indexes in pset[]
int graph::bfs(int in1, int in2)
{
    int visited[V];
    memset(visited, 0, sizeof(visited));
    queue<int> que;
    visited[in1] = 1;
    que.push(in1);
    list<int>::iterator i;
    while (!que.empty()) {
        int p = que.front();
        que.pop();
        for (i = l[p].begin(); i != l[p].end(); i++) {
            if (!visited[*i]) {
                visited[*i] = visited[p] + 1;
                que.push(*i);
            }
            if (*i == in2) {
                return visited[*i] - 1;
            }
        }
    }
}
 
// Returns true if num1 and num2 differ
// by single digit.
bool compare(int num1, int num2)
{
    // To compare the digits
    string s1 = to_string(num1);
    string s2 = to_string(num2);
    int c = 0;
    if (s1[0] != s2[0])
        c++;
    if (s1[1] != s2[1])
        c++;
    if (s1[2] != s2[2])
        c++;
    if (s1[3] != s2[3])
        c++;
 
    // If the numbers differ only by a single
    // digit return true else false
    return (c == 1);
}
 
int shortestPath(int num1, int num2)
{
    // Generate all 4 digit
    vector<int> pset;
    SieveOfEratosthenes(pset);
 
 
    // Create a graph where node numbers are indexes
    // in pset[] and there is an edge between two
    // nodes only if they differ by single digit.
    graph g(pset.size());
    for (int i = 0; i < pset.size(); i++)
        for (int j = i + 1; j < pset.size(); j++)
            if (compare(pset[i], pset[j]))
                g.addedge(i, j);    
     
 
    // Since graph nodes represent indexes of numbers
    // in pset[], we find indexes of num1 and num2.
    int in1, in2;
    for (int j = 0; j < pset.size(); j++)
        if (pset[j] == num1)
            in1 = j;
    for (int j = 0; j < pset.size(); j++)
        if (pset[j] == num2)
            in2 = j;
 
    return g.bfs(in1, in2);
}
 
// Driver code
int main()
{
    int num1 = 1033, num2 = 8179;
    cout << shortestPath(num1, num2);
    return 0;
}

Java

// Java program to reach a prime number from
// another by changing single digits and
// using only prime numbers.
import java.io.*;
import java.util.*;
 
class Graph {
  private int V;
  private LinkedList<Integer>[] l;
 
  // Constructor
  @SuppressWarnings("unchecked") Graph(int v)
  {
    V = v;
    l = new LinkedList[v];
    for (int i = 0; i < v; i++)
      l[i] = new LinkedList<Integer>();
  }
 
  // Function to add an edge into the graph
  void addedge(int V1, int V2)
  {
    l[V1].add(V2);
    l[V2].add(V1);
  }
 
  // Finding all 4 digit prime numbers
  static void SieveOfEratosthenes(LinkedList<Integer> v)
  {
    // Create a boolean array "prime[0..n]" and
    // initialize all entries it as true. A value in
    // prime[i] will finally be false if i is Not a
    // prime, else true.
    int n = 9999;
    Boolean prime[] = new Boolean[n + 1];
    Arrays.fill(prime, true);
 
    for (int p = 2; p * p <= n; p++) {
 
      // If prime[p] is not changed, then it is a
      // prime
      if (prime[p] == true) {
 
        // Update all multiples of p
        for (int i = p * p; i <= n; i += p)
          prime[i] = false;
      }
    }
 
    // Forming a vector of prime numbers
    for (int p = 1000; p <= n; p++) {
      if (prime[p])
        v.add(p);
    }
  }
 
  // in1 and in2 are two vertices of graph which are
  // actually indexes in pset[]
  int bfs(int in1, int in2)
  {
    int visited[] = new int[V];
    Arrays.fill(visited, 0);
    Queue<Integer> que = new LinkedList<Integer>();
    visited[in1] = 1;
    que.add(in1);
 
    while (!que.isEmpty()) {
      int p = que.poll();
      for (int i : l[p]) {
        if (visited[i] == 0) {
          visited[i] = visited[p] + 1;
          que.add(i);
        }
        if (i == in2) {
          return visited[i] - 1;
        }
      }
    }
 
    return 0;
  }
 
  // Returns true if num1 and num2 differ
  // by single digit.
  static Boolean compare(int num1, int num2)
  {
    // To compare the digits
    char[] s1 = (Integer.toString(num1)).toCharArray();
    char[] s2 = (Integer.toString(num2)).toCharArray();
    int c = 0;
    if (s1[0] != s2[0])
      c++;
    if (s1[1] != s2[1])
      c++;
    if (s1[2] != s2[2])
      c++;
    if (s1[3] != s2[3])
      c++;
 
    // If the numbers differ only by a single
    // digit return true else false
    return (c == 1);
  }
 
  static int shortestPath(int num1, int num2)
  {
    // Generate all 4 digit
    LinkedList<Integer> pset
      = new LinkedList<Integer>();
    SieveOfEratosthenes(pset);
 
    // Create a graph where node numbers are indexes
    // in pset[] and there is an edge between two
    // nodes only if they differ by single digit.
    Graph g = new Graph(pset.size());
    for (int i = 0; i < pset.size(); i++) {
      for (int j = i + 1; j < pset.size(); j++) {
        if (compare(pset.get(i), pset.get(j)))
          g.addedge(i, j);
      }
    }
 
    // Since graph nodes represent indexes of numbers
    // in pset[], we find indexes of num1 and num2.
    int in1 = 0, in2 = 0;
    for (int j = 0; j < pset.size(); j++) {
      if (pset.get(j) == num1)
        in1 = j;
    }
 
    for (int j = 0; j < pset.size(); j++) {
      if (pset.get(j) == num2)
        in2 = j;
    }
 
    return g.bfs(in1, in2);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int num1 = 1033, num2 = 8179;
    int ans = shortestPath(num1, num2);
    System.out.println(ans);
  }
}
 
// This code is contributed by cavi4762.

Python3

# Python3 program to reach a prime number
# from another by changing single digits 
# and using only prime numbers.
import queue
 
class Graph:
     
    def __init__(self, V):
        self.V = V;
        self.l = [[] for i in range(V)]
         
    def addedge(self, V1, V2):
        self.l[V1].append(V2);
        self.l[V2].append(V1);
 
    # in1 and in2 are two vertices of graph 
    # which are actually indexes in pset[]
    def bfs(self, in1, in2):
        visited = [0] * self.V
        que = queue.Queue()
        visited[in1] = 1
        que.put(in1)
        while (not que.empty()):
            p = que.queue[0]
            que.get()
            i = 0
            while i < len(self.l[p]):
                if (not visited[self.l[p][i]]):
                    visited[self.l[p][i]] = visited[p] + 1
                    que.put(self.l[p][i])
                if (self.l[p][i] == in2):
                    return visited[self.l[p][i]] - 1
                i += 1
     
    # Returns true if num1 and num2
    # differ by single digit.
     
# Finding all 4 digit prime numbers
def SieveOfEratosthenes(v):
     
    # Create a boolean array "prime[0..n]" and 
    # initialize all entries it as true. A value
    # in prime[i] will finally be false if i is
    # Not a prime, else true.
    n = 9999
    prime = [True] * (n + 1)
 
    p = 2
    while p * p <= n:
 
        # If prime[p] is not changed,
        # then it is a prime
        if (prime[p] == True):
 
            # Update all multiples of p
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
 
    # Forming a vector of prime numbers
    for p in range(1000, n + 1):
        if (prime[p]):
            v.append(p)
     
def compare(num1, num2):
     
    # To compare the digits
    s1 = str(num1)
    s2 = str(num2)
    c = 0
    if (s1[0] != s2[0]):
        c += 1
    if (s1[1] != s2[1]):
        c += 1
    if (s1[2] != s2[2]):
        c += 1
    if (s1[3] != s2[3]):
        c += 1
 
    # If the numbers differ only by a single
    # digit return true else false
    return (c == 1)
     
def shortestPath(num1, num2):
     
    # Generate all 4 digit
    pset = []
    SieveOfEratosthenes(pset)
 
    # Create a graph where node numbers
    # are indexes in pset[] and there is
    # an edge between two nodes only if
    # they differ by single digit.
    g = Graph(len(pset))
    for i in range(len(pset)):
        for j in range(i + 1, len(pset)):
            if (compare(pset[i], pset[j])):
                g.addedge(i, j)    
 
    # Since graph nodes represent indexes
    # of numbers in pset[], we find indexes
    # of num1 and num2.
    in1, in2 = None, None
    for j in range(len(pset)):
        if (pset[j] == num1):
            in1 = j
    for j in range(len(pset)):
        if (pset[j] == num2):
            in2 = j
 
    return g.bfs(in1, in2)
 
# Driver code
if __name__ == '__main__':
 
    num1 = 1033
    num2 = 8179
    print(shortestPath(num1, num2))
 
# This code is contributed by PranchalK

C#

// C# program to reach a prime number from
// another by changing single digits and
// using only prime numbers.
using System;
using System.Collections.Generic;
 
class Graph {
    private int V;
    private List<int>[] l;
 
    // Constructor
    Graph(int v)
    {
        V = v;
        l = new List<int>[ v ];
        for (int i = 0; i < v; i++)
            l[i] = new List<int>();
    }
 
    // Function to Add an edge into the graph
    void Addedge(int V1, int V2)
    {
        l[V1].Add(V2);
        l[V2].Add(V1);
    }
 
    // Finding all 4 digit prime numbers
    static void SieveOfEratosthenes(List<int> v)
    {
        // Create a bool array "prime[0..n]" and
        // initialize all entries it as true. A value in
        // prime[i] will finally be false if i is Not a
        // prime, else true.
        int n = 9999;
        bool[] prime = new bool[n + 1];
        Array.Fill(prime, true);
 
        for (int p = 2; p * p <= n; p++) {
 
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == true) {
 
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
 
        // Forming a vector of prime numbers
        for (int p = 1000; p <= n; p++) {
            if (prime[p])
                v.Add(p);
        }
    }
 
    // in1 and in2 are two vertices of graph which are
    // actually indexes in pset[]
    int Bfs(int in1, int in2)
    {
        int[] visited = new int[V];
        Array.Fill(visited, 0);
        Queue<int> que = new Queue<int>();
        visited[in1] = 1;
        que.Enqueue(in1);
 
        while (que.Count > 0) {
            int p = que.Dequeue();
            foreach(int i in l[p])
            {
                if (visited[i] == 0) {
                    visited[i] = visited[p] + 1;
                    que.Enqueue(i);
                }
                if (i == in2) {
                    return visited[i] - 1;
                }
            }
        }
 
        return 0;
    }
 
    // Returns true if num1 and num2 differ
    // by single digit.
    static bool Compare(int num1, int num2)
    {
        // To compare the digits
        string s1 = num1.ToString();
        string s2 = num2.ToString();
        int c = 0;
        if (s1[0] != s2[0])
            c++;
        if (s1[1] != s2[1])
            c++;
        if (s1[2] != s2[2])
            c++;
        if (s1[3] != s2[3])
            c++;
 
        // If the numbers differ only by a single
        // digit return true else false
        return (c == 1);
    }
 
    static int ShortestPath(int num1, int num2)
    {
        // Generate all 4 digit
        List<int> pset = new List<int>();
        SieveOfEratosthenes(pset);
 
        // Create a graph where node numbers are indexes
        // in pset[] and there is an edge between two
        // nodes only if they differ by single digit.
        Graph g = new Graph(pset.Count);
        for (int i = 0; i < pset.Count; i++) {
            for (int j = i + 1; j < pset.Count; j++) {
                if (Compare(pset[i], pset[j]))
                    g.Addedge(i, j);
            }
        }
 
        // Since graph nodes represent indexes of numbers
        // in pset[], we find indexes of num1 and num2.
        int in1 = 0, in2 = 0;
        for (int j = 0; j < pset.Count; j++) {
            if (pset[j] == num1)
                in1 = j;
        }
 
        for (int j = 0; j < pset.Count; j++) {
            if (pset[j] == num2)
                in2 = j;
        }
 
        return g.Bfs(in1, in2);
    }
 
    // Driver code
    static void Main(string[] args)
    {
        int num1 = 1033, num2 = 8179;
        int ans = ShortestPath(num1, num2);
        Console.WriteLine(ans);
    }
}
 
// This code is contributed by cavi4762.

Producción : 

6

Publicación traducida automáticamente

Artículo escrito por Shubham091996 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *