Once upon a time there was a series of 5 books about a very English hero called Harry. (At least when this Kata was invented, there were only 5. Since then they have multiplied) Children all over the world thought he was fantastic, and, of course, so did the publisher. So in a gesture of immense generosity to mankind, (and to increase sales) they set up the following pricing model to take advantage of Harry's magical powers.
One copy of any of the five books costs 8 EUR. If, however, you buy two different books from the series, you get a 5% discount on those two books. If you buy 3 different books, you get a 10% discount. With 4 different books, you get a 20% discount. If you go the whole hog, and buy all 5, you get a huge 25% discount.
- See more at: http://craftsmanship.sv.cmu.edu/exercises/potter-kata#sthash.qLcFbFvX.dpuf
First, I thought there might be some sets or combinations that could be done ahead. After two hours, I found there was no easy way but a brute force solution.
Then I use a recursive function and dynamic programming.
1. Create a rule map and a dp map:
ruleMap = new HashMap<>();
dp = new HashMap<>();
ruleMap.put(0, 0d);
ruleMap.put(1, 1d);
ruleMap.put(2, 0.95d);
ruleMap.put(3, 0.90d);
ruleMap.put(4, 0.80d);
ruleMap.put(5, 0.75d);
2. Create an array to only contains the numbers of the distinct books. Then sort it.
int[] nums = new int[ruleMap.keySet().size()];
for (int i : list) {
   nums[i]++;
}
Arrays.sort(nums);
3. Define a recursive function.
private double calculatePrice(int[] nums)Â
If all elements in nums are zero: end
If dp has the result, return from dp.
Get all permutations from nums:( no duplicate elements in each permutation). For example, (0,0,0,1,1)=>(0,0,0,0,0),(0,0,0,0,1),(0,0,0,1,0),(0,0,0,1,1)
Traverse all permutations and find the minimum result.
private double calculatePrice(int[] nums) {
       if (isAllZero(nums)) {
           return 0d;
       String numsString = arrayToString(nums);
       if (dp.containsKey(numsString)) {
           return dp.get(numsString);
        // generate all possible permutations
       ArrayList<ArrayList<Integer>> permutations = getPermutations(nums);
        double minimum = Double.MAX_VALUE;
       for (ArrayList<Integer> list : permutations) {
           if (list.isEmpty()) {
               continue;
            for (int i : list) {
               nums[i]--;
           int listSize = list.size();
           minimum = Math.min(
                   calculatePrice(nums) + BASE_PRICE * ruleMap.get(listSize)
                           * listSize, minimum);
           // recover
           for (int i : list) {
               nums[i]++;
       dp.put(numsString, minimum);
       return minimum;
    private ArrayList<ArrayList<Integer>> getPermutations(int[] array) {
       ArrayList<ArrayList<Integer>> permutations = new ArrayList<ArrayList<Integer>>();
       permutations.add(new ArrayList<Integer>());
       for (int i = 0; i < array.length; i++) {
           if (array[i] > 0) {
               int psize = permutations.size();
               for (int j = 0; j < psize; j++) {
                   ArrayList<Integer> tmplist = new ArrayList<>(
                           permutations.get(j));
                   tmplist.add(i);
                   permutations.add(tmplist);
               }
       return permutations;
    private String arrayToString(int[] array) {
       String result = "";
       for (int i : array) {
           result += i + ",";
       return result;
