//Zachary Fitzsimmons                       Period 4                CookieMonster.java
/*
 * This program finds the path with the most 'cookies' in a data file.
 **/
import java.io.*;
import java.util.*;
public class CookieMonster
{
  public static void main() throws IOException
  {
     Integer x = 0, y = 0; 
     Scanner scan = new Scanner(new File("cookies.dat"));
     Integer[][] map = new Integer[12][12];
     Stack<Integer> map_values = new Stack<Integer>();
     Stack<String> paths = new Stack<String>();
     
     while(scan.hasNextInt()) // Reads in everything from Scanner
     {
       map[y][x] = scan.nextInt();
       x++; 
       if(x == 12)
       {
         y++;
         x %= 12;
       }
    }
    eatCookies(map, map_values, 0, 0, 0, paths, ""); //calls the eatCookies method recursivly
    
    Integer best = 0;
    String bestpath = "";    
    while(!map_values.empty()) //gets the values from eatCookies out of their repected stacks
    {
      if(map_values.peek() > best)
      {
        best = map_values.pop();
        bestpath = paths.pop();
      }
      else
      {
        map_values.pop();
        paths.pop();
      }
    }
    System.out.println("Most Cookies = " + best + " cookies");
    System.out.println("Best Path = " + bestpath);
  }
  public static void eatCookies(Integer[][] map, Stack<Integer> map_values,
                               Integer total, Integer x, Integer y, Stack<String> paths, String path)
  {
    total += map[y][x];
    path += " " + map[y][x];
    if(x < 11 && map[y][x+1] != -1) //Increment x
      eatCookies(map, map_values, total, x+1, y, paths, path); 
    if(y < 11 && map[y+1][x] != -1) //Increment y
      eatCookies(map, map_values, total, x, y+1, paths, path); 
    if(x == 11 && y == 11) //Add the path
    {
      map_values.push(total);
      paths.push(path);
    }
  }
  //I coiuld only figure out how to get the zig-zap pattern in a while loop.
  /*public static void eatCookies(Integer[][] map, Stack<Integer> values,
                               Integer total, Integer x, Integer y, Stack<String> paths, String path)
  {
    Integer m = 0; 
    while(m < 20)
    {
      while(x < 11 && y < 11)
      {
        total += map[y][x];
        path += " " + map[y][x];
        if(x < 11 && map[y][x+1] != -1) 
          x++; 
        if(y < 11 && map[y+1][x] != -1)
          y++; 
      }
      values.push(total);
      paths.push(path);
      m++;
    }
  }*/
}