Published
Edited
Jul 8, 2019
function get_partitions(n, parts) {
// Set aside 'memory' for the dynamic programming solution (making change for smaller amounts using the various
// combinations of denominations of currency)
let data = [];
// Loop through each coin and attempt to make change for the following amount, m, with smaller coins
for (let part = 0; part < parts.length + 1; ++part) {
// Just building up the array as we go, which is okay because we are only accessing previously constructed
// sections of 'memory'
data.push([]);
// Loop through all smaller amounts of money to make change for
for (let m = 0; m < n + 1; ++m) {
// Initialize all entries to zero
data[part].push(0);
// This row is set aside for making change with no coins, so there are zero ways to do so
if (part == 0) {
continue;
}
// If the coin is more than the amount we want to make change for, then the number of ways to make change
// only depends on smaller coins
if (parts[part - 1] > m) {
data[part][m] = data[part - 1][m];
// If the coin is exactly the amount we want to make change for, then we can use this coin, but we also
// have smaller coins that can be used to make change separately
} else if (parts[part - 1] == m) {
data[part][m] = 1 + data[part - 1][m];
// If the coin is smaller than the amount we want to make change for, then the number of ways to make change
// is the number of ways to make it with only smaller coins but also the number of ways to make the
// remaining amount after using this coin
} else if (parts[part - 1] < m) {
data[part][m] = data[part - 1][m] + data[part][m - parts[part - 1]];
}
}
}
// The entry in the last row (all the coins) and last column (the full amount) is what we actually desire
return data[data.length - 1][data[0].length - 1];
}
// Solve this specific problem
get_partitions(500, [1, 2, 5, 10, 20, 50, 100, 200]);
function get_value_formulas(operations, numbers, to_value, num_index=0, running_expr=[], candidates=[]) {
if (running_expr.length == 0) {
running_expr.push(numbers[0]);
}
for (let op in operations) {
running_expr.push(operations[op]);
running_expr.push(numbers[num_index + 1]);
if (num_index + 2 == numbers.length) {
if (eval(running_expr.join().replace(/,/g, '')) == to_value) {
candidates.push(running_expr.join().replace(/,/g, ''));
}
}
else {
get_value_formulas(operations, numbers, to_value, num_index + 1, running_expr, candidates);
}
running_expr.pop();
running_expr.pop();
}
return {value: to_value, candidates: candidates};
}
get_value_formulas(['+', '-', ''],
['1','2','3','4','5','6','7','8','9'],
100)
function get_all_formulas(ops, formula_length, evaluate_to, expr=['1']) {
// For each operation, try it and either evaluate, or go another level deeper
for (let op in ops) {
// Compute what the last number used is (for determining whether to evaluate or not)
let last_num = Number(expr[expr.length - 1]);
// Push the operation to try in the expression
expr.push(ops[op]);
// Place the next number after it
expr.push((last_num + 1));
// Check to see if this expression should be evaluated
if (last_num == formula_length) {
// If so, evaluate the expression
let value = eval(expr.join().replace(/,/g, ''));
// Check to see if this value has been initialized
if (!(value.toString() in evaluate_to)) {
// If not, set it to zero (will be increased regardless of initialization so 0 is fine)
evaluate_to[value] = 0;
}
// This value has been evaluated to, so increase its evaluation count
evaluate_to[value] += 1;
} else {
// Go another level deeper
get_all_formulas(ops, formula_length, evaluate_to, expr);
}
// Remove the number used (just to get rid of operation)
expr.pop();
// Remove the operation to try another or quit if this operation has been exhausted
expr.pop();
}
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.