Databases
StackOverflow2013
Postsdbo
POHow can I make this method end its recursion and reach a maximum?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow can I make this method end its recursion and reach a maximum?
    primarykey
    data
    text
    <p>I ran into a StackOverflowError when running a solution I wrote to an assignment.</p> <p>These are the exact instructions from the book <em>Java Methods: A &amp; AB</em>:</p> <blockquote> <p>Write a program in which Cookie Monster finds the optimal path from the upper left corner (0,0) to the lower right corner(SIZE-1,SIZE-1) in a cookie grid (a 2-D array). The elements of the grid contain cookies (a non-negative number) or barrels (-1). On each step, Cookie Monster can only go down or to the right. He is not allowed to step on barrels. The optimal path contains the largest number of cookies.</p> <p>The program reads the cookie grid from a file and reports the number of cookies on the optimal path. (The path itself is not reported.) A sample data file is provided in JM\Ch19\Exercises\cookies.dat.</p> <p>Hint: Use a stack. If there is only one way to proceed from the current position, then go there and update the total accumulated number of cookies. If there are two ways to proceed, save one of the possible two points (and its total) on the stack and proceed to the other point. If you have reached the lower-right corner, update the maximum. If there is nowhere to go, examine the stack: pop a saved point, if any, and resume from there.</p> </blockquote> <p>The goal is to give my teacher the best possible path (the one with the most "cookies" on it).</p> <p>Okay. so the mentioned cookie map file is this:</p> <pre><code> 1 3 0 5 -1 7 -1 -1 0 4 2 1 -1 3 2 1 -1 4 -1 5 3 -1 1 0 5 4 8 -1 3 2 2 -1 4 -1 0 0 2 1 0 4 1 -1 8 0 2 -1 2 5 1 4 0 1 -1 0 3 2 2 4 1 4 0 1 4 1 1 6 1 4 5 2 1 0 3 2 5 2 0 7 -1 2 1 0 -1 3 0 -1 4 -1 -1 3 5 1 4 2 1 2 5 4 8 -1 3 2 2 -1 4 -1 0 0 2 1 0 4 1 -1 8 0 2 -1 2 5 1 3 0 5 -1 7 -1 -1 0 4 2 1 0 0 3 1 5 2 1 5 4 1 3 3 </code></pre> <p>And this is the class I use to get a 2-D array of the numbers (I know this part works.) Using A BlueJ debugger, the 2-D array seems to be what I want it to be.</p> <pre><code>import java.util.*; import java.io.*; public class MapReader { public static int[][] grid; public static Scanner gridscanner = null; public static int[][] getMap() { File file = new File("cookies.dat"); try { gridscanner = new Scanner(file); } catch (FileNotFoundException ex) { System.out.println("*** Cannot open cookis.dat ***"); System.exit(1); } int row = 12; grid = new int[row][row]; for(int r = 0; r &lt; row; r++) { for(int c = 0; c &lt; row; c++) { grid[r][c] = gridscanner.nextInt(); } } return grid; } } </code></pre> <p>And here is a class I use to keep track of saved positions, their values, and their locations for when I'm traversing this "cookie map":</p> <pre><code>import java.util.*; public class Point { int row; int col; int total; public Point(int r, int c, int t) { row = r; col = c; total = t; } public int getRow() { return row; } public int getCol() { return col; } public int getValue() { return MapReader.getMap()[row][col]; } public int getTotal() { return total; } } </code></pre> <p>And finally, here is the class that I use to recursively travel through the 2D array. You'll notice that I prefer to go right when two paths are available but then go down when I pop a Point from the "saved" Stack. The problem lies in this class as far as I know: How can I make the method end its recursion and reach a maximum? </p> <pre><code>import java.util.*; public class CookieMonster { private static int[][] map = MapReader.getMap(); private static int max = 11; private static int total, maximum; private static Stack&lt;Point&gt; saved = new Stack&lt;Point&gt;(); public static void main(String[] args) { System.out.println(move(0,0)); } public static int move(int r, int c) { int right = 0; int down = 0; boolean isright = true; boolean isdown = true; if (c &lt; max) { right = map[r][c + 1]; } else isright = false; if (r &lt; max) { down = map[r + 1][c]; } else isdown = false; if (right == -1) isright = false; if (down == -1) isdown = false; if (isright &amp;&amp; isdown) { saved.push(new Point(r + 1, c, total + down)); total += right; move(r, c + 1); } else if (isright) { total += right; move(r, c + 1); } else if (isdown) { total += down; move(r + 1, c); } else { if (r == max &amp;&amp; c == max) { if (maximum &lt; total) maximum = total; } if (!saved.isEmpty()) { Point sd = saved.pop(); total = sd.getTotal(); move(sd.getRow(), sd.getCol()); } } return maximum; } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USTom Wijsman
    1. USMingling94
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTDuplicate
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow can I make this method end its recursion and reach a maximum?
      1. USMarvin Pinto
      1. VTFavorite
    2. VO
      singulars
      1. POHow can I make this method end its recursion and reach a maximum?
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POHow can I make this method end its recursion and reach a maximum?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COrow and col never change?
      singulars
      1. POHow can I make this method end its recursion and reach a maximum?
      1. USbdares
    2. COYou forgot to paste the traversal code.
      singulars
      1. POHow can I make this method end its recursion and reach a maximum?
      1. USVojislav Stojkovic
    3. COAre you missing some code here?
      singulars
      1. POHow can I make this method end its recursion and reach a maximum?
      1. USLouis Wasserman
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload