Friday, 10 January 2014

Coding Contest - Arranging 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

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<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

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?