Question 2 - Finding the best plan

#!/usr/bin/python

import itertools
from collections import defaultdict
from timeit import Timer

class Feature(object):
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return "{0}".format(self.name)

    def __repr__(self):
        return "Feature({0})".format(self.name)

class Plan(object):
    def __init__(self, name, cost, features):
        self.name = name
        self.cost = cost
        self.features = features

    def __str__(self):
        return "{0} plan for ${1} with {2}".format(self.name, self.cost, [str(f) for f in self.features])

    def __repr__(self):
        return 'Plan("{0}", {1}, [Feature(name) for name in {2}])'.format(self.name, self.cost, [f.name for f in self.features])

def find_the_best_plan_naive(plans, features):
    feature2plans = defaultdict(list)
    for plan in plans:
        for feature in plan.features:
            if feature.name in features:
                feature2plans[feature.name].append(plan)

    out = [set(tup) for tup in itertools.product(*feature2plans.values())]
    min_out = min(out, key=lambda x: sum([i.cost for i in x]))
    return min_out

def find_the_best_plan_approx(plans, features):
    # try plans which have all the required features first
    candidates = []
    min_1 = min_2 = None
    for p in plans:
        # print(set(p.features))
        if set(features).issubset(set([f.name for f in p.features])):
            candidates.append(p)
    if candidates:
        min_1 = min(candidates, key=lambda x: x.cost)
        candidates = []
    # try combinations of two plans as well
    for tup in itertools.combinations(plans, 2):
        if set(features).issubset(set([f.name for f in tup[0].features]) | set([f.name for f in tup[1].features])):
            candidates.append(tup)
    if candidates:
        min_2 = min(min_1, min(candidates, key=lambda x: sum([p.cost for p in x]))) if min_1 else min(candidates, key=lambda x: sum([p.cost for p in x]))
    return min_2

if __name__ == '__main__':
    plans = [Plan("6HT2WD", 57, [Feature(name) for name in ['GLKIIH', '4KIJ88', '2488I1', 'OSAGXC', '73W573', '6SPPED']]), Plan("HN18K9", 84, [Feature(name) for name in ['GLKIIH', 'OH4FW0', 'LXI0DA', '4KIJ88', 'OSAGXC', 'AHKS67']]), Plan("Z8XUUR", 4, [Feature(name) for name in ['OSAGXC', '6SPPED', 'GLKIIH']]), Plan("CKYWCQ", 24, [Feature(name) for name in ['6SPPED', 'OH4FW0', 'CHBDBT', 'LXI0DA', '4KIJ88', 'GLKIIH', '2488I1', 'AHKS67', 'OSAGXC']]), Plan("IQLIJT", 55, [Feature(name) for name in ['OH4FW0', 'AHKS67', '73W573', '4KIJ88', '6SPPED', 'CHBDBT', 'GLKIIH']]), Plan("FVGXZ8", 10, [Feature(name) for name in ['OSAGXC', 'GLKIIH', '2488I1', '6SPPED', 'OH4FW0', '73W573', '4KIJ88', 'LXI0DA', 'AHKS67']]), Plan("JNGJNW", 53, [Feature(name) for name in ['6SPPED', '73W573', 'LXI0DA', 'GLKIIH', 'CHBDBT']]), Plan("GN5PGV", 84, [Feature(name) for name in ['6SPPED', '2488I1', '4KIJ88', 'AHKS67', 'CHBDBT', 'OSAGXC', 'LXI0DA', '73W573', 'GLKIIH']]), Plan("LX0J7U", 14, [Feature(name) for name in ['GLKIIH', '73W573', '2488I1', '6SPPED', 'OSAGXC', 'LXI0DA']]), Plan("GZCFFC", 53, [Feature(name) for name in ['AHKS67', '6SPPED', '4KIJ88', '2488I1']]), Plan("B32FMC", 82, [Feature(name) for name in ['OH4FW0', '6SPPED', 'LXI0DA']]), Plan("D1GPZI", 57, [Feature(name) for name in ['GLKIIH', '2488I1', '4KIJ88']]), Plan("YZB12O", 25, [Feature(name) for name in ['OH4FW0', '73W573']]), Plan("N27WOK", 10, [Feature(name) for name in ['OH4FW0', 'LXI0DA', '2488I1']]), Plan("T0YGC7", 27, [Feature(name) for name in ['AHKS67', 'GLKIIH', '4KIJ88']]), Plan("WPWXL7", 97, [Feature(name) for name in ['73W573', '2488I1', '4KIJ88', 'OSAGXC', 'OH4FW0']]), Plan("K1STVT", 76, [Feature(name) for name in ['LXI0DA', '73W573', '2488I1', 'CHBDBT']]), Plan("DM8TAR", 35, [Feature(name) for name in ['73W573', 'LXI0DA', 'GLKIIH', '6SPPED', 'AHKS67', '4KIJ88', 'CHBDBT', 'OSAGXC', '2488I1']]), Plan("PW2D25", 88, [Feature(name) for name in ['AHKS67', 'OH4FW0']]), Plan("2S65RD", 53, [Feature(name) for name in ['OSAGXC', 'AHKS67', 'LXI0DA', 'OH4FW0', '4KIJ88', '2488I1']])]

    required_features = ['AHKS67', '73W573', 'OH4FW0', '6SPPED', 'LXI0DA']

    t = Timer(lambda: find_the_best_plan_naive(plans, required_features))
    print(t.timeit(10))

    t = Timer(lambda: find_the_best_plan_approx(plans, required_features))
    print(t.timeit(10))

2.2247428894
0.00876998901367
Times on my laptop