(Recursion) print the cheapest path through 2D array

[jaunty lance]

Hello, I am working on a recursion exercise. Sample output below. I have to find the cheapest path from bottom left to top right of a 2D grid. I can only traverse up and right (north and east).

However, my program is printing out ALL the possible routes, and NOT the cheapest. (There are more paths but it wouldn't fit the screenshot. It also doesn't recursively call itself forever.)

Does anyone have any insight? Attached below in the link is my recursive method. I am thinking something is wrong with the if statement inside my base case but I don't know what... why is it doing this, and how do I go about fixing it?

https://codeshare.io/pqMb1D

[tulip tundra]

The broad idea of your issue is that you're printing the result for each path when it should only be printed when you went through all possible paths.

You could try something like this

if (row - 1 >= 0) {
  path[index] = grid[row][column];
  directions[index] = "NORTH";
  mps(grid, row - 1, column, directions, sum + grid[row][column], cheapestSum, path, index + 1, cheapestPath, cheapestDirections);
} else if (column + 1 <= grid[0].length - 1) {    
  path[index] = grid[row][column];
  directions[index] = "EAST";
  mps(grid, row, column + 1, directions, sum + grid[row][column], cheapestSum, path, index + 1, cheapestPath, cheapestDirections);
} else {
  System.out.println(Arrays.toString(cheapestPath));
  System.out.println(Arrays.toString(cheapestDirections));
  System.out.println("Cheapest Cost: $" + cheapestSum);
}

[jaunty lance]

Wow, that makes alot of sense — it's only printing one path now.

however, it's not the cheapest path, and I think it's due to the this if condition:

if (sum <= cheapestSum) {
                cheapestSum = sum; 
            
                for (int i = 0; i < path.length; i++) {
                    cheapestPath[i] = path[i]; 
                }
                for (int i = 0; i < directions.length; i++) {
                    cheapestDirections[i] = directions[i];
                }
            }

[tulip tundra]

Can you send me your whole code

Or the main function

[jaunty lance]

okay! one second.

[tulip tundra]

Btw, you can send code like I did by doing this
```java
your code here
```

[jaunty lance]

Ahh, gotha. I was moving it to a codeshare link

discord says the message is too long :(

[tulip tundra]

Just send the main

[jaunty lance]

public static void main(String[] args) throws IOException {
        System.out.println("Finding the Cheapest Routes:\n");
        Scanner in = new Scanner (new File ("src/assignment2/grid.txt"));

        int numOfGrids = Integer.parseInt(in.nextLine());

        // miscellaneous and variable declarations
        int gridNumber = 1; 
        int numOfRows = 0;
        int numOfColumns = 0; 

        int row = 0; int column = 0;
        int sum = 0;

        while (numOfGrids != 0) {
            numOfRows = Integer.parseInt(in.nextLine());
            numOfColumns = Integer.parseInt(in.nextLine());

            int[][] grid = new int [numOfRows][numOfColumns];

            row = grid.length-1;
            column = 0;

            // reads in grid from text file into 2D array
            int i = 0;
            while (numOfRows != 0) {
                String rowGrid = in.nextLine();
                String[] tokens = rowGrid.split(" ");
                for (int j = 0; j < grid[0].length; j++) {
                    grid[i][j] = Integer.parseInt(tokens[j]);
                }
                i++;
                numOfRows--;
            }

            System.out.println("Grid #" + gridNumber); 
            printGrid(grid);

            int[] path = new int [grid.length + grid[0].length-1];
            String[] directions = new String [grid.length + grid[0].length-2];
            int index = 0; 
            int [] cheapestPath = new int [path.length];
            String [] cheapestDirections = new String [path.length-1];
            int minSum = Integer.MAX_VALUE; 

            mps(grid, row, column, directions, sum, minSum, path, index, cheapestPath, cheapestDirections);

        
            numOfGrids--;
            gridNumber++; 

            System.out.println();
        }
    }

this is what the text file looks like

[tulip tundra]

Mmh it's a more complex main that I thought it would. I'm kinda a lazy to adapt then XD.

I'll tell you what I think without testing it.

I think you simply need to remove row == 0 in your if (row == 0 && column == grid[0].length - 1)

[jaunty lance]

hmm could you give like two words on why?

[jaunty lance]

yeah, it's not changing anything. the array that stores the cheapest path/directions isn’t updating with each new path somehow.

[tulip tundra]

My bad I made a mistake and sorry I had an important unexpected meeting

I'll check it out more later but it seems like it always changes the cheapestSum. Maybe because it resetting it to the Integer.MAX which makes the condition sum <= cheapestSum always true

[jaunty lance]

nono, no worries! dont apologize for that... i also tried playing with that, but to no success

[south fulcrum]

so you are doing a brute-force approach, basically trying all the paths?

[jaunty lance]

yes, by storing all the possible paths in an array and having another array to store the cheapest path (which i will be printing out)

so if the sum of the second possible path is smaller than the sum of the first path, it SHOULD be updating the cheapest array by copying the 2nd path into it and only printing that out.

that is the idea, i hope i explained it okay!! i am so bad at articulating anything related to code and maths

[south fulcrum]

why not sort put them in a TreeMap<Integer sum, ArrayList<String path>>

normally, you would not want to brute-force, but try some less expansive algo 🤷‍♂️

[jaunty lance]

i havent been taught treemaps or arraylist yet

[south fulcrum]

ok

ArrayList<T> is just a wrapper over T[]

[jaunty lance]

i have no idea what that means

let me watch a video

[south fulcrum]

but more memory efficient

you just keep the best route