Python solution for SPOJ problem 'Buying apples'

apples.py

import collections

# From
# http://stackoverflow.com/questions/1653970/does-python-have-an-ordered-set
class OrderedSet(collections.OrderedDict, collections.MutableSet):

    def update(self, *args, **kwargs):
        if kwargs:
            raise TypeError("update() takes no keyword arguments")

        for s in args:
            for e in s:
                self.add(e)

    def add(self, elem):
        self[elem] = None

    def discard(self, elem):
        self.pop(elem, None)

    def __le__(self, other):
        return all(e in other for e in self)

    def __lt__(self, other):
        return self <= other and self != other

    def __ge__(self, other):
        return all(e in self for e in other)

    def __gt__(self, other):
        return self >= other and self != other

    def __repr__(self):
        return 'OrderedSet([%s])' % (', '.join(map(repr, self.keys())))

    def __str__(self):
        return '{%s}' % (', '.join(map(repr, self.keys())))

    difference = property(lambda self: self.__sub__)
    difference_update = property(lambda self: self.__isub__)
    intersection = property(lambda self: self.__and__)
    intersection_update = property(lambda self: self.__iand__)
    issubset = property(lambda self: self.__le__)
    issuperset = property(lambda self: self.__ge__)
    symmetric_difference = property(lambda self: self.__xor__)
    symmetric_difference_update = property(lambda self: self.__ixor__)
    union = property(lambda self: self.__or__)


def sort(packets):
    '''Sort the packets with respect of their price/quantity ratio.
    A list of tuples (quantity, price) where:

        price_i / quantity_i < price_(i + 1) / quantity_(i + 1)

    In case of equality, the lower quantity is put first.
    '''
    return sorted(((i, price) for i, price in enumerate(packets, 1) if price != -1),
                  key=lambda t:t[1]/float(t[0]))


def compute_price(chosen, prices):
    '''Compute the total price for the chosen packets, given
    all the prices.
    '''
    return sum(prices[g] for g in chosen)


def solve(n, k, packets_list):
    '''Solve a single case.
    
    The core idea
    =============
    
    The base idea revolves around these simple concepts:
    
        1. Packets are sorted with respect to their price/quantity ratio
           (see the `sort` function).
        
        2. A list of candidate solutions is built, starting from the single
           quantities themselves.
           
        3. At each iteration, from every candidate, other `l` new candidates
           are constructed, where `l` is the number of packets. To the base
           candidate we add every quantity. For example:
           
             quantities = [1, 2, 3]
             candidates = {(1, ), (2, ), (3, )}
             # First iteration
             candidates = {(1, 1), (1, 2), (1, 3),
                           (2, 1), (2, 2), (2, 3),
                           (3, 1), (3, 2), (3, 3)}
        
        4. However, not all of the new candidates are really added the the new
           candidates list. If we observe that the sum of an old candidate has
           already exceeded the `k` value, it is useless to keep it as a candidate
           solution, since that candidate, with all the other candidates it can
           generate, won't be acceptable solutions.
           Optimizations like this help to reduce greatly the number of cases to
           analyze.

        5. When a solution is found, we compare it against the previous minimum:
           if it is lower we take it as a new minimum, otherwise we continue.

        6. At the end, if we found the minimum price we return it, otherwise we
           return -1.
    
    Variables reference
    ===================
    
    I list here the most important ones:

        * packets: packets already sorted.
        * prices: dictionary in quantity: price form.
        * minimum: the minimum solution found. Default to float('inf').
        * quantities: only the quantities from `packets`, keeping the sorted order.
        * most_favorable: quantities[0], i.e. the quantity which has the most favorable
          price / quantity ratio.
        * discarded: a set which contains all discarded combinations, for future lookup.
        * candidates: the candidate solutions. At start they are simply 1-element tuples
          containing each element from `quantities`. An example:
          
            >>> quantities = [1, 2, 3]
            >>> candidates = {(1,), (2,), (3,)}  # An OrderedSet really


    Detailed process
    ================
    
        1. Sort the packets with the `sort` function.
        2. Look for a "fast" solution with the most favorable quantity:
            a. Calculate ``divmod(k, most_favorable)``

        DOCSTRING WIP
    '''
    packets = sort(packets_list)
    prices = dict(packets)
    minimum = float('inf')
    for g, price in packets:
        if g == k:
            minimum = price
            break
    quantities = zip(*packets)[0]
    most_favorable = quantities[0]
    q = min(quantities)
    # Look for a fast solution
    # A fast solution is one of the form: u * quot + rem == k and quot + 1 <= n
    # where `u` is the most favorable quantity (the one for which the ratio
    # price/quantity is minimum).
    # If a fast solution is not found, then all subsequent ones are tried,
    # decreasing `quot` and increasing `rem` by `q`.
    quot, rem = divmod(k, most_favorable)
    while quot > 0:
        if rem in quantities and quot + 1 <= n:
            fast_solution = quot * prices[most_favorable] + prices[rem]
            if fast_solution < minimum:
                minimum = fast_solution
        rem += most_favorable
        quot -= 1
    discarded = set()
    # Initialize the set
    candidates = OrderedSet()
    for g in quantities:
        candidates.add((g, ))
    # Try n - 1 times (because candidates has already been filled once)
    for _ in xrange(n - 1):
        if not candidates:
            break
        new = OrderedSet()
        for c in candidates:
            for g in quantities:
                new_c = tuple(c + (g, ))
                sorted_c = tuple(sorted(new_c))
                # Have we already met this combination?
                if sorted_c in discarded:
                    continue
                s = sum(new_c)
                c_price = compute_price(new_c, prices)
                # We found a solution!
                if s ==  k and c_price < minimum:
                    minimum = c_price
                # Make these conditions more strict to gain speed
                # (reduce the number of candidates)
                if s + q < k and c_price + packets[0][1] < minimum:
                    new.add(new_c)
                else:
                    discarded.add(sorted_c)
        candidates = new
    return minimum if minimum != float('inf') else -1


# It still fails these ones (time limit exceeded):
#solve(51, 53, [-1, 3, -1, 2, 8, 10, -1, 19])

# The answer to the above is: 32 (from [4] * 12 + [5])