Mo Money, Mo Algorithms

As I am currently interviewing for jobs, I felt it best to review some basic algorithm development. One of the problems I worked on turned out to be quite ideal for analyzing the pros and cons of various techniques and so I thought I'd share them with you here. (I hope this also inspires me to publish more of my theoretical and practical work, that I often write down tediously, but never manage to post anywhere). I assume you know how to program in Python and have a basic understanding of algorithm development and complexity analysis. If you find any of my hidden errors in the following, please let me know.

The problem I have selected is a well-known one: Given an amount of change due, what is the smallest set of coins, whose values add up to that amount? For instance, for 27 cents, the smallest set of coins could be [20,5,2]. Here is a specification of the problem:

Algorithm: change
Signature: change(coins, amount)
Parameters: Set of positive integers (coins), positive integer (amount)
Result: Set of positive integers
Constraints: All coin values are > 0.
Description: Return the smallest set of integers [i₁,...i_n], where each i is a value from coins, that add up to amount. Result is undefined, if no such set exists.

So, let's try our first attempt at the matter. I always find it helpful to try to describe how we humans would solve the problem. In this case, We usually start with the biggest coins or bills and inch our way closer to the solution with increasing granularity. And what does that sound like? Right, a greedy approach. Let's try implementing it. We'll start with a recursive version, as I often find that the more intuitive way to think (though I may just be awfully weird). Go ahead and do it yourself first for practice, if you like!

# Greedy, recursive algorithm
def change(coins, amount):
	if amount == 0:
		return []
	else:
		# Get the valid coin candidates
		cands = [c for c in coins if c <= amount]
 
		# Stop, if there are no candidates left
		if len(cands) == 0:
			return []
 
		# Return the max coin and change the rest
		coin = max(cands)
		return [coin] + change(coins, amount-coin)

So let's try it out and see how well it works:

change([1,2], 7)
> [2, 2, 2, 1]
change([1,2,5,10,20,50], 179)
> [50, 50, 50, 20, 5, 2, 2]
change([5,10], 22)
> [10, 10]

Hey, that looks alright. The last example shows what happens when change does not add up to the required amount. (Basically, we get gypped). So, for now, it seems to work. Let's think about how complex our algorithm is. First, let's look at time complexity: In the worst case, we will have n = amount/min(coins) recursive calls. A more precise bound for this is n = [d + (amount-d)/min(coins)], where d = [floor(amount/max(coins))]. In each call, we find the candidates, and from these, we find the maximum. In the worst case, that is 2c comparisons, where c is the number of coins. This brings us to a complexity of O(2nc). This is acceptable, but we could do better. What about space requirements (apart from those introduced by the parameters and result)? The problem is, that for each recursive call, we generate a new list of candidates (in addition to the space required for the additional parameter stack overhead). Thus, we have a space complexity of O(nc). Let us now try to improve our algorithm. We begin by reviewing what is wrong with the current implementation:

Unnecessary recursion leads to linear space requirements.

Search for maximum is not optimal. A sorted list would be better.

In case of an error (coins do not fit), we may overlook that the change is invalid.

Alas, here is our improved version of the algorithm.

# Greedy, non-recursive
def change(coins, amount):
	result = []
	coins.sort()
	c = len(coins)-1
	while amount > 0:
		# Find largest coin that fits
		while (coins[c] > amount):
			c = c - 1
			if c < 0:
				return -1
 
		# Add coin to result, and update amount
		amount = amount - coins[c]
		result = result + [coins[c]]
	return result

Again, let's see if everything works

change([1,2,5,10,20,50], 179)
> [50, 50, 50, 20, 5, 2, 2]
change([5,10], 22)
> -1

Looking good. Notice, how now, in the last case, we are given a clear indication that something has gone wrong. This may or may not be preferable to the last solution. Let's take a look at the complexities now. The number of outer loop iterations is again bounded by n. Now it may look like (due to the inner loop), that the complexity is cn, but in fact, we observe that the inner loop is run at most once. Assuming that the Python sort operation is somewhat efficient, this leads us to an improved complexity of O(n + c+c*log(c)). Since c is usually small, and n dominates, we may omit c to obtain a time complexity of O(n). Furthermore, apart from the space for parameters and result, our space complexity is now fixed. So in terms of complexity, we have improved quite a bit from before.

However, all is not as shiny as it may seem. Let us now go to Unga-Bunga-Land, where the coins come in the flavors 2, 7, and 10 cents. Let's see what happens when we apply our algorithm now:

change([2,7,10], 14)
> [10, 2, 2]
change([2,7,10], 21)
> -1

Woha. Both answers are incorrect. The first could be more easily expressed as [7,7]. Even worse, the second result suggests there is no valid answer, when clearly [7,7,7] would be one. It turns out, that our greedy algorithm does not work for arbitrary coins. So what do we do now? Well, as we can't really get our heads around this, we do what we always do in that case: Brute-force, i.e. try every possible combination. Now we know that things can get rather large in these scenarios, so we will want to do a depth-first search to save on valuable space. As you may also know, depth-first search leaves many possibilities for optimizations open. The main drawback, namely incompleteness, is not relevant to our case, as we have no infinite branches. So let's implement a classic depth-first search in our coin space:

infinity = 10**6
 
# Depth-first
def change(coins, amount):
	if amount == 0:
		# Found a result
		return []
	elif min(coins) > amount:
		# Invalid path
		return [None]
	else:
		# Return child path with minimum length
		# Ignore paths that start with [None]
		children = [change(coins, amount-c)+[c] for c in coins]
		minlen = infinity
		best = [None]
		for child in children:
			if len(child) < minlen and child[0]:
				minlen = len(child)
				best = child
		return best

For every node in the search tree, we need to handle the following 3 cases: If amount is zero, we return the empty list (as no coins are handed out for 0 change). If the amount is smaller than any coin we have, we return an invalid value. Otherwise, we return the smallest coin-list returned by our children. We ignore those paths that do not lead to a solution. So let's try a few cases:

change([1,2], 7)
> [2, 2, 2, 1]
change([2,7,10], 14)
> [7, 7]
change([2,7,10], 21)
> [7, 7, 7]

Okay, cool, so far everything looks good. But I doubt you and I are hardly happy with the current solution. After all, we know that our tree will grow exponentially. Let's try some *slightly* more complex tests:

change([1,2,5,10], 32)
#...a few minutes pass
> [10, 10, 10, 2]
change([1,2,5,10], 42)
#....

Just as we feared, our implementation is of no practical use, as even minor problems turn out to be unsolvable in reasonable time. The height of the search tree is h = amount/min(coins). Thus an upper bound for the number of nodes in the search tree is O(c^h), where c is the number of coins. Exponential growth in the amount is not exactly reassuring. However, this is a very pessimistic view, as most paths in the tree will be much smaller (since they contain bigger coins and thus reach the goal faster). So, in this case, let us try to be more precise. How many nodes are created for a specific amount exactly? We can find the exact number using the following formula:

Plugging in the values used in the example before, we find that, while much smaller than c^h, the number of nodes in the search tree is still daunting: For the first example a total of f(32) = 96,824,013 nodes need to be generated. Yes, that is 96 million! We will also be waiting a long time for the second test to return, which has a whopping f(42) = 20,680,392,425 nodes. As we do a number of operations in each node, our time complexity is proportional to these numbers. Much more urgent at this point is the question of space complexity. Aren't we filling up memory fast? Well, as we are using a depth-first search, we only expand one node at a time, giving us a maximum of n*h expanded nodes simultaneously. Alas, this is not so much a problem. Still, we mentioned before that depth-first search can be optimized even more. There are two general tricks that can be applied:

Horizontal Compression

Expand only a single child, instead of all of them. A new child can take the memory slot of its old sibling.

Vertical Compression

Move up and down the tree by altering the current state directly.

These ideas are closely related, and usually referred to as backtracking. While the first idea is usually simple to implement, the second one may be more difficult. Let us think about what state information we have in each node. One comes to mind immediately: The coin value of the node! So how can we update the state when moving down the tree? Easy: We append the coin to the current result. When moving up we do the exact opposite: Remove the coin from the result. We also had the remaining amount value, however we can calculate this directly from the total amount and the current coins in the result. So can we implement a depth first search without any states? Unfortunately we missed one crucial value, which has so far been rather hidden on the stack: The current child being expanded. This becomes important when we move back up the tree, and need to know which child to expand next. Thus we will need a stack of h integers for this state information. As every toddler knows, code is worth more than a thousand words, so here is an implementation of the depth-first search using backtracking:

def change(coins, amount):
	path = []
	istack = [0]
	minlen = infinity
	best = [None]
 
	while len(istack) > 0:
		# Get next coin index
		ix = istack[-1]
		istack[-1] = ix+1
 
		# If none left, pop
		if ix >= len(coins):
			del istack[-1]
			path = path[:-1]
			continue
 
		# Get coin at that index
		c = coins[ix]
 
		# Update path and current sum
		path = path + [c]
		cur = sum(path)
 
		# Are we done yet?
		if cur < amount:
			# No, continue aggregating
			istack.append(0)
		else:
			# Yes, check if this is current best solution
			if cur == amount and len(path) < minlen:
				best = path
				minlen = len(path)
			path = path[:-1]
	return best

There you go. No recursion, and very modest space requirements. Of course, all this work has not helped us in any way to reduce time complexity. We still are visiting every node in the tree! So, it is time for our biggest weapon. Its name is dynamic programming, and the idea simple: Split the problem into (possibly overlapping) sub-problems, and reuse results. Actually, we have already split the problem into sub-problems, namely: To find the change of a certain amount, find the change of smaller amounts. For dynamic programming to work, these sub-problems need to be optimal, that is: Their optimal solution must lead to a global optimal solution. In our case, this property holds, as we can quickly verify: Every node of a result path returned by our depth-first search yields an optimal solution for the change problem for the remaining amount at that node. Were this not the case, then a smaller list of coins would exist for that amount. In that case, the global solution would not be optimal, as from that node on, we could insert the more optimal path. Hence, every sub-solution is optimal.

But when does it even make sense to reuse results? The obvious answer: Always when we expect to reach the same sub-problem, that yields the same solution, over and over again (hence, there are "overlapping" ways to reach the same intermediate result). Let's see for our case if we reach a subproblem over and over again. For example, when calculating change([1,2], 10) how often will we reach the subproblem change([1,2], 7)? Recall our formula from above. We slightly modify it (to eliminate the counting of the intermediate nodes) to receive:

In the current case f is therefore:

Wait a minute, that looks a lot like some Fibonacci dude we know! In fact, in this case, f(x) = fib(x+1). Thus f(7) = fib(8) = 21. Woha, so we reach change([1,2], 7) 21 times, and calculate that value over and over again. How often do we reach 9? A scary 55 times. Obviously we should be reusing results.

So let's begin with our final implementation. Here, we shall simply use the depth-first approach from before (as I find it to be much more readable, even if it requires slightly more memory). The only thing we will add is a dictionary of the sub-problems already solved. Thus, for every sub-problem encountered, an entry in the dictionary is created with the best solution to that problem. This leads us to the following implementation:

def changeDP(coins, amount, mem):
	print "At %d" % amount
	if amount == 0:
		return []
	elif min(coins) > amount:
		return [None]
	else:
		minlen = infinity
		best = [None]
		for c in coins:
			amount = amount - c
			if mem.has_key(amount):
				path = mem[amount]+[c]
			else:
				path = changeDP(coins, amount, mem)+[c]
			if len(path) < minlen and path[0]:
				minlen = len(path)
				best = path
			amount = amount + c
		mem[amount] = best
		return best
 
def change(coins, amount):
	return changeDP(coins, amount, {})

So now, let's try all of our killer tests:

# Greedy failed here
change([2,7,10], 14)
> [7, 7]
change([2,7,10], 21)
> [7, 7, 7]
 
# Simple depth-first failed here
change([1,2,5,10], 32)
> [10, 10, 10, 2]
change([1,2,5,10], 42)
> [10, 10, 10, 10, 2]
change([1,2,5,10,20,50], 179)
> [50, 50, 50, 20, 5, 2, 2]

As we see, this solution works very well. To try even larger amounts, you may need to change the maximum recursion depth in python, like this:

import sys
 
# Raise the recursion limit
sys.setrecursionlimit(10000)
 
# Try out a large change problem
change([1,2,7,13,46,91], 4711)
>[91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91,
91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91,
91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91,
91, 91, 91, 46, 13, 7, 2, 2]

Of course, we require more space in this approach than when using depth-first search directly. Our mem dictionary will contain up to n entries, where n = amount. However, the time complexity has been greatly reduced. We now recursively visit every node only once, and store the best path in the mem dictionary. Thus, the number of recursions is bounded by n. In each recursive call we potentially look-up a value in the map c times (c = number of coins). Thus there are up to c*log(n) table comparisons per recursive call. This leads us to a complexity of O(c*n*log(n)). What an improvement compared to the near exponential growth of the simple depth-first search!

This is where we conclude our journey through the wonderful world of algorithms. I hoped the above examples outline some of the approaches available, how they work, and how well they work. In this case, the dynamic programming solution proved to work best for the general problem of finding the minimum amount of coins. For other problems of course, this may be totally different. As always, the best way to learn these things is to do them yourself. Luckily, there is a long list of interesting problems, that you can attempt to tackle! Happy coding!