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();
}
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
