# 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.

Last modified 3yr ago