Challenge #16: Change is the only constant

so-challenge-16-notes.md

Violet's notes on the Stack Overflow Challenge #16

Initial Thoughts

Greedy doesn't work

A greedy algorithm, starting by taking as much of the biggest coins and then filling the remainder with smaller, doesn't work. Counter example: [[5,4,3,1],[1,1,100,100],7]

If you use the 5, you are stuck with 5 + 1 + 1, but if you take the 4, you get 4 + 3.

Maybe there is a cutoff where you know it's fine to take the larger coin?

A graph approach

You could start at a empty node, {}, and from there reach a number of states by adding 1 available coin to the previous node. For the [5,4,3,1] example, your first children nodes would be {5}, {4}, {3}, and {1}. From each of those states, add another available coin. If ever you overshoot the goal, that node shouldn't be added, and if ever you reach the goal, it's a potential solution.

If you implemented this as a breadth first search, then the first time you reach the target, it will certainly be the shortest way there.

Additionally, permutation of the path to the goal doesn't matter, so you could choose an approach that ensures each path is unique. One easy way would be to only add equal or smaller coins as children nodes off of a parent.

This algorithm's complexity (runtime and memory) seems high, as each subsequent layer widens beyond the last, but also can narrow as paths are eliminated.

Complexity analysis

Let a problem input consist of n denominations, with a target sum of m. For example, for [[5,4,3,1],[1,1,100,100],7] case, n=4 and m=7.

Because denominations are non-zero, the tree has a maximum depth of m. At each layer of the tree, up to n nodes are added to each previous node, meaning the tree grows in width by a factor of n every layer (proof: assume you have an arbitrarily large number of each coin; at most, every node can have n children, one for each denomination). This suggests an upper bound of the algorithm runtime is O(n^m).

The worst case in the inputs given for this approach is [[5,11,17],[10,10,10],34], with n=3 and m=34, which gives a complexity of 1.6677182e+16, or over 10 quadrillion operations. This is just on the cusp of doable on modern hardware, especially with parallel computing, but seems high for the problem at hand.

Even with the bad upper bound, that specific case would solve in just 2 layers, with the solution 17 + 17, so it's not actually that bad.

Possible Improvements with Division

I talked to my wife about this problem at dinner, and I think the algorithm can be further optimized by making the proper greedy choice.

The theorem is that you should never take a coin which is a divisor of a coin available for adding (meaning, with quantity > 0 and denomination <= target sum). The reasoning is that the larger coin should get you closer to the target without changing the reachability of sums <= the target. What remains is to prove (or disprove) this assumption. However, even if it is true, an adversarial example could be constructed using only coprime denominations, eliminating most of the efficiency gained, though 1 coins would never be used until the final stretch of the algorithm.

Theorem

Let $\mathbb{N}$ be the set of positive, natural numbers, and let $\mathbb{N}^+$ be the set of positive, non-zero, natural numbers.

Let $d_a,d_b,t\in\mathbb{N}^+$ such that $\exists q_a,q_b\in\mathbb{N}$ such that $q_ad_a+q_bd_b=t$.

If $d_a \mid d_b$, then $\exists q_a,q_b\in\mathbb{N}$ such that $q_ad_a+q_bd_b=t$ and $q_ad_a\lt d_b$.

Proof

Let $d_a,d_b,t\in\mathbb{N}^+$ and $q_a^0,q_b^0\in\mathbb{N}$ such that $q_a^0d_a+q_b^0d_b=t$ and let $d_a \mid d_b$.

If $q_a^0d_a\lt d_b$, we are done.

Assume $q_a^0d_a\geq d_b$. We know $d_a \mid d_b$, meaning $\exists!\alpha\in\mathbb{N}^+$ such that $\alpha d_a=d_b$. Let $\alpha$ be that number.

It follows that:

$$\begin{split} q_a^0d_a + q_b^0d_b & = (q_a^0 - \alpha)d_a +\alpha d_a + q_b^0d_b \\ & = (q_a^0 - \alpha)d_a + d_b + q_b^0d_b\\ &= (q_a^0 - \alpha)d_a + (1 + q_b^0)d_b \end{split}$$

Additionally, we know:

$$\begin{split} q_a^0d_a&\geq d_b \\ (q_a^0-\alpha)d_a + \alpha d_a&\geq d_b \\ (q_a^0-\alpha)d_a + d_b&\geq d_b \\ (q_a^0-\alpha)d_a + d_b - d_b&\geq d_b - d_b \\ (q_a^0-\alpha)d_a &\geq 0 \\ q_a^0-\alpha &\geq 0 \end{split}$$

Let $q_a^1=q_a^0-\alpha$ and $q_b^1=1+q_b^0$.

Because $q_a^1\geq 0$ and $q_a^0,\alpha\in\mathbb{N}$, $q_a^1\in\mathbb{N}$. Additionally, because $q_b^1&gt;q_b^0\geq 0$ and $1,q_b^0\in\mathbb{N}$, $q_b^1\in\mathbb{N}$.

Additionally, notice that $q_a^1&lt;q_a^0$.

If $q_a^1d_a\lt d_b$, we are done.

Assume $q_a^1d_a\geq d_b$. By the same logic above, substituting $q_a^1$ for $q_a^0$ and $q_b^1$ for $q_b^0$, we can construct $q_a^2=q_a^1-\alpha$ and $q_b^2=1+q_b^1$ such that $q_a^2d_a+q_b^2d_b=t$ and $q_a^2,q_b^2\in\mathbb{N}$.

In the general case, if $q_a^nd_a\geq d_b$, we can construct $q_a^{n+1}=q_a^n-\alpha$. As this sequence is strictly decreasing, eventually there must be an $m$ for which $q_a^{m+1}\lt q_b$.

Q.E.D. $\blacksquare$

Sums of coins

If we have [5,3,2] coins available, does similar logic hold in that 5=3+2?

Seemingly no, given that would imply for this test case [[5,4,3,1],[1,1,100,100],7] that we should pick 5 before 4 and 1, because 5=4+1, and we know that that is an incorrect assumption.

However, it may hold true for cases where the remaining total will be >= the coin value (i.e >= 2x coin value).

Dynamic Programming

As we discover nodes, we could store the values reached and how we reached them and treat them as kind of "meta" coins. For example, if we reach 7 with [4,3], we know we can always add 7 to our running total by adding those same coins. However, I'm not sure how this helps with my approach as it would break the BFS assumption and would only increase the search space. It may be useful as a sort of "short-cut" along with the divisor idea above.

New thoughts

Based on the proof regarding divisors and the idea that it is "safe" to add the largest coin as long as the target is >= 2x its value, a very optimized algorithm could be made. I'm not yet convinced of the second assumtion (that it's safe to add the largest coin as long as the remainder isn't smaller than it).