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"

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


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?
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
  • 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());
               }            

               /**
                * 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 traverseVertexes(List 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 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
  • First Argument: If 'true' sequences are written in log file, if 'false' print to the console
  • Second Argument : The number for which the sequence to be generated
  • Third Argument: 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


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?

Posted by
Labels: Hamiltonian path Travelling salesman problem
0

Add a comment

You might be seeking for the option to profile (capturing method's execution time) your spring application. Spring provides different ways to profile the application. Profiling should be treated as a separate concern and spring AOP facilitates easy approach to separate this concern. With the help of spring AOP you can profile your methods without making any changes in actual classes. 

You just need to perform pretty simple steps to configure your application for profiling using spring AOP:

In application context file, add below tag to enable the load time weaving          context:load-time-weaver      

With this configuration, AspectJ's Load-time weaver is registered with current class loader.

Why Locking is required?

When two concurrent users try to update database row simultaneously, there are absolute chances of losing data integrity. Locking comes in picture to avoid simultaneous updates and ensure data integrity.

Types of Locking

There are two types of locking, Optimistic and Pessimistic. In this post optimistic locking is described with example.

Optimistic Locking: This locking is applied on transaction commit.

Liferay is one of the portal frameworks based on java. You can create portlets in Liferay using Spring MVC framework. The main purpose of this post is to provide the complete solution for free text search integration with Liferay Spring MVC portlets.

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.

Jenkins is an open source tool which provides continuous integration services for software development. If you want to get more detail about Jenkins and it's history I would suggest refer this link. This post will help you installing and configuring Jenkins and creating jobs to trigger maven builds. Setting up Jenkins is not a rocket science indeed. In this post, I would like to concise the installation and configuration steps.

Peer code review is an important activity to find and fix mistakes which are overlooked during development. It helps improving both software quality as well as developers skills. Though, it’s a good process for quality improvement. But this process becomes tedious if you need to share files and send review comments through mails, you need to organize formal meetings and you need to communicate peers who are in different time zone.

If you are using Hudson as continuous integration server and you might feel lazy about accessing Hudson explicitly to check the build status or checking Hudson build status mails, there is an option to monitor Hudson build and perform build activities in Eclipse IDE itself. This post describes about installing, configuring and using the Hudson in Eclipse IDE.

As a developer or architect, you always need to draw some sequence diagrams to demonstrate or document your functionality. And of course, if you do this manually you have to spare much time for this activity. Just think about, what If sequence diagram is generated automatically and you get it free of cost. Your reaction would be ‘wow’ this is great. But the next question will be ‘how’.

If you are using JPA 2.0 with Hibernate and you want to do audit logging from middle-ware itself, I believe you landed up on the exact place where you should be. You can try audit logging in your local environment by following this post.

Required JPA/Hibernate Maven Dependencies

JPA Configuration in Spring Application Context File

For JPA/Hibernate, you need to configure entity manager, transaction, data source and JPA vendor in your ‘applicationContext.xml’ file.

If any issue is observed in production, there are two major aspects related to providing the solution. First ‘how quick you can analyze the root cause’ and second ‘how quick you can fix the issue’. Story starts from analyzing the root cause. Unless, you find the root cause, you can’t even think about providing solution for that. Can you?

Now let’s think about actual production environment. There may be multiple JVMs where application is deployed.
Loading