import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * Command line program to compute a number.
 * For a given sequence of K decimal digits
 * it computes the sum of all variations of numbers
 * from those digits, including decimal fractions.
 *
 * Input digit array {1, 3} leads to 1 + 3 + 1.3 + 3.1 = 8.4
 *
 * Input {1, 1, 2, 3, 4} is supposed to add up to 1802153.2592
 * according to the article at
 * http://www.faz.net/s/RubE2C6E0BCC2F04DD787CDC274993E94C1/Doc~E2573D34C0B2F45BDAC9783B18478F947~ATpl~Ecommon~Scontent.html
 * (Stefan Niggemeier: "11 + 1 = 14". Frankfurter Allgemeine Sonntagszeitung,
 *  13 Oct 2003, issue 41, page 35.)
 *
 * Running the program with those numbers
 * <pre>java AddDigits 1 1 2 3 4</pre>
 * actually yields
 * <pre>Sum: 1802153.2592 (669 numbers).</pre>
 * as output.
 *
 * Caveat: keeps all numbers in memory.
 * A variant of this program could restrict itself to merely generating
 * all numbers, printing them to standard output one number per line.
 * Utilities sort and uniq would then shrink that list to contain only
 * unique numbers.
 * Then an additional program would add the output of that reduced list.
 * This has not been done in order to keep all functionality within the
 * program.
 *
 * @author Marco Schmidt
 * @created 2007-02-07
 */
public class AddDigits {

  /**
   * Convert the argument array and
   * variations of it with the radix point at all possible positions
   * to BigDecimal objects which are then added to the argument map.
   * Example: input {1,2,3,4} leads to the numbers 1234, 1.234, 12.34 and 123.4
   * being added to the map numbers.
   * Generally, an input array of length K will result in an addition of K numbers.
   * Some of the numbers may already be contained in the map.
   * @param number the number as an array of digits
   * @param numbers a map of BigDecimal objects
   */
  private static void addSingleNumberVariations(int[] number, Map numbers) {
    for (int i = 0; i < number.length; i++) {
      int length = number.length;
      if (i > 0) {
        length++;
      }
      StringBuffer sb = new StringBuffer(length);
      for (int j = 0; j < number.length; j++) {
        if (i == j && i > 0) {
          sb.append('.');
        }
        sb.append((char)('0' + number[j]));
      }
      String s = sb.toString();
      //System.out.println(s);
      BigDecimal dec = new BigDecimal(s);
      numbers.put(dec, dec);
    }
  }

  /**
   * Returns if the argument array contains a number more than once.
   */
  private static boolean containsDuplicateValues(int[] a) {
    if (a.length < 2) {
      return false;
    }
    int[] b = new int[a.length];
    System.arraycopy(a, 0, b, 0, a.length);
    Arrays.sort(b);
    for (int i = 0; i < b.length - 1; i++) {
      if (b[i] == b[i + 1]) {
    	 return true;
      }
    }
    return false;
  }

  /**
   * Add all variations of numbers created from digits of
   * a given length (not including the radix point) as BigDecimal
   * objects to a map.  
   */
  private static void createVariations(int[] digits, int length, Map numbers) {
    int[] index = new int[length];
    int[] number = new int[length];
    do {
      if (!containsDuplicateValues(index)) {
        for (int i = 0; i < length; i++) {
          number[i] = digits[index[i]];
        }
        addSingleNumberVariations(number, numbers);
      }
    }
    while (!increase(index, digits.length - 1));
  }

  /**
   * Create all variations of numbers from the given digits
   * as BigDecimal objects and return them as a map.
   */
  private static Map createVariations(int[] digits) {
    Map numbers = new HashMap();
    for (int i = 1; i <= digits.length; i++) {
      createVariations(digits, i, numbers);
    }
    return numbers;
  }

  /**
   * Increases a number by one and returns true if and only if
   * an overflow occurs.
   * The number is given as an array of non-negative int values,
   * each array item being a single digit.
   * The maximum value of a digit is stored in argument max.
   */
  private static boolean increase(int[] index, int max) {
    int i = index.length - 1;
    while (true)
    {
      if (index[i] == max) {
        index[i] = 0;
      } else {
        index[i]++;
        return false;
      }
      i--;
      if (i == -1) {
        return true;
      }
    }
  }

  public static void main(String[] args) {
    // check availability of argument digits
    if (args.length < 1) {
      System.err.println("Usage: AddDigits DIGIT1 DIGIT2 ...");
      System.exit(1);
    }

    // parse digits and put them into an int array
    int[] digits = new int[args.length];
    for (int i = 0; i < args.length; i++) {
       int digit = Integer.parseInt(args[i]);
       if (digit < 0 || digit > 9) {
         System.err.println("All arguments must be decimal digits.");
         System.exit(1);
       }
       digits[i] = digit;
    }

    // collect all number variations
    Map numbers = createVariations(digits);

    // compute the sum of those numbers 
    BigDecimal sum = BigDecimal.ZERO;
    Collection coll = numbers.values();
    Iterator iter = coll.iterator();
    while (iter.hasNext()) {
      BigDecimal item = (BigDecimal)iter.next();
      sum = sum.add(item);
    }

    // print the sum to standard output
    System.out.println("Sum: " + sum + " (" + coll.size() + " numbers).");
  }
}