Expense App

App.java

package com.mm.exp;

import java.math.BigDecimal;
import java.util.*;
import java.util.stream.Collectors;

/**
 * Expense Reports.
 * max is maximum to spend
 * source is list of expenses, exceeding maximum.
 * Calculates which sources get you closest to the maximum. If multiple results reach the maximum, prints them all.
For the test data used here, 6 combinations reach the maximum.
 */
public class App 
{
    public static void main( String[] args ) {
        double[] sourceTest = {
                1.00, 2.00, 3.00, 4.00
        };


        double[] source = {
                2.00,
                9.32,
                9.49,
                37.30,
                13.14,
                13.76,
                9.69,
                6.29,
                12.32,
                22.48,
                10.67,
                11.07,
                10.92,
                22.40,
                11.78,
                13.09,
                35.56,
        };

        List<BigDecimal> tempValues = Arrays.stream(source)
                .mapToObj((double s) -> String.format("%15.2f", s).trim())
                .map(BigDecimal::new)
                .collect(Collectors.toCollection(ArrayList::new)); // specify ArrayList to ensure a RandomAccess list
        Collections.sort(tempValues);
        List<BigDecimal> master = Collections.unmodifiableList(tempValues);
//        master.forEach(System.out::println);
        System.out.printf("Sum: %s%n", sumValues(master));
        new App().run(master);
        
//        Collection<Long> timings = new LinkedList<>();
//        long count = 100L;
//        for (long ii=0L; ii<count; ++ii) {
//            long duration = new App().run(master);
//            timings.add(duration);
//        }
//
//        long sum = 0L;
//        for (Long time: timings) {
//            System.out.printf("%d ms%n", time);
//            sum += time;
//        }
//        long mean = (sum + (count / 2L)) / count;
//        System.out.printf("Mean: %d%n", mean);
    }

    private final BigDecimal limit = new BigDecimal("3300.00");
    private final BigDecimal spent = new BigDecimal("3121.59");
    private final BigDecimal max = limit.subtract(spent); // .subtract(new BigDecimal("10.00"));
    private BigDecimal sum = BigDecimal.ZERO;
    private Collection<BigDecimal> data = new LinkedList<>();
    private Collection<List<BigDecimal>> resultList = new LinkedList<>();
    
    int caseCount = 0;

    private long run(List<BigDecimal> master) {
        Deque<BigDecimal> decimalList = new LinkedList<>();
        
        long start = System.currentTimeMillis();
        addEach(master, decimalList, 0);
        long end = System.currentTimeMillis();
        showResult(data);

        System.out.printf("%nCasesFound: %d%nAll:%n", resultList.size());
        for (List<BigDecimal> list: resultList) {
            System.out.printf("%2d  %s = %s%n", list.size(), list, sumValues(list));
        }

        long duration = end - start;
        System.out.printf("Duration: %d ms%n", duration);
        return duration;
    }
    
    private void addEach(List<BigDecimal> master, Deque<BigDecimal> values, int start) {
        int end = master.size();
//        List<BigDecimal> subMaster = master.subList(start, master.size());
        for (int i=start; i<end; ++i) {
            BigDecimal value = master.get(i);
            values.add(value);
            boolean maxedOut = test(values);
            addEach(master, values, i+1);
            values.removeLast();
//            values.remove();
            if (maxedOut) {
                break;
            }
        }
    }

    private boolean test(Collection<BigDecimal> candidateList) {
        BigDecimal cSum = sumValues(candidateList);
        caseCount++;
        if (cSum.compareTo(max) > 0) {
            return true;
        }
//        System.out.printf("Testing %6s < %s from %s %n", cSum, max, candidateList.toString());
//        if ((cSum.compareTo(max) <= 0) && (cSum.compareTo(sum) > 0)) {
        if (cSum.compareTo(sum) > 0) {
            sum = cSum;
            data = new LinkedList<>(candidateList);
        }
        if (cSum.compareTo(max) == 0) {
//            showResult(candidateList);
            resultList.add(new LinkedList<>(candidateList)); // Just for fun.
        }
        return false;
    }

    private static BigDecimal sumValues(Iterable<BigDecimal> candidate) {
        BigDecimal cSum = BigDecimal.ZERO;
        for (BigDecimal bigDecimal: candidate) {
            cSum = cSum.add(bigDecimal);
        }
        return cSum;
    }

    private void showResult(Collection<BigDecimal> candidate) {
        System.out.println("result: " + Arrays.toString(candidate.toArray()));
        System.out.printf("Sum: %s <= %s%n", sum, max);
        System.out.printf("%d cases tested%n", caseCount);
//        System.exit(0);
    }
}