import SimpleOutput;

/**
 * Compute the minimum number of stamps to make some price.  Created
 * as an example for CSC152 99S.  To use this, run
 *   % java NewStampComputer postage price1 price2 ... pricen
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of February 1999
 */
public class NewStampComputer {

  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** 
   * An object to use for debugging output.  If set to null, no 
   * debugging output is generated.
   */
  protected SimpleOutput debugger;

  /**
   * The table used to keep track of previously computed
   * results.
   */
  protected int[] MIN_STAMPS;

  /**
   * The number of steps involved in a computation.
   */
  protected int steps = 0;


  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Build a new NewStampComputer that prints debugging output
   * during computation.
   */
  public NewStampComputer(SimpleOutput debugger) {
    this.debugger = debugger;
  } // NewStampComputer(SimpleOutput)

  /**
   * Build a new NewStampComputer that doesn't print debugging
   * output during computation.
   */
  public NewStampComputer() {
    this.debugger = null;
  } // NewStampComputer


  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Compute the minimum number of stamps required for some postage.
   * All values are expressed in terms of cents.  Uses an improved
   * algorithm, based on the MIN_STAMPS table.
   * Pre: postage >= 0.
   * Pre: fewer than Integer.MAX_VALUE stamps are required.
   * Post: returns the minimum number of stamps required for that
   *   postage (but does not print out which stamps).
   * Post: throws an exception if it's not possible to make that
   *   postage with the given stamp prices.
   */
  public int minStamps(int postage, int[] stampPrices, String indent)
    throws Exception
  {
    // Print some debugging information.
    ++steps;
    if (debugger != null) 
      debugger.println(indent + "Computing minStamps for " + postage);
    // Check if the table has been set up
    if (MIN_STAMPS == null) {
      MIN_STAMPS = new int[postage+1];
      MIN_STAMPS[0] = 0;
      for (int i = 1; i <= postage; ++i) {
        MIN_STAMPS[i] = 0;
      } // for
    } // if (MIN_STAMPS == null)
    // Check if we've already computed the minimum number of stamps
    // for this postage.
    if (MIN_STAMPS[postage] != 0)
      return MIN_STAMPS[postage];
    // Our guess.  Initialized to some outlandish value so that
    // we can tell if we don't have a solution.
    int guess = Integer.MAX_VALUE;
    // The next guess.  Used as we step through potential prices.
    int nextGuess;
    // Base case: no stamps are required for no postage.
    if (postage == 0) return 0;
    // Recursive case: try each price until we find the smallest.
    else {
      for(int i = 0; i < stampPrices.length; ++i) {
        // If the current stamp is cheap enough, try to
        // improve our guess.
        if (stampPrices[i] <= postage) {
          try {
            // Make a new guess
            nextGuess = 1 + minStamps(postage-stampPrices[i],
                                      stampPrices,
                                      indent + " ");
            if (nextGuess < guess) guess = nextGuess;
          } // try
          // No number of stamps could be used for revised postage.
          // Don't update our guess.
          catch (Exception e) { }
        } // if the price was cheap enough.
      } // for
      // Record the number of stamps (even if it's invalid).
      MIN_STAMPS[postage] = guess;
      // We've now computed the minimum number of stamps.  Ensure
      // that it's a reasonable value.
      if (guess != Integer.MAX_VALUE) return guess; 
      // Otherwise, there was no way to sum stamp prices to the given
      // postage, so throw an exception
      else throw new Exception("No combination of stamps for " + postage);
    } // Recursive case
  } // minStamps(int,int[])


  // +------+----------------------------------------------------
  // | Main |
  // +------+

  /** 
   * Read the postage and prices from the command line and then
   * do the comptuation.
   */
  public static void main(String[] args) {
    // Prepare for output.
    SimpleOutput out = new SimpleOutput();
    // Prepare for comptuation.
    NewStampComputer computer = new NewStampComputer(out);
    // Verify the number of arguments.
    if (args.length < 1) {
      out.println("Usage: java StampCounter postage price1 ... pricen");
      System.exit(1);
    }
    // The postage.
    int postage = 0;
    // The stamp prices.
    int[] stampPrices = new int[args.length-1];
   
    // Get the postage.
    try { postage = Integer.parseInt(args[0]); }
    catch (Exception e) {
      out.println("Invalid postage: " + args[0]);
      System.exit(2);
    }
    if (postage < 0) {
      out.println("Postage must be positive");
      System.exit(3);
    }

    // Get the stamp prices.
    for(int i = 1; i < args.length; ++i) {
      try { stampPrices[i-1] = Integer.parseInt(args[i]); }
      catch (Exception e) {
        out.println("Invalid stamp price: " + args[i]);
        System.exit(4);
      }
      if (stampPrices[i-1] <= 0) {
        out.println("Only positive stamp prices are permitted.");
        System.exit(5);
      }
    } // for

    // Compute the minimum number of stamps, counting how many
    // steps were used.
    computer.steps = 0;
    try {  
      out.print(computer.minStamps(postage, stampPrices, ""));
      out.print(" stamps are required for a postage of ");
      out.println(postage);
    }
    catch (Exception e) {
      out.print("No combination of stamps can be used for ");
      out.println(postage);
    }
    out.println("  That computation took " + computer.steps + " steps.");
  } // main(String[])

} // class NewStampComputer