Coins

8.11 Coins: Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), write code to calculate the number of ways of representing n cents.

• I first decided to take the brute force approach. It runs fine, but the solution isnt correct. I still include it because I think the idea is valuable.

• What I did is take the power set of the permutations to find all the possible subcombinations, and their permutations. After generating these, (which there are a reletively few number of, as QDNP is only 4 characters, and the power set grows at 2^k, which perms at k!) this only generates 65 different permutations of subcombinations.

• I then ran these through a function that would mod all the elements in their strict order in order to find the ones that work (generate change == 0).

• The main problem with this is that now each 'command' has to be iterated through a several number of different times. E.g. "DQ" does not only mean maxing out Dimes and then Quarters, as my algorithm does. It means finding and all combinations of n-number of dimes, and n-number of quarters.

// wrong!

void permute_rec(vector<string> &cur_perms, string fullstr, int index) {
    if (index >= fullstr.length()) return;

    // add char for every word of every index
    vector<string> newPerms;
    for (auto i : cur_perms) {
        string go_back = i;
        for (int j = 0; j <= i.length(); j++) {
            char add = fullstr.at(index);
            i.insert(i.begin() + j, add);
            newPerms.push_back(i);
            i = go_back;
        }
    }

    cur_perms = newPerms;
    permute_rec(cur_perms, fullstr, ++index);
}

vector<string> permute(string str) {
    vector<string> permutations;
    if (str.empty()) return permutations;
    // start us off
    permutations.push_back(string(1, str.at(0)));
    if (str.length() <= 1) return permutations;

    // go
    permute_rec(permutations, str, 1);
    return permutations;
}


vector<string> power_set(string str) {
    vector<string> build;

    build.push_back(" ");

    if (str.length() >= 1) {
        string temp(1, str[0]);
        build.push_back(temp);
    }

    for (int i = 1; i < str.length(); i++) {
        int cur_size = build.size();
        for (int j = 0; j < cur_size; j++) {
            string temp = build[j];
            if (temp == " ") 
                temp = str[i];
            else 
                temp.insert(temp.end(), str[i]);
            //print(build);
            build.push_back(temp);
        }
    }

    return build;
}

unordered_map<string, vector<int>> successful_commands(vector<vector<string>> &all_commands, int change) {

    unordered_map<string, vector<int>> successes;
    vector<int> poten_success;
    int chg_cpy = change;
    int remainder;

    for (int i = 0; i < all_commands.size(); i++) {
        for (int j = 0; j < all_commands.at(i).size(); j++) {
            string cur_command = all_commands.at(i).at(j);
            for (int k = 0; k < cur_command.length(); k++) {

                if (cur_command.at(k) == 'Q') {
                    poten_success.push_back(int(change / 25));
                    change = change % 25;
                }
                else if (cur_command.at(k) == 'D') {
                    poten_success.push_back(int(change / 10));
                    change = change % 10;
                }
                else if (cur_command.at(k) == 'N') {
                    poten_success.push_back(int(change / 5));
                    change = change % 5;
                }
                else if (cur_command.at(k) == 'P') {
                    poten_success.push_back(int(change / 1));
                    change = change % 1;
                }

                // if the change reaches zero before the end of cur_str
                if (change == 0 && k + 1 < cur_command.length()) {
                    poten_success.clear();
                    change = chg_cpy;
                    k = cur_command.length();
                    //continue;
                }
            }

            // only add to hash map if it fully emitted the change
            if (change == 0) {
                successes.insert({ { cur_command } ,{ poten_success } });
            }
            poten_success.clear();
            change = chg_cpy;
        }
    }
    return successes;
}

unordered_map<string, vector<int>> optional_change(int change) {
    unordered_map<string, vector<int>> results;
    if (change == 0) return results;

    // quarters, dimes, nickels, pennies
    vector<string> comb_commands = power_set("QDNP");

    vector<vector<string>> all_commands;
    for (auto i : comb_commands) {
        all_commands.push_back(permute(i));
    }
    print2d(all_commands);

    return successful_commands(all_commands, change);
}

void map_print(unordered_map<string, vector<int>> &map) {
    for (auto &i : map) {
        cout << i.first << ": ";
        for (auto j : i.second) {
            cout << j << ", ";
        }
        cout << endl;
    }
    cout << endl;
    pause();
}

int main() {
    unordered_map<string, vector<int>> change = optional_change(100);

    //printing re
    map_print(change);
}

• New approach:

  • Given just 3 different coins, we can represent this problem visually:

    • Some combination of 25, 10, and 5 to represent a 3-dimensional plane.

  • If each distinct integer of the plane

• However when we limit the graph to its realistic dimensions ContourPlot3D[25 x+10 y+5 z==100, {x, 0, 22}, {y, 0, 22}, {z, 0, 22}], we get something like this:

• Which contains a limited surface area we can calculate. Each distinct whole number point represents a solution. So the surface area represents the total sum of solutions.

• The surface area is a double integral...

• Can apply the same idea with in a 4 dimensional solution, like the problem asks.