Mathematical Programming for Hackers

1 Coin Change Example   

1.1 Description

This example illustrates how test-driven-development can be applied to a dynamic program. It is written in Python.

Given a list of \(N\) coins, ordered by their values (\(V_{1}, V_{2}, \dots V_{N}\)) and the total sum \(M\). Find the minimum number of coins to form the sum \(M\) or report that it's not possible to select coins in such a way.

1.2 Central Idea

We have to split the problem in two dimensions: We have to split the problem both for each sum \(i, i \in \{1, \dots M\}\) and for each possible value \(j, j \in \{1, \dots N\}\). Thus our subproblem may be denoted with \(S_{i}^{j}\), the minimum number of coins to form sum \(i\) given all values \(V_{1}, \dots, V_{j}\). Because we did „name and conquer“ (D. E. Knuth, I truly adore you), we only have to find a formula that connects all possible states \(S_{i}^{j}\):

\[S_{i}^{j} = \min \left\{ S_{i}^{j-1}; 1 + \min\{S_{i - V_{j}}^{j}, S_{i - V_{j}}^{j-1}, \dots , S_{i - V_{j}}^{1} \} \right\}.\]

If you have not seen this before: This is called a recursive formula. Recursive since the left-hand-side (LHS) is defined in terms of the right-hand-side (RHS). The RHS selects the minimum of two composed, previous states. The first state is \(S_{i}^{j-1}\), namely the minimum of coins which are needed to form sum \(i\) if we ignore the coin \(V_{j}\). The second state \(1 + S_{i - V_{j}}^{j - 1}\) considers the new coin \(V_{j}\) explicitly. If we choose the new coin \(V_{j}\), we are using at least one coin, that is why the state starts with \(1 + \dots\). Because we are using this coin with value \(V_{j}\), we can subtract its value from our sum \(i\), i.e. \(i - V_{j}\). For this new sum, we already have calculated a solution either with \(V_{j}\) itself or one of its lower values \(V_{j-1}\). We certainly select the best solution, which in this case is the solution with the least coins.

Beware this formula is only applicable if we have defined at least one of those two previous states in the minimization part. That said, keep in mind the formula was born under the sacrifice of readability before mathematical completeness. To make for a full mathematical model, we would have to impose some extra conditions like defining \(\infty\) for all undefined states except \(S_{0}^{j} = 0 \forall j \in \{1 \dots N\}\). And we might come up with a formula for the case \(j = 1\) where we have to differentiate at least from cases where \(V_{1} = 1\) and \(V_{1} \neq 1\).

1.3 Example

Given coins with values \(1, 3\). \(M\) set to be \(6\). We might derive the following table by doing the arithmetic mentally:

\(V_{j}\) / \(i\) 1 2 3 4 5 6
1 1 2 3 4 5 6
3 1 2 1 2 3 2

The row heads contain the possible sums \(i, i \in \{1, \dots , M\}\), the column heads the value of each coin \(V_{j}, j \in \{1, 3\}\). The cells describe \(S_{i}^{j}\) for each combination of \(i\) and \(j\). E.g. in the first row, we have \(j = 1\) and \(V_{1} = 1\). To form the sum \(i = 4\) we need four coins, ergo \(S_{4}^{1} = 4\). In the second row we have both \(V_{1} = 1\) and \(V_{2} = 3\) as possible coin values. Two coins are needed to form the sum \(i = 4\), i.e. \(S_{4}^{2} = 2\).

So far we did not use our formula from the previous section. Now let us test our formula against our table. I would like to select the cases \(i = 4\) and \(i = 6\) with all coins, i.e. \(S_{4}^{2}\) and \(S_{6}^{2}\):

\begin{align*} S_{4}^{2} &= \min \{S_{4}^{1} ; 1 + \min\{S_{4 - V_{2}}^{2}, S_{4 - V_{2}}^{1} \} \} \\ &= \min \{4 ; 1 + \min\{S_{4 - 3}^{2}, S_{4 - 3}^{1} \} \} \\ &= \min \{4 ; 1 + \min\{S_{1}^{2}, S_{1}^{1} \} \} \\ &= \min \{4 ; 1 + 1 \} \\ &= \min \{4 ; 2 \} \\ &= 2 \\ \end{align*} \begin{align*} S_{6}^{2} &= \min \{S_{6}^{1} ; 1 + \min\{S_{6 - V_{2}}^{2}, S_{6 - V_{2}}^{1} \} \} \\ &= \min \{6 ; 1 + \min\{S_{6 - 3}^{2}, S_{6 - 3}^{1} \} \} \\ &= \min \{6 ; 1 + \min\{S_{3}^{2}, S_{3}^{1} \} \} \\ &= \min \{6 ; 1 + \min\{1, 3 \} \} \\ &= \min \{6 ; 1 + 1 \} \\ &= \min \{6 ; 2 \} \\ &= 2 \\ \end{align*}

Both cases are in line with our formula, hooray. Since we now have a very clear understanding of what is to come, let us head towards the computer doing this for us.

1.4 Computer Program

However, before we start hammering on our keyboards you might go out in the wild and check on some of the other resources there are on the coin changing problem. You may soon see, that those solutions often totally neglect our \(\min\{S_{i - V_{j}}^{j}, S_{i - V_{j}}^{j-1}, \dots , S_{i - V_{j}}^{1} \}\). This is so because in computer programming it seems more practicable and even so easier to code if we speak about updating a variable's value. In formal math, I do not see any need to do so since we have all those nice letters on our keyboard. And if they do not suffice, we can easily borrow some greek letters for low interests. However, in programming there is KISS – Keep it simple, stupid. And updating is a lot simpler than carrying around extra indices and alike. Our new formula looks like this:

\[S_{i} := \min \left\{ S_{i}; 1 + S_{i - V_{j}} \right\}.\]

With this formula, we make sure all previous values \(S_{i}\) are already the best ones. We now can appreciate this form, since we know the exact mathematics behind it. Withal I find it very little appealing to skip the math and jump right into this formula. I think the math makes it much better to understand and implement.

1.4.1 Python Program

I have based the design of this python program on the demands of test-driven-development (ttd). This means in easy words: Write a test and then make the test pass. I value this as a terrific source to gain speed in development in various ways: At first. it makes me think exactly how I want my out- and input to look like. Secondly and tightly connected to my previous point, I am unable to write sloppy programs as I have done all my lifetime. I think with ttd I left behind my state of coding infantilism and finally succeeded in writing kind of mature code which tests both for edge cases and an acceptable exception management. Sadly I have never done this before and came to realize, while coding this, that all my prior programs are doomed to fail because I never cared about these details that rather make a program shine. ttd taught me that the computer program is not about the core algorithm but about managing all those little things around it. For sure only if you ever intend to write serious production code. Thirdly ttd saved some time because unintended changes become strikingly clear.

  1. Test Suite
    """Tests for the Coin Changing Problem"""
    
    import unittest
    from coinchange import *
    
    
    class CoinChangeInitialization(unittest.TestCase):
    
        def test_init_with_coins(self):
            self.mycoins = [1, 2]
            self.Changer = CoinChanger(self.mycoins, 99)
            self.assertEqual(self.Changer.V, self.mycoins)
    
        def test_raise_exception_if_one_not_among_coins(self):
            self.coinswithoutone = [2, 3]
            self.assertEqual(True, 1 not in self.coinswithoutone)
            self.assertRaises(ValueError, CoinChanger, self.coinswithoutone, 99)
    
        def test_raise_exception_if_not_initialized_with_list_first(self):
            self.assertRaises(ValueError, CoinChanger, 1, 99)
    
        def test_raise_exception_if_not_initialized_with_pos_integer_scnd(self):
            self.assertRaises(ValueError, CoinChanger, [1], [99])
            self.assertRaises(ValueError, CoinChanger, [1], -1)
            
    
    class CoinChangeReturnValues(unittest.TestCase):
    
        def setUp(self):
            self.coins_one_input_output = ((0, 0), (1, 1), (2, 2), (3, 3),
                                           (57, 57), (60, 60))
            self.coins_one_two_in_out = ((0, 0), (1, 1), (2, 1), (3, 2), (4, 2),
                                         (9, 5), (10, 5), (19, 10), (20, 10))
            self.coins_one_three_five_in_out = ((0, 0), (1, 1), (3, 1), (5, 1),
                                                (6, 2), (9, 3), (11, 3))
    
        def test_raise_exception_if_sum_to_be_returned_out_of_range(self):
            self.Changer = CoinChanger([1], 60)
            self.assertRaises(ValueError, self.Changer.no_coins_returned, 61)
    
        def test_only_coin_with_value_one_return_is_easy(self):
            self.Changer = CoinChanger([1], 60)
            for (value, nocoins) in self.coins_one_input_output:
                self.assertEqual(self.Changer.no_coins_returned(value), nocoins)
    
        def test_coins_one_two_test_basic_algorithm(self):
            self.Changer = CoinChanger([1, 2], 60)
            for (value, nocoins) in self.coins_one_two_in_out:
                self.assertEqual(self.Changer.no_coins_returned(value), nocoins)
    
        def test_coins_one_three_five(self):
            self.Changer = CoinChanger([1, 3, 5], 60)
            for (value, nocoins) in self.coins_one_three_five_in_out:
                self.assertEqual(self.Changer.no_coins_returned(value), nocoins)
    
                
    def main():
        unittest.main()
    
    if __name__ == '__main__':
        main()
    
  2. Program
    """A solution approach to the coin changing problem."""
    
    # imports
    
    import sys
    
    # constants
    # exception classes
    # interface functions
    # classes
    
    class CoinChanger(object):
    
        def __init__(self, lst_V, int_maxsum):
    
            if type(lst_V) != list:
                raise ValueError("First argument must be a list!")
            
            if 1 not in lst_V:
                raise ValueError("There is no coin with value '1'!")
    
            if type(int_maxsum) != int:
                raise ValueError("Second argument must be an integer!")
    
            if int_maxsum < 1:
                raise ValueError("Second argument must be positive!")
    
            self.V = lst_V
            self.S = list(range(0, int_maxsum + 1))
    
            # initialize lookup table via Dynamic Program
            for j in range(1, len(self.V)):
                for i in range(1, len(self.S)):
                    ## we need error handling if we call out of range (e.g. S[i] = 1)
                    self.S[i] = min(self.S[i], 1 + self.S[i - self.V[j]])
    
        def no_coins_returned(self, int_sum_to_be_returned):
    
            if int_sum_to_be_returned > max(self.S):
                raise ValueError("Sum to be returned out of range!")
    
            # if len(self.V) == 1:
            #     return(self.S[int_sum_to_be_returned])
            return(self.S[int_sum_to_be_returned])
            
    
    # internal functions & classes
    
    def main():
        pass
    
    
    if __name__ == '__main__':
        status = main()
        sys.exit(status)
    
  3. Run Program
    python3 ./python/coinchangetests.py -v 2>&1
    true
    
    test_init_with_coins (__main__.CoinChangeInitialization) ... ok
    test_raise_exception_if_not_initialized_with_list_first (__main__.CoinChangeInitialization) ... ok
    test_raise_exception_if_not_initialized_with_pos_integer_scnd (__main__.CoinChangeInitialization) ... ok
    test_raise_exception_if_one_not_among_coins (__main__.CoinChangeInitialization) ... ok
    test_coins_one_three_five (__main__.CoinChangeReturnValues) ... ok
    test_coins_one_two_test_basic_algorithm (__main__.CoinChangeReturnValues) ... ok
    test_only_coin_with_value_one_return_is_easy (__main__.CoinChangeReturnValues) ... ok
    test_raise_exception_if_sum_to_be_returned_out_of_range (__main__.CoinChangeReturnValues) ... ok
    
    ----------------------------------------------------------------------
    Ran 8 tests in 0.001s
    
    OK
    
  4. Final Remarks

    One could extend the program to accept arguments from command line, deal with coins where sum amounts cannot be represented, more extreme tests and so forth. However, I just wanted to make sure I understood unit-tests and test-driven-development in Python so these tasks are left up to the reader to complete.