package com.mmnaseri.cs.ctci.ch08.p11;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Mohammad Milad Naseri (mmnaseri@programmer.net)
 * @since 1.0 (11/26/16, 10:25 PM)
 */
public class RecursiveDenominatorCounter implements DenominatorCounter {

    @Override
    public int makeChange(int amount) {
        int[] denominators = {25, 10, 5, 1}; //putting this in decreasing order makes it more efficient
        final Map<ChangeAmount, Integer> cache = new HashMap<>();
        return makeChange(denominators, amount, 0, cache); //try breaking it to change by taking "25"s (the 0th denominator).
    }

    private int makeChange(int[] denominators, int amount, int index, Map<ChangeAmount, Integer> cache) {
        if (index >= denominators.length - 1) {
            return 1; //this is the end of the recursion
        }
        final ChangeAmount changeAmount = new ChangeAmount(amount, index);
        if (cache.containsKey(changeAmount)) {
            return cache.get(changeAmount);
        }
        int count = 0;
        int ways = 0;
        while (count * denominators[index] <= amount) {
            ways += makeChange(denominators, amount - count * denominators[index], index + 1, cache); //see how many ways we can break the rest of the money while considering only the remaining denominators
            count ++; //add one more coin to pay for more of the money using this denominator
        }
        cache.put(changeAmount, ways);
        return ways;
    }

    private static class ChangeAmount {

        private final int amount;
        private final int index;

        private ChangeAmount(int amount, int index) {
            this.amount = amount;
            this.index = index;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ChangeAmount that = (ChangeAmount) o;
            return amount == that.amount && index == that.index;
        }

        @Override
        public int hashCode() {
            int result = amount;
            result = 31 * result + index;
            return result;
        }
    }

}

@@ -316,112 +316,8 @@
 ) %7B%0A
-        int%5B%5D denominators = %7B25, 10, 5, 1%7D; //putting this in decreasing order makes it more efficient%0A
     
@@ -400,36 +400,26 @@
  makeChange(
-denominators
+25
 , amount, 0,
@@ -419,11 +419,8 @@
 unt,
- 0,
  cac
@@ -532,23 +532,13 @@
 (int
-%5B%5D denominators
+ coin
 , in
@@ -550,19 +550,8 @@
 unt,
- int index,
  Map
@@ -599,38 +599,15 @@
 if (
-index %3E= denominators.length -
+coin ==
  1) 
@@ -742,21 +742,20 @@
 amount, 
+co
 in
-dex
 );%0A     
@@ -918,35 +918,20 @@
 count * 
-denominators%5Bindex%5D
+coin
  %3C= amou
@@ -967,28 +967,26 @@
 eChange(
-denominators
+next(coin)
 , amount
@@ -1000,38 +1000,12 @@
 t * 
-denominators%5Bindex%5D, index + 1
+coin
 , ca
@@ -1087,38 +1087,28 @@
 ing 
-only the remaining denominator
+the next set of coin
 s%0A  
@@ -1268,32 +1268,248 @@
 rn ways;%0A    %7D%0A%0A
+    private int next(int coin) %7B%0A        switch (coin) %7B%0A            case 25:%0A                return 10;%0A            case 10:%0A                return 5;%0A            default:%0A                return 1;%0A        %7D%0A    %7D%0A%0A
     private stat
@@ -1593,21 +1593,27 @@
 nal int 
-index
+denominator
 ;%0A%0A     
@@ -1652,21 +1652,27 @@
 nt, int 
-index
+denominator
 ) %7B%0A    
@@ -1722,21 +1722,33 @@
 his.
-index = index
+denominator = denominator
 ;%0A  
@@ -2025,27 +2025,39 @@
  && 
-index == that.index
+denominator == that.denominator
 ;%0A  
@@ -2187,13 +2187,19 @@
 t + 
-index
+denominator
 ;%0A  

update answer to p11 to an easier but less extensible solution