WCC24.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class WCC24 {
    public static void main(String[] args) {

        WCC24 w = new WCC24();

        // Visible cases
        print(w.TZWeek2ChallengeMoney(12500, new double[] { 0.2, 1, 2, 2.5, 4, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000 }).toString());
        print(w.TZWeek2ChallengeMoney(165200, new double[] { 0.2, 1, 2, 2.5, 4, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000 }).toString());
        print(w.TZWeek2ChallengeMoney(460, new double[] { 0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1, 2, 5, 10, 20, 50, 100, 200, 500 }).toString());
        print(w.TZWeek2ChallengeMoney(0, new double[] { 0.5, 1.5, 2.5 }).toString());
        print(w.TZWeek2ChallengeMoney(8000000000d, new double[] { 1000000000 }).toString());
        print(w.TZWeek2ChallengeMoney(0.52, new double[] { 0.01, 0.03, 0.1 }).toString());
        print(w.TZWeek2ChallengeMoney(6, new double[] { 1 }).toString());
        print(w.TZWeek2ChallengeMoney(-1, new double[] { 0.5, 1.5, 2.5 }).toString());
        print(w.TZWeek2ChallengeMoney(17, new double[] { 1, 3, 5, 6, 9 }).toString());

        // Edge cases that we not in the contest
        print(w.TZWeek2ChallengeMoney(100, new double[] { 25, 50, 75, 90 }).toString()); // [75, 25]
        print(w.TZWeek2ChallengeMoney(105, new double[] { 25, 5, 75, 90 }).toString()); // [75, 25, 5]
        print(w.TZWeek2ChallengeMoney(175, new double[] { 8, 80, 10, 30, 20, 50, 8, 75 }).toString()); // [80, 75, 20]

        // this has two solutions: [75,25] and [70,30], but we can assume that the first
        // solution we found is the correct one
        print(w.TZWeek2ChallengeMoney(100, new double[] { 25, 30, 70, 75, 90 }).toString());
    }

    static void print(String s) {
        System.out.println(s);
    }

    List<Double> solution;
    int nbAvailableNotes;
    Double target;

    List<Double> TZWeek2ChallengeMoney(double amount, double[] availableNotes) {

        // How is it possible to have a negative amount of money? Or is it a money we
        // owe someone? x)
        if (amount <= 0) {
            solution = new ArrayList<>();
            solution.add(-1d);
            return solution;
        }

        /**
         * The approach is to recursively try every possible combination of availables
         * notes with BackTracking.
         */

        // Since we are asked to return the solution with the least number of notes,
        // we'll have to maximize the amount of the notes used, thus we have to sort the
        // availableNotes array so we will always start subtracting the bigger notes
        // before the smaller ones in the seach method. We will start subtracting notes
        // in reverse (from the last index to the first)
        Arrays.sort(availableNotes);

        // store the target amount in an instance variable and put it in the wrapper
        // class in order to make use of Double.compareTo() method for precise
        // comparison
        target = Double.valueOf(amount);

        // Initialize the solution to null, we haven't found a solution yet
        solution = null;

        // number of available notes
        nbAvailableNotes = availableNotes.length;

        // TAKE NOTE OF THIS FOR LOOP
        // we subtract available notes from the biggest to the smallest
        for (int i = nbAvailableNotes - 1; i >= 0; i--) {

            double currentNote = availableNotes[i];

            // we reinitialize the remainingAmount whenever we start subtracting notes
            double remainingAmount = amount;

            // We initialize a possible solution
            Map<Double, Integer> possibleSolution = new HashMap<>();

            while (remainingAmount >= currentNote) {

                // we subtract the current note from remainingAmount and we add it to the
                // possile solution
                remainingAmount -= currentNote;

                if (!possibleSolution.containsKey(currentNote)) {
                    possibleSolution.put(currentNote, 0);
                }

                possibleSolution.put(currentNote, possibleSolution.get(currentNote) + 1);
            }

            // We batcktrack the remaining amount to amount for checking crossed notes
            // combination like in the following
            // ---- amount: 17
            // ---- availableBankNote: [1, 3, 5, 6, 9]
            while (remainingAmount < amount) {

                List<Double> possibleSolutionList = toList(possibleSolution);

                // If we already found a shorter solution, we don't search for larger ones
                if (solution == null || possibleSolutionList.size() < solution.size()) {

                    // This is the recursive method, i is our incremental (so it's decremental here)
                    // variable, we will start decrementing from i-1 for every subsequent nodes
                    // instead of nbAvailableNotes - 1
                    searchSolution(possibleSolution, remainingAmount, i - 1, availableNotes);

                } else if (solution != null && possibleSolutionList.size() > solution.size()) {
                    break;
                }

                remainingAmount += currentNote; // re-add the current node to the remaining amount
                possibleSolution.put(currentNote, possibleSolution.get(currentNote) - 1);
            }
        }

        // We didn't find any solution, so we return [-1];
        if (solution == null || solution.isEmpty()) {
            solution = new ArrayList<>();
            solution.add(-1d);
        }

        return solution;
    }

    private void searchSolution(Map<Double, Integer> possibleSolution, Double remainingAmount, int startIndex,
            double[] availableNotes) {

        List<Double> possibleSolutionList = toList(possibleSolution);

        if (sumUpToTarget(possibleSolutionList)) {

            // if we haven't found any solution yet or the size of the possible solution is
            // smaller than the found solution so far, we will take it as our new solution
            if (solution == null || possibleSolutionList.size() < solution.size()) {
                solution = possibleSolutionList;
            }
            return;
        }

        // Obvious
        if (solution != null && possibleSolutionList.size() > solution.size() || startIndex < 0
                || remainingAmount < 0) {
            return;
        }

        // REMEMBER THE ABOVE FOR LOOP? THIS ONE IS EXACTLY THE SAME, EXCEPT THAT WE
        // DON'T REINITIALIZE THE REMAINING AMOUNT NUT DUPLICATE THE ONE PASSED AS
        // PARAMETER, AND WE CLONE THE POSSIBLE SOLUTION LIST
        for (int i = startIndex; i >= 0; i--) {

            double currentNote = availableNotes[i];
            double newRemainingAmount = remainingAmount;

            // We need to clone the possible solution map so we don't modify the existing
            // map that is used for backtracking
            Map<Double, Integer> newPossibleSolution = clone(possibleSolution);

            while (newRemainingAmount >= currentNote) {

                // we subtract the current note from remainingAmount and we add it to the
                // possile solution
                newRemainingAmount -= currentNote;

                if (!newPossibleSolution.containsKey(currentNote)) {
                    newPossibleSolution.put(currentNote, 0);
                }

                newPossibleSolution.put(currentNote, newPossibleSolution.get(currentNote) + 1);
            }

            while (newRemainingAmount < remainingAmount) { // Backtracking

                List<Double> newPossibleSolutionList = toList(newPossibleSolution);

                // If we already found a shorter solution, we don't search for larger ones
                if (solution == null || newPossibleSolutionList.size() < solution.size()) {

                    // This is the recursive method, i is our incremental (so it's decremental here)
                    // variable, we will start decrementing from i-1 for every subsequent nodes
                    // instead of nbAvailableNotes - 1
                    searchSolution(newPossibleSolution, newRemainingAmount, i - 1, availableNotes);

                } else if (solution != null && newPossibleSolutionList.size() > solution.size()) {
                    break;
                }

                newRemainingAmount += currentNote;
                newPossibleSolution.put(currentNote, newPossibleSolution.get(currentNote) - 1);
            }

        }
    }

    private Map<Double, Integer> clone(Map<Double, Integer> original) {

        Map<Double, Integer> clone = new HashMap<>();

        for (Double key : original.keySet()) {
            clone.put(key, original.get(key));
        }

        return clone;
    }

    private List<Double> toList(Map<Double, Integer> possibleSolution) {
        List<Double> porposedSolution = new ArrayList<>();

        for (Double note : possibleSolution.keySet()) {
            int count = possibleSolution.get(note);

            while (count-- > 0) {
                porposedSolution.add(note);
            }
        }

        Collections.sort(porposedSolution);
        Collections.reverse(porposedSolution);

        return porposedSolution;
    }

    private boolean sumUpToTarget(List<Double> possibleSolution) {
        Double solutionSum = possibleSolution.stream().mapToDouble(Double::doubleValue).sum();
        return target.compareTo(solutionSum) == 0;
    }
}