DiegoVallely/anchor

Test for Anchor Loans

Anchor Loans Test

The proplem solution using knapsack problem

But first, I calculated the total of each combination for each coins as following:

from itertools import *

coins = [1, 5, 7, 9, 11]


def combination(items):
    return ( set(compress(items,mask)) \
        for mask in product(*[[0,1]]*len(items)) )


def determineCoins():
    for x in combination(coins):
        print x

So, I found 32 possible combination given the list of coins

list(combination(range(len(coins))))

[set(),
 {4},
 {3},
 {3, 4},
 {2},
 {2, 4},
 {2, 3},
 {2, 3, 4},
 {1},
 {1, 4},
 {1, 3},
 {1, 3, 4},
 {1, 2},
 {1, 2, 4},
 {1, 2, 3},
 {1, 2, 3, 4},
 {0},
 {0, 4},
 {0, 3},
 {0, 3, 4},
 {0, 2},
 {0, 2, 4},
 {0, 2, 3},
 {0, 2, 3, 4},
 {0, 1},
 {0, 1, 4},
 {0, 1, 3},
 {0, 1, 3, 4},
 {0, 1, 2},
 {0, 1, 2, 4},
 {0, 1, 2, 3},
 {0, 1, 2, 3, 4}]

With the list o all possible combination, I added each of then

map(sum,list(combination(coins)))
[0,
 11,
 9,
 20,
 7,
 18,
 16,
 27,
 5,
 16,
 14,
 25,
 12,
 23,
 21,
 32,
 1,
 12,
 10,
 21,
 8,
 19,
 17,
 28,
 6,
 17,
 15,
 26,
 13,
 24,
 22,
 33]

So if the sum is 23 in the 14th position I have [1,2,4] which is [5,7,11]. That was my solution withou the knapsack problem.

But, in terms of computional thinking, I suppose that the use of knapsack problem was the best aproach. So, I started studying it. In the general this problem is NP-Complete, I choose use it as recursive function and memoization (see views.py).

The web response

First, I've created a server with Django framework because I'm more comfortable in using it (rs) and you don't put restrictions for it. However, as you use the Pyramid framework, I took more time to learn how it works. I already hear spoken of Pyramid but don't use it yet and I enjoy use it :) It is pure Python.