I have got a problem in coding contest. In this post, I would like to share the approach to solve this problem. I would definitely not say that I have invented something new and I am not trying to reinvent the wheel again. I just described the end to end approach that I followed to solve this problem.It was really a great brain storming activity.
Problem Statement
"Arrange numbers from 1 to 71 in a sequence such that sum of any 2 adjacent numbers in the sequence adds up to a prime number.”For e.g : 7,6,5,2,1,4,3 is a valid one sequence for arranging 1..7"
Problem Statement
"Arrange numbers from 1 to 71 in a sequence such that sum of any 2 adjacent numbers in the sequence adds up to a prime number.”For e.g : 7,6,5,2,1,4,3 is a valid one sequence for arranging 1..7"
Theory: How to Solve?
Let's take an example, we want to find all series from 1 to 5 such that sum of any 2 adjacent numbers in the sequence adds up to a prime number. For this problem, there should be below no. of possible combinations.
1, 4, 3, 2, 5
3, 4, 1, 2, 5
5, 2, 1, 4, 3
5, 2, 3, 4, 1
Now, lets talk about the approach to get above combinations.
Firstly, for each number, check all possible numbers in series such that sum should be a prime number. Let's take number 1 and check which sum is prime number out of 1+2 = 3, 1+3=4, 1+4=5, 1+5=6. So, we have got 1+2 = 3 and 1+4=5 that means 2 and 4 are the numbers that can be connected to number 1. Now apply the same logic for all remaining numbers 2,3,4,5. You will get below combinations.
1 --> 2, 4
2 --> 1, 3, 5
3 --> 2, 4
4 --> 1, 3
5 --> 2
Secondly, create a graph that connects any two numbers that has a prime number sum. If you take number 1 that is connected to 2 and 4, the graph must represent link between connected numbers. In graph's terminology you can say each number is a vertex and each connected link is an edge.
Till now you are half done. You have graph that connects any two numbers that has a prime number sum.
Thirdly, you just need to find out the unique cycles in graph where you visit each vertex exactly once. This is kind of calculating Hamiltonian Paths (also refer this).
Below graph shows two cycles:
1, 4, 3, 2, 5
5, 2, 3, 4, 1
Thirdly, you just need to find out the unique cycles in graph where you visit each vertex exactly once. This is kind of calculating Hamiltonian Paths (also refer this).
Below graph shows two cycles:
1, 4, 3, 2, 5
5, 2, 3, 4, 1
Below graph shows two cycles:
3, 4, 1, 2, 5
5, 2, 1, 4, 3
Theoretically you have achieved what you wanted to achieve. You have all 4 possible combinations for given problem from 1 to 5.
Now let's convert above theory into computer programming and ask computer to get combinations for any given number. Well, I am a Java Techie and I would prefer to convert this theory into java programming. If you are a Java Techie you have prepared solution in your hand. In case you are not, you have to struggle converting my program into your required language.
Programmatic Approach: How to Solve?
Now let's convert above theory into computer programming and ask computer to get combinations for any given number. Well, I am a Java Techie and I would prefer to convert this theory into java programming. If you are a Java Techie you have prepared solution in your hand. In case you are not, you have to struggle converting my program into your required language.
Programmatic Approach: How to Solve?
Before jumping into the programming, you have to think first how you can represent this graph in java. This is bit complex. But once you get into this; it will be easy to understand and apply.
I took help from here to represent the graph in two dimensional array. To get combinations from 1 to 5, graph can be represented in 2D array like below:
Action Points for Programming
Solution in Java
Program
How to Execute Program?
You can use below command to execute above program.
java PrimeSequenceSolution <logging_Flag> <last_number> <max_sequences>
Example:
java PrimeSequenceSolution true 5
java PrimeSequenceSolution false 7
java PrimeSequenceSolution false 15 100000
Execution Statistics
Below are the captured execution statistics for above program.
Conclusion
Above approach is one of the solutions for given problem. I am sure there can be other approaches to solve this problem. If you notice the execution statistics, execution time is drastically increased if last number is increased. What about if program gets executed to get combinations for last number say 70, 80, 100 etc. This program will definitely take much time to get combinations or it may prompt out of memory error. Generating the expected result can be one of the aspect to solve a problem but efficiency is most important aspect that must not be ignored. Though, this solution gives the expected result but it may not be considered as efficient as it should be. This execution statistics left me thinking about what can be the other approaches? How can I make this program efficient? Can I think about parallel processing? etc.Well, I still need to get answers of my own questions. If you know the better solution; your comments are greatly appreciated.
Additionally, I tried to find out the real world problems related to this mathematical problem. TSP
is one of the most famous problems. This is just to get into the real world problems. isn't it?
I took help from here to represent the graph in two dimensional array. To get combinations from 1 to 5, graph can be represented in 2D array like below:
- Populate 2D array that connects any two numbers that has a prime number sum.
- Implement recursive function to find out the path that visits each connected number exactly once
- Print the path if path length equals to the provided last number
Solution in Java
Program
import
java.io.File;
import
java.util.ArrayList;
import
java.util.Date;
import java.util.List;
import
org.apache.log4j.Appender;
import
org.apache.log4j.DailyRollingFileAppender;
import
org.apache.log4j.FileAppender;
import
org.apache.log4j.Level;
import
org.apache.log4j.Logger;
import
org.apache.log4j.PatternLayout;
/**
* Coding Contest
*
* Arrange numbers from 1 to n in a sequence
such that sum of any 2 adjacent
* numbers in the sequence adds up to a prime
number. For e.g : 7,6,5,2,1,4,3 is
* a valid one sequence for arranging 1..7
*
*
* @author NarendraVerma
*/
public class
PrimeSequenceSolution {
/** The pattern layout. */
private static PatternLayout
patternLayout = new PatternLayout("%d{ISO8601}\t%m%n");
/** Logger instance. */
private static final Logger
LOGGER = Logger
.getLogger(PrimeSequenceSolution.class);
/** Matrix that holds all prime
numbers . */
public static int[][]
inputArray = null;
/** Matrix[1][n] hat connects
any two numbers that has a prime number sum. */
public static int
inputArrayLength;
/** The total sequences count.
*/
public static int totalCount =
0;
/** Maximum Sequences to be
generated. */
public static long maxSeq =
1000000000;
/** The start time. */
public static long startTime;
/** The logging flag. */
public static boolean
loggingFlag = true;
/**
* Find prime sequences.
*/
public static void
findPrimeSequences() {
traverseVertexes(new
ArrayList<Integer>());
}
/**
* Populate 2D array that connects any two
numbers that has a prime number sum
*
* For example: If last No is 5, matrix is populated
like below
*
*
1 --> 2, 4
*
2 --> 1, 3, 5
*
3 --> 2, 4
*
4 --> 1, 3
*
5 --> 2
*
* 2D Array:
*
*
1 2 3
4 5
* 1
[0 1
0 1 0]
* 2
[1 0
1 0 1]
* 3
[0 1
0 1 0]
* 4
[1 0
1 0 0]
* 5
[0 1
0 0 0]
*
* @param lastNo the last no
*/
public static void
prepareInputMatrix(int lastNo) {
inputArray = new
int[lastNo][lastNo];
for (int i = 1;
i <= lastNo; i++) {
for
(int j = 1; j <= lastNo; j++) {
if
(i == j) {
inputArray[i
- 1][j - 1] = 0;
}
else {
inputArray[i
- 1][j - 1] = isPrime(i + j);
}
}
}
}
/**
* Checks if given number is prime number
*
* @param number
*
the number
* @return the int
*/
public static int isPrime(int
number) {
// check if
number is a multiple of 2
if (number % 2
== 0)
return
0;
// if not, then
check the odd numbers
for (int i = 3;
i * i <= number; i += 2) {
if
(number % i == 0)
return
0;
}
return 1;
}
/**
* The recursive function to find out the
path that visits each connected number exactly once
*
* @param traversedPath
*
the path so far
* @return the list
*/
public static
List<Integer> traverseVertexes(List<Integer> traversedPath) {
inputArrayLength
= inputArray.length;
if
(traversedPath.size() == inputArrayLength) {
printSequences(traversedPath);
return
traversedPath;
} else if
(traversedPath.size() == 0) {
for
(int i = 0; i < inputArrayLength; i++) {
traversedPath.add(i);
traverseVertexes(traversedPath);
traversedPath.remove(traversedPath.size()
- 1);
}
} else {
int
currentNode = traversedPath.get(traversedPath.size() - 1);
for
(int i = 0; i < inputArrayLength; i++) {
if
(!traversedPath.contains(i) && inputArray[currentNode][i] != 0) {
System.out.println("I
am here:" + traversedPath );
traversedPath.add(i);
traverseVertexes(traversedPath);
traversedPath.remove(traversedPath.size()
- 1);
}
}
}
return
traversedPath;
}
/**
* Prints the solution.
*
* @param pathSoFar
*
the path so far
*/
public static void
printSequences(List<Integer> pathSoFar) {
StringBuffer sb
= new StringBuffer(" -- ");
sb.append("
[ SeqNo."+ (totalCount + 1 )+"] -- ");
for (Integer
number : pathSoFar) {
sb.append(number
+ 1).append(", ");
}
if (loggingFlag)
LOGGER.info(sb.toString());
else
System.out.println(new
Date() + " " + sb.toString());
if (maxSeq !=
1000000000 && totalCount > maxSeq - 2) {
LOGGER.info("Maximum
sequences [ " + maxSeq
+
" ] have been generated. Total-Elapsed-Time [ "
+
(System.currentTimeMillis() - startTime) + " msec ] ");
System.out.println("Maximum
sequences [ "
+
maxSeq
+
" ] have been generated.
Total-Elapsed-Time [ "
+
(System.currentTimeMillis() - startTime) + " msec ]");
System.exit(1);
}
++totalCount;
}
/**
* Creates the log file.
*
* @param lastNo the last no
* @return the file
*/
public static File
createLogFile(int lastNo){
String fileName
= "271962_primeseq_"+ lastNo + ".log";
File logFile =
new File(fileName);
//Remove
existing log file if exists
if(logFile.exists()){
logFile.delete();
}
FileAppender fa
= new FileAppender();
fa.setName("FileOut");
fa.setFile(fileName);
fa.setLayout(patternLayout);
fa.setThreshold(Level.DEBUG);
fa.setAppend(true);
fa.activateOptions();
LOGGER.setAdditivity(false);
LOGGER.addAppender(fa);
return new
File(fileName);
}
/**
* The main method.
*
* @param args the arguments
* @throws Exception the exception
*/
public static void
main(String[] args) throws Exception{
int lastNo = 0;
try{
//
Fetch second argument - The number for which the sequence to be generated
lastNo
= Integer.parseInt(args[1]);
//
Create log file
File
logFile = createLogFile(lastNo);
startTime
= System.currentTimeMillis();
//
Fetch first argument - This is log level flag. If 'true' write to log
//
file, if false print to the console
String
logFlag = args[0];
if
("true".equals(logFlag)){
System.out.println("\nPrime
sequences are logged into file
["+logFile.getAbsolutePath()+"]");
loggingFlag
= true;
}
else
loggingFlag
= false;
//
Fetch third argument - Maximum Sequences to be generated
if(args.length
== 3){
maxSeq
= Integer.parseInt(args[2]);
}
}
catch(Exception
e ){
String
errorMessage = "\nPlease provide the valid arguments \n"
System.out.println(errorMessage);
System.exit(1);
}
// Populate 2D array
prepareInputMatrix(lastNo);
// Find the
sequences
findPrimeSequences();
long end =
System.currentTimeMillis();
long
totalTimeSpend = end - startTime;
if(!loggingFlag){
LOGGER.info("Since
logging flag (first argument of the program) is false, sequences are printed
to the console");
}
LOGGER.info("Total-Elapsed-Time
[ " + totalTimeSpend
+
" msec ] and No. of total sequences found [ "
+
totalCount + " ]");
System.out.println("\nCongratulations
!! Sequences generated successfully.");
System.out.println("\nTotal
sequences generated [ "+ totalCount + " ], Elapsed Time [ " +
totalTimeSpend + " msec ]");
}
}
|
How to Execute Program?
You can use below command to execute above program.
java PrimeSequenceSolution <logging_Flag> <last_number> <max_sequences>
- <logging_Flag> : If 'true' sequences are written in log file, if 'false' print to the console
- <last_number> : The number for which the sequence to be generated
- <max_sequences> : Maximum sequences to be generated. This is optional. Default value is 1000000000
Example:
java PrimeSequenceSolution true 5
java PrimeSequenceSolution false 7
java PrimeSequenceSolution false 15 100000
Below are the captured execution statistics for above program.
Conclusion
Above approach is one of the solutions for given problem. I am sure there can be other approaches to solve this problem. If you notice the execution statistics, execution time is drastically increased if last number is increased. What about if program gets executed to get combinations for last number say 70, 80, 100 etc. This program will definitely take much time to get combinations or it may prompt out of memory error. Generating the expected result can be one of the aspect to solve a problem but efficiency is most important aspect that must not be ignored. Though, this solution gives the expected result but it may not be considered as efficient as it should be. This execution statistics left me thinking about what can be the other approaches? How can I make this program efficient? Can I think about parallel processing? etc.Well, I still need to get answers of my own questions. If you know the better solution; your comments are greatly appreciated.
Additionally, I tried to find out the real world problems related to this mathematical problem. TSP
is one of the most famous problems. This is just to get into the real world problems. isn't it?
No comments:
Post a Comment