Find all Non-Prime Paths in a triangle-CodePudding

I'm trying to find routes that do not contain prime numbers in a triangle of integers leading from top to bottom.

What is wrong with my code?

For example (int[][] input = {{1}, {8, 4}, {2, 6, 9}, {8, 5, 9, 3}}),

This triangle has three paths that meet these criteria:

1 - 8 - 6 - 9  
1 - 4 - 6 - 9  
1 - 4 - 9 - 9

How can I achieve this?

My code:

private static void findPaths(int x, int y, int input[][])
{
   if(x < input.length - 1)
   {
     if(!isPrime(input[x   1][y]) & !isPrime(input[x   1][y   1]))
     {
         System.out.println(input[x   1][y]);
         findPaths(x   1, y, input);
            
         System.out.println(input[x   1][y   1]);
         findPaths(x   1, y   1, input);
     }
     else if(!isPrime(input[x   1][y]))
     {
         System.out.println(input[x   1][y]);
         findPaths(x   1, y, input);
     }
     else if(!isPrime(input[x   1][y   1]))
     {
         System.out.println(input[x   1][y   1]);
         findPaths(x   1, y   1, input);
     }
   }
}

public static boolean isPrime(int num)
{
  if (num <= 1) {return false;}

  for (int i = 2; i * i <= num; i  )
  {
     if ((num % i) == 0) {return false;}
  }
  return true;
}

Results for findPaths(0, 0, input) (array input initialized as shown above):

CodePudding user response：

This problem can be solved by modeling the relationships between the numbers in the given array as a Graph.

Note that although the elements form a structure which resembles a Binary Tree. It's certainly not a tree because each node of the tree by definition should have only one parent-node, but here it's not the case (remainder: Tree - is a particularization of a Graph, which has no circles, intersections between brunches and disjointed components).

      1 <- root element
     / \   
    8   4 <- level
   / \ / \
  2   6   9
 / \ / \ / \
8   5   9   3

Although it's not a tree, for simplicity I would use terminology which is usually used to describe a tree, like root - which the top vertex (node) of this tree-like structure and level - which is a group of vertices (nodes) having the same depth (distance from the root to a vertex).

And like in a Binary Tree, each element can be represented as a vertex having left and right children.

To find all non-prime paths in a graph starting from the root, we need to traverse over the graph. Each path would be represented as a separate List, i.e. every non-prime child of a non-prime vertex should spawn a new path. And every encountered prime vertex would cause the path that leads to it to be discarded.

To traverse the implement the graph, I've implemented Depth first search algorithm using recursion (because it's relatively easier to digest).

We would have two base cases (conditions when recursion should terminate):

a prime number has been encountered, path gets invalidated;
we've reached the last level and current vertex has a non-prime value, current path should be added to the collection of paths.

And in case if current vertex has a non-prime value, and it doesn't belong to the last level (i.e. it has children), we need to fire the depth first search recursively for both left and right child-vertices. That would be the recursive case of the algorithm.

Note: to avoid shifting the focus from the main goal of finding non-prime paths in the Graph to checking whether a particular value is a prime number, I've used built-in method BigInteger.isProbablePrime() which expects an int argument certainty, denoting the probability of getting correct result according to the formula 1-1/2^certainty. You're free to replace this check with any other logic.

Implementation might look like this:

public class NonPrimeTriangle {
    private final Vertex root;
    
    private NonPrimeTriangle(Vertex root) {
        this.root = root;
    }
    
    public List<List<Integer>> getNonPrimePaths() {
        List<List<Integer>> paths = new ArrayList<>();
        dfs(paths, new ArrayList<>(), root);
        
        return paths;
    }
    
    private void dfs(List<List<Integer>> paths, List<Integer> path, Vertex root) {
        if (BigInteger.valueOf(root.getValue()).isProbablePrime(100)) return; // base case - a prime number has been encountered, hence this path is invalidated
        
        path.add(root.getValue());  // vertex is proved to be non-prime and should be added to the path
        
        if (root.hasNoChildren()) { // base case - a non-prime path has been encountered found
            paths.add(path);
            return;
        }
        // recursive case
        dfs(paths, new ArrayList<>(path), root.getLeft());
        dfs(paths, new ArrayList<>(path), root.getRight());
    }
    
    // Not a part of the Algorithm - convenience-method for parsing the given Array into a Graph
    public static NonPrimeTriangle parse(int[][] arr) {
        if (arr.length == 0 || arr[0].length == 0) throw new IllegalArgumentException();
        
        Vertex root = new Vertex(arr[0][0]);
        NonPrimeTriangle triangle = new NonPrimeTriangle(root);
        List<Vertex> prevLevel = List.of(root);
        
        for (int row = 1; row < arr.length; row  ) {
            List<Vertex> nextLevel = new ArrayList<>(prevLevel.size()   1); // next level of Vertices
            for (int col = 0; col < arr[row].length; col  ) {
                Vertex newVertex = new Vertex(arr[row][col]);
                // every vertex has two parents, except for the leftmost and the rightmost which have only one and the root which has none
                if (col != 0) prevLevel.get(col - 1).setRight(newVertex);
                if (col != prevLevel.size()) prevLevel.get(col).setLeft(newVertex);
                
                nextLevel.add(newVertex); // updating the next level of Vertices
            }
            prevLevel = nextLevel;
        }
        return triangle;
    }

    public static class Vertex {
        private final int value;
        private Vertex left;
        private Vertex right;
    
        public Vertex(int value) {
            this.value = value;
        }
    
        public boolean hasNoChildren() {
            return left == null && right == null;
        }
        
        // getters & setters
    }
}

main()

public static void main(String[] args) {
    int[][] input = {{1}, {8, 4}, {2, 6, 9}, {8, 5, 9, 3}};
    NonPrimeTriangle triangle = NonPrimeTriangle.parse(input);
    
    triangle.getNonPrimePaths().forEach(System.out::println);
}

Output:

[1, 8, 6, 9]
[1, 4, 6, 9]
[1, 4, 9, 9]

A link to Online Demo

CodePudding user response：

Alternative approach (don't miss comments in code):

private static void traverseNonPrimalAndPrintPaths(int row, int col, int[][] arr, String curPath){
    int curNum = arr[row][col];
    if (!isPrime(curNum)) {//we only want to handle non-prime values

        //lets add value we are in to current path
        if (row == 0){//first value shouldn't have "-" before it
            curPath = String.valueOf(curNum);
        } else {//later values need to also add "-" before them in path
            curPath = curPath   "-"   curNum;
        }

        //If there are rows below check left and right "node" below current node
        if (row < arr.length-1){//we are NOT in last row
            traverseNonPrimalAndPrintPaths(row 1, col, arr, curPath);//check left node
            traverseNonPrimalAndPrintPaths(row 1, col 1, arr, curPath);//check right node
        } else {//here we know there are no more rows.
            //So we all we need to do is print path we took to get here.
            System.out.println(curPath);
        }
    }
}

Demo:

int[][] input1 = {{1}, {8, 4}, {2, 6, 9}, {8, 5, 9, 3}};
traverseNonPrimalAndPrintPaths(0, 0, input1,"");

Output:

1-8-6-9
1-4-6-9
1-4-9-9