import itertools

##
## Class-based implementation. (Iterator)
##
class MultiIter(object):
    """
    Wraps up several nested loops into one iterator which returns a tuple
    of loop variables.
    """
    def __init__(self, *args):
        """
        List loop limits in order you want them.
        """
        self.limits = args
        self.currentNum = -1
        self.iterLimit = reduce(lambda x,y: x*y, self.limits, 1)

    def __iter__(self):
        return self

    def next(self):
        self.currentNum += 1
        if self.currentNum == self.iterLimit:
            raise StopIteration
        t = self._toTuple(self.currentNum)
        return t

    def _toTuple(self, num):
        result = ()
        for i in xrange(len(self.limits)):
            val = num % self.limits[i]
            num = num / self.limits[i]
            result += (val,)
        return result


##
## Function-based implementation.  (Generator)
##
def _toTuple(num, limits):
    result = ()
    for i in xrange(len(limits)):
        val = num % limits[i]
        num = num / limits[i]
        result += (val,)
    return result

def multiIter(*args):
    """
    Wraps up several nested loops into one generator which returns a tuple
    of loop variables.
    """
    limits = args
    iterLimit = reduce(lambda x,y: x*y, limits, 1)
    for i in xrange(iterLimit):
        t = _toTuple(i, limits)
        yield t

##
## Tests for multi-iter stuff.
##
def testClass():
    for t in MultiIter(2, 3, 4):
        print str(t)

def testFunction():
    for t in multiIter(2, 3, 4):
        print str(t)

def testBoth():
    cL = [t for t in MultiIter(2, 3, 4)]
    fL = [t for t in multiIter(2, 3, 4)]
    for t in zip(cL, fL):
        if t[0] != t[1]:
            print str(t)

##
## Example usage of multiIter to solve McNuggets problem.
##
def mcnuggets():
    current = 0
    lastUnbuyable = 0
    while current - lastUnbuyable <= 6:
        #print "Testing %d, lastUnbuyable = %d" % (current, lastUnbuyable)
        for t in multiIter(current / 6 + 1, current / 9 + 1, current / 20 + 1):
        #for t in itertools.product(xrange(current / 6 + 1), xrange(current / 9 + 1), xrange(current / 20 + 1)):
            if 6*t[0] + 9*t[1] + 20*t[2] == current:
                print "Can buy %d (= 6*%d + 9*%d + 20*%d)" %\
                      (current, t[0], t[1], t[2])
                break
        else: # when for loop exits normally
            print "Can't buy %d" % current
            lastUnbuyable = current
        current += 1
    print "Maximum McNuggets that can't be bought: %d" % (lastUnbuyable)