I thought it would be a fun problem: Prime Path
But...It is hard for me. My only idea is "To do something with knapsack problem".. and no other ideas. Could You track me for good way? It's not for any challenge or University homework. I just want to learn something.
_
Ok, but firstly, how to find this prime numbers? Do i need to find all 4digit prime numbers, add it to graph?
For now i have generating all prime numbers.
Could You give me sample code to declare graph build on neighbour list?
Seems like a straightforward graph path finding problem.
Take all 4 digit primes as the vertices. Connect two with an edge, if we can go from one to the other.
Now given two, you need to find the shortest path between them, in the graph we just formed. A simple BFS (breadth-first-search) should do for that.
For programming contests with time limits, you could even hardcode every possible prime pair path and get close to zero running time!
Build a graph where the nodes are all the 4 digit prime numbers, and there are arcs everywhere two numbers have three digits in common. From there, it's a basic graph traversal to find the lowest-cost path from one node to another.
I came across a similar question where I had to convert one 4 digit prime number 1033 to another 4 digit prime number 3739 in minimum number of steps. I was able to solve the problem, it might not be efficient but here is the working code for the same.
Below code has been written in Java
import java.util.*;
public class PrimeNumberProblem {
public static void main(String... args) {
System.out.println("Minimum number of steps required for converting 1033 to 3739 are = "
+ getMinSteps(1033, 3739));
}
public static int getMinSteps(int a, int b) {
if (a == b)
return 0;
List<Integer> primes = new ArrayList<>();
// get all the 4 digit prime numbers
primes = getPrimeNumbers();
// consists of graph with vertices as all the prime numbers
Graph graph = addNumbersToGraph(primes);
// adding edges to the graph vertices
Graph finalGraph = addWeightToGraph(graph);
// min number of steps required
int result = findShortestRoute(finalGraph.getVertex(a), finalGraph.getVertex(b));
return result;
}
private static int findShortestRoute(Vertex source, Vertex dest) {
if (source.getVertexValue() == dest.getVertexValue())
return 0;
// step 1 Initialize the queue. Also Map to store path
Queue<Vertex> visitedQueue = new LinkedList<>();
Map<Vertex, Vertex> currentPrevMap = new HashMap<Vertex, Vertex>();
// step 2 start from visiting S (starting node), and mark it visited, add to queue
Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
visited.put(source.getVertexValue(), true);
visitedQueue.add(source);
int level = 0;
// step 3 Repeat until queue is empty
while (!visitedQueue.isEmpty()) {
// step 4 remove from queue
Vertex current = visitedQueue.remove();
if (current.getVertexValue() == dest.getVertexValue()) {
printPath(source, dest, currentPrevMap);
return level;
} else if (current.getAdjacentVertices().size() > 0) {
level++;
}
// step 5 add each of the unvisited neighbour and mark visited
for (Vertex adjacentVertex : current.getAdjacentVertices()) {
Integer value = adjacentVertex.getVertexValue();
if (value == dest.getVertexValue()) {
currentPrevMap.put(adjacentVertex, current);
printPath(source, dest, currentPrevMap);
return level;
}
if (visited.get(value) == null) {
currentPrevMap.put(adjacentVertex, current);
// mark visited and enqueue it
visited.put(value, true);
visitedQueue.add(adjacentVertex);
}
}
}
// not found
System.out.println("Dest vertex not found");
return -1;
}
private static void printPath(Vertex source, Vertex dest, Map<Vertex, Vertex> currentPrevMap) {
Vertex node = dest;
System.out.println("Reverse Path from source: " + source.getVertexValue() + " to dest: "
+ dest.getVertexValue());
while (node != source) {
System.out.println(node.getVertexValue());
node = currentPrevMap.get(node);
}
System.out.println(source.getVertexValue());
}
private static Graph addWeightToGraph(Graph graph) {
List<Vertex> vertices = graph.getAllVertices();
for (Vertex i : vertices) {
for (Vertex j : vertices) {
if (i.equals(j))
continue;
if (distance(i, j) == 1) {
i.getAdjacentVertices().add(j);
// i.addEdge(new Edge(i, j, 1));
}
}
}
return graph;
}
private static int distance(Vertex source, Vertex dest) {
if (source.getVertexValue() == dest.getVertexValue()) {
return 0;
}
char[] numA = extractIntegers(source.getVertexValue());
char[] numB = extractIntegers(dest.getVertexValue());
int len1 = numA.length;
int tracker = 0;
for (int i = 0; i < len1; i++) {
if (numA[i] != numB[i]) {
numA[i] = numB[i];
tracker++;
String sA = String.copyValueOf(numA);
String sB = String.copyValueOf(numB);
// if we have reached destination
if (Integer.parseInt(sA) == Integer.parseInt(sB)) {
return tracker;
}
}
}
return tracker;
}
private static char[] extractIntegers(int i) {
char[] arr = Integer.toString(i).toCharArray();
return arr;
}
private static Graph addNumbersToGraph(List<Integer> primes) {
Graph g = new Graph();
for (Integer prime : primes) {
g.addVertex(new Vertex(prime));
}
return g;
}
private static List<Integer> getPrimeNumbers() {
List<Integer> fourDigitPrimes = new ArrayList<>();
fourDigitPrimes.add(1033);
fourDigitPrimes.add(1733);
fourDigitPrimes.add(3733);
fourDigitPrimes.add(3739);
// for (int i = 1000; i < 9999; i++) {
// if (isPrime(i))
// fourDigitPrimes.add(i);
// }
return fourDigitPrimes;
}
private static boolean isPrime(int i) {
for (int k = 2; k < Math.sqrt(i); k++) {
if (i % k == 0)
return false;
}
return true;
}
}
class Graph {
public List<Vertex> vertexList = new ArrayList<Vertex>();
public void addVertex(Vertex V) {
vertexList.add(V);
}
public List getAllAdjacentNodes(Vertex V) {
return V.getAdjacentVertices();
}
public List getAllVertices() {
return vertexList;
}
public Vertex getVertex(int val) {
Iterator<Vertex> keys = vertexList.iterator();
while (keys.hasNext()) {
Vertex v = keys.next();
if (v.getVertexValue() == val)
return v;
}
return null;
}
}
class Vertex {
int value;
private List<Vertex> adjacentVertices = new ArrayList<Vertex>();
public Vertex(int v) {
this.value = v;
}
public List<Vertex> getAdjacentVertices() {
return adjacentVertices;
}
public int getVertexValue() {
return value;
}
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (o == null || getClass() != o.getClass())
return false;
Vertex vertex = (Vertex) o;
return value == vertex.value;
}
@Override
public int hashCode() {
return value;
}
}
Look into "breadth-first search". Also worth bearing in mind here that the problem can be approached "from both ends" simultaneously (a chain from numbers X to Y can be reversed to get Y to X, and you can exploit this). Precalculating primes will avoid much computation along the way.
I'd run a BFS using probable prime testing, which would work relatively well with only 4 digit numbers. With only 4 digits, also, you may want to use more exacting methods to produce all primes to compare against for faster prime checking.
Here is my solution using BFS and I have already saved all 4 digit prime numbers into an array as there is no need to write a function to calculate the prime numbers. I hope it helps
#include<stdio.h>
int hash[10000];
int a,b,ans,level,new_num,count;
int prime[] = {1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993,8009,8011,8017,8039,8053,8059,8069,8081,8087,8089,8093,8101,8111,8117,8123,8147,8161,8167,8171,8179,8191,8209,8219,8221,8231,8233,8237,8243,8263,8269,8273,8287,8291,8293,8297,8311,8317,8329,8353,8363,8369,8377,8387,8389,8419,8423,8429,8431,8443,8447,8461,8467,8501,8513,8521,8527,8537,8539,8543,8563,8573,8581,8597,8599,8609,8623,8627,8629,8641,8647,8663,8669,8677,8681,8689,8693,8699,8707,8713,8719,8731,8737,8741,8747,8753,8761,8779,8783,8803,8807,8819,8821,8831,8837,8839,8849,8861,8863,8867,8887,8893,8923,8929,8933,8941,8951,8963,8969,8971,8999,9001,9007,9011,9013,9029,9041,9043,9049,9059,9067,9091,9103,9109,9127,9133,9137,9151,9157,9161,9173,9181,9187,9199,9203,9209,9221,9227,9239,9241,9257,9277,9281,9283,9293,9311,9319,9323,9337,9341,9343,9349,9371,9377,9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973};
int size = sizeof(prime)/sizeof(prime[0]);
int bfs(int,int);
typedef struct q{
int x, c;
} queue;
queue qq[10000];
int isprime(int x)
{
int l,r,m;
l=m=0; r=size-1;
while (l <= r)
{
int m = l + (r-l)/2;
if (prime[m] == x)
return 1;
if (prime[m] < x)
l = m + 1;
else
r = m - 1;
}
return 0;
}
int bfs(int num1,int num2)
{
int i,j,k,p,q,n;
new_num=p=q=0;
i=0;
j=1;
qq[i].x = num1;
qq[i].c = 0;
hash[num1] = 1;
while(i!=j)
{ n = qq[i].x;
level = qq[i].c;
if(n==num2)
{
count = level;
return count;
}
level++;
p = n%1000;
for(k=1;k<10;k++)
{ new_num = (k*1000)+ p;
if(isprime(new_num)&&(new_num!=n)&&(!hash[new_num]))
{
hash[new_num] = 1;
qq[j].x = new_num;
qq[j].c = level;
j++;
}}
p=q=new_num=0;
p = n/1000;
q = n%100;
for(k=0;k<10;k++)
{ new_num = (p*1000)+k*100+q;
if(isprime(new_num)&&(new_num!=n)&&(!hash[new_num]))
{
hash[new_num] = 1;
qq[j].x = new_num;
qq[j].c = level;
j++;
}}
p=q=new_num=0;
p = n/100;
q = n%10;
for(k=0;k<10;k++)
{ new_num = (p*100)+k*10+q;
if(isprime(new_num)&&(new_num!=n)&&(!hash[new_num]))
{
hash[new_num] = 1;
qq[j].x = new_num;
qq[j].c = level;
j++;
}}
p=q=new_num=0;
p = n/10;
for(k=0;k<10;k++)
{ new_num = (p*10)+k;
if(isprime(new_num)&&(new_num!=n)&&(!hash[new_num]))
{
hash[new_num] = 1;
qq[j].x = new_num;
qq[j].c = level;
j++;
}}
p=q=new_num=0;
i++;
}
return -1;}
int main()
{
int v,tc;
setbuf(stdout,NULL);
scanf("%d",&tc);
for(v=1;v<=tc;v++)
{ int i,j;
a=b=ans=level=new_num=count=0;
for(i=0;i<10000;i++)
{qq[i].x=0;
qq[i].c=0;
hash[i]=0;}
scanf("%d%d",&a,&b);
if(a==b)
{ ans = 0;}
else
{ ans = bfs(a,b);}
printf("Case #%d\n", v);
if(ans==-1)
{
printf("Impossible\n");
}
else
{printf("%d\n",ans);}
}
return 0;
}
Could You give me sample code to declare graph build on neighbour list?
here is a sample code for breadth first search
public static final int MAX = 10000;
boolean[] prime = new boolean[MAX];
int[] dist = new int[MAX];
//get digit i [1 to 4] in num
public int getDigit(int num,int i){
return num % ((int)Math.pow(10, i)) / ((int) Math.pow(10, i-1));
}
//set digit i to d
public int setDigit(int num,int i,int d){
return (num - getDigit(num, i)*(int)Math.pow(10, i-1)) + d * (int)Math.pow(10,i-1);
}
public int bfs(int start,int end){
Queue<Integer> q = new LinkedList<Integer>();
q.add(start);
HashSet<Integer> visited = new HashSet<Integer>();
visited.add(start);
dist[start] = 0;
int x,y,d = 0;
while (q.size() > 0){
x = q.poll();
d = dist[x];
if (x == end) return d;
for (int i = 1; i < 5; i++) {
//digit number i
for (int j = 0; j < 10; j++) {
//avoid setting last digit
if (j == 0 && i == 4) continue;
//set digit number i to j
y = setDigit(x, i, j);
if (prime[y] && y != x && !visited.contains(y)){
q.add(y);
visited.add(y);
dist[y] = d + 1;
}
}
}
}
return -1;
}
My Python solution using BFS:
import queue
# Class to represent a graph
class Graph:
def __init__(self, V):
self.V = V # No. of vertices
self.prime_list = [[] for i in range(V)]
# function to add an edge to graph
def addedge(self, V1, V2):
self.prime_list[V1].append(V2)
self.prime_list[V2].append(V1)
def bfs(self, in1, in2):
visited = [0] * self.V
que = queue.Queue()
visited[in1] = 1
que.put(in1)
while not que.empty():
prime_index = que.get()
i = 0
while i < len(self.prime_list[prime_index]):
if not visited[self.prime_list[prime_index][i]]:
visited[self.prime_list[prime_index][i]] = visited[prime_index] + 1
que.put(self.prime_list[prime_index][i])
if self.prime_list[prime_index][i] == in2:
return visited[self.prime_list[prime_index][i]] - 1
i += 1
# // 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 be
# finally be false if i is Not a prime, else true.
n = 9999
prime = [True] * (n + 1)
p = 2
while p * p <= 9999:
if prime[p]:
i = p * p
while i <= 9999:
prime[i] = False
i = i + p
p = p + 1
# v = []
for i in range(1000, n + 1):
if prime[i]:
v.append(i)
return v
def compare(a, b):
diff = 0
while a:
if a % 10 != b % 10:
diff += 1
a //= 10
b //= 10
# If the numbers differ only by a single # digit return true else false
if diff > 1:
return False
return True
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))
