CODEWITHSUNDEEP
javaalgorithmpath-finding
bob
bob

Reputation: 29

Find All Possible Paths Algorithm

Hello there StackOverFlow! I am posting here today because I have a problem here in Java where I am trying to compute the all the possible combinations of pogo sticks that my character may use to move. The character uses pogo sticks which all have a distance, given by user input.

Likewise, the total distance is also given via user input and all possible paths are to be found. I have shown my function below with the output and the desired output that I can't seem to get quite right.

I have been stuck on this problem for a while and I am really hoping somebody can help me out here!

/*
 * First integer in input
 */
int totalDistance;

/*
 * The remaining integers in the input
 */
ArrayList<Integer> pogoSticks = new ArrayList<Integer>();

private void findPaths() {
        ArrayList<ArrayList<Integer>> possibleSticks = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i < pogoSticks.size(); i++) {

            int pogoStickDistance = pogoSticks.get(i);

            if (pogoStickDistance == totalDistance) {
                if (!possibleSticks.contains(new ArrayList<Integer>(pogoStickDistance))) {
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    list.add(pogoStickDistance);
                    possibleSticks.add(list);
                }
            } else if (pogoStickDistance < totalDistance) {
                int remainingDistance = totalDistance;
                ArrayList<Integer> possibleSubSticks = new ArrayList<Integer>();

                possibleSubSticks.add(pogoStickDistance);
                remainingDistance -= pogoStickDistance;

                for (int j = 0; j < pogoSticks.size(); j++) {

                    int pogoStickDistance1 = pogoSticks.get(j);
                    if (pogoStickDistance1 == remainingDistance) {
                        possibleSubSticks.add(pogoStickDistance1);

                        possibleSticks.add(possibleSubSticks);
                        break;
                    } else if (pogoStickDistance1 < remainingDistance) {
                        possibleSubSticks.add(pogoStickDistance1);
                        remainingDistance -= pogoStickDistance1;
                    }

                    if (j == (pogoSticks.size() - 1) && pogoStickDistance1 != remainingDistance) {
                        j = 0;
                    }
                }
            }

        }

        System.out.println(possibleSticks);
    }

Here is the output that I get from running the function above:

Enter input: 5 10 4 1 2
[[4,1], [1,4], [2,1,2]]

Note that 5 is the distance, and 10, 4, 1, and 2 are the distances that a pogo stick may travel.

The issue is that these are not all the possible paths! For example, it is missing the paths such as [1, 1, 1, 1, 1] or [2, 2, 1].

Can anybody please help me modify my function to include these? I believe it is happening because once my loop finds the first occurrence of a pogo stick distance that's less than the remaining distance it will immediately use that path and ignore other possibilities.

Upvotes: 1

Views: 165

Answers (1)

Om Chabra
Om Chabra

Reputation: 35

                for(int i = 0;i < pogoSticks.size();i++){
                   //part to calculate small enough 
        int[] temps = new int[pogoSticks.size];
        int temp1 = 0; 
                   for(int j; j< pogoStricks.size();i++){
                   if(pogoSticks.getIndex(j) + k <= totalDisatnce){
        temps[temp1] = pogoSticks.getIndex(j);
        }
    //code to calculate number of paths to get to TotalDistance

This should do half the job, now you just need a method to calculate the distance from all the temps variables. I suggest you subtract each value from the TotalDistance and see which numbers added up would equal that.

Upvotes: 1

Related Questions