/*
 * Wally.java 
 *
 * starter file with some helpful routines for
 * solving the fuel-minimizing Wally problem...
 */

import java.util.Random;
import java.lang.Math;

/*
 * This is the class to create...
 *
 * It may do pretty much anything, but
 * it needs to have a method (be sure it's static!)
 *
 * public static int minDonuts(int[][] grid)
 *
 */
class Wally
{

  public static int minDonuts(int[][] grid)
  {
      int gridHeight = grid.length;
      int gridWidth = grid[0].length; 

      // sleep for a bit... You probably won't want to do this...
      int millisecondsToSleep = (int)(Math.random()*1000);
      try {
        Thread.sleep( millisecondsToSleep );
      } catch (Exception e) {
        System.out.println("Don't interrupt my sleep!");
      }

      return 42;
  }


  public static void main(String[] args)
  {
      System.out.println("Run  java Timing  instead of   java Wally !");
  }

}

/*
 * This is a timing class, Timing, which we will
 * use to evaluate your Wally code's running time...
 */
class Timing
{

  /*
   * this object, R, lets us create "random"
   * grids of values in a reproduceable way...
   */
  static Random R = new Random(1000000000l); // seeding our RNG

  public static void main(String[] args)
  {
    boolean printStuff = true;
    new Timing(); // be sure that the static data members are created

    int maxValue = 9;
    int size = -1;
    int[][] grid;

    long beforeTime = 0;
    long afterTime = 0;
    long deltaTime = 0;
    int answer;

    if (args.length > 0) 
      size  = Integer.parseInt(args[0]); // specify a single size at the command-line

    if (size == -1)
    {
      for (size=2 ; size<100 ; size*=2) // we will test even larger ones...
      {
        grid = randomGrid(size, maxValue);
        if (printStuff &&size<50) printGrid(grid);

        beforeTime = System.nanoTime();
        answer = Wally.minDonuts(grid);
        afterTime = System.nanoTime();
        deltaTime = afterTime-beforeTime;

        report("size = " + size, answer, deltaTime);
      }
      /* correct answers for the Random seed of 1000000000l are
       *   size = 2, answer = 8
       *   size = 4, answer = 22
       *   size = 8, answer = 43
       *   size = 16, answer = 89
       *   size = 32, answer = 194
       *   size = 64, answer = 380
       */
    }
    else
    {
      grid = randomGrid(size, maxValue);
      if (printStuff && size<50) printGrid(grid);

      beforeTime = System.nanoTime();
      answer = Wally.minDonuts(grid);
      afterTime = System.nanoTime();                                             
      deltaTime = afterTime - beforeTime;
      report("size = " + size, answer, deltaTime);
    }
  } // end of main

  /*
   * prints out the results...
   */
  public static void report(String s, int answer, long time)                   
  {                                                                            
    System.out.println(s + "   Answer: " + answer + 
                           "   Time: " + (time/1000000.0) + " ms.\n\n");
  }                                                                            
                                                                               
  /*
   * copies one grid into another
   */
  public static void copyData(int[][] original_data, int[][] data)             
  {                                                                            
    for (int row=0 ; row<original_data.length ; ++row)                         
      for (int col=0 ; col<original_data[row].length ; ++col)                  
        data[row][col] = original_data[row][col];                              
  }                                                                            
                                                                               
  /*
   * returns a random grid (using randomInteger)
   */
  public static int[][] randomGrid(int size, int max)                          
  {                                                                            
    int[][] data = new int[size][size];                                        
    for (int row=0 ; row<data.length ; ++row)                                  
      for (int col=0 ; col<data[row].length ; ++col)                           
        data[row][col] = randomInteger(max);                                   
                                                                               
    return data;                                                               
  }                                                                            
                                                                               
  /*
   * returns a random integer from 1 to limit, inclusive
   */
  public static int randomInteger(int limit)                                   
  {                                                                            
    return (int)(1+Timing.R.nextDouble()*limit);                                    
  }                                      

  /*
   * prints the grid neatly
   */
  public static void printGrid(int[][] grid)                                   
  {                                                                            
    for (int row=0 ; row<grid.length ; ++row)                                  
    {                                                                          
      for (int col=0 ; col<grid[row].length ; ++col)                           
      {                                                                        
        String num = "" + grid[row][col];                                      
              int L = num.length();                                            
              int totalLength = 2;                                             
              for (int i=L ; i<totalLength ; ++i)                              
                num = " " + num;                                               
        System.out.print(num + " ");                                           
      }                                                                        
      System.out.println();                                                    
    }                                                                          
  }                                                                            
} // end of the Timing class