Question

(Warning: spoilers about McNuggets question.)

Answer 1

Someone asked about the McNuggets question, and they said "loop" to iterate over the values. The straightforward implementation uses 3 nested loops, but it made me think that there should be a way to use one loop, and inside the loop you'd generate all the a,b,c values at once. So, you'd be iterating over the whole set of (a,b,c) tuples.

I've done this many times in the past. It uses the same kind of algorithm you'd use to print a number in base b (without using some built-in function). It calculates how many tuples there will be, loops from 0 to that number, breaks the number into the tuple, and returns it.

I coded it up as an iterator class, and as a generator function. Then I tried to use it to solve the McNuggets problem. It worked really well. Then I remembered about the itertools module, and that someone had probably thought of this before. Turns out they did.

But I already coded it up and everything, so I thought I'd post it: http://codepad.org/KsusHRWj
Magical itertools: http://docs.python.org/library/itertools.html

Answer 2

Interesting implementation. Kudos for coding it, mate :-). You even used *args, haha. Just two *dumb* questions about your code: one, did you use 'yield' just because you wanted to use a generator, instead of creating an iterator(I mean, due to the fact that it was test code and you would not read data more than one time). Second question: why didn't the _toTuple instance raised ZeroDivisionError? I mean, I thought xrange created (0,len(self.iterLimit)), so when you wrote val = num%iterLimit[i] I was expecting that error. I didn't understand why it didn't try to divide by zero.
I find itertools incredible useful, but it's the only lib, so far, that I had problems with the docs. They didn't seem complete to me, I tend to use more SO whenever I need to search for something in itertools.

Answer 3

Nevermind the second question, erm. Just realized how dumb it was...

Answer 4

I have both implementations, iterator class and generator function. At first I was confused about how the "yield" keyword worked, so I was trying to put it in my iterator's next() method. Once I figured out the right way to use yield I already had the iterator class written, so I thought I'd finish it off, and then use yield like I had wanted to. So the MultiIter class is an iterator, and the multiIter() function is a generator (which actually returns an iterator under the covers, I think).

I know you figured out your second question, but I'll answer it in case anyone else is reading. limits is a tuple of the limits for each loop, not the current value. iterLimit is a number which is the total number of times the innermost loop would be executed (it's just the product of all the loop limits). I didn't actually test with a 0 limit for one of the loops, so that could cause a problem. [Time passes] It did actually work, because with a 0 limit the iterLimit becomes 0, and it never tries to generate any tuples.

And, like I said, itertools already does this, and better. So don't actually use my implementation, use itertools.

But, since itertools exists, I wonder if we could have used it to solve the McNuggets problem, or used the permutations/combinations in the word game problem set. Would have made those problems easier.

Answer 5

Hi guys,
I was working on the McNuggets problems. I figured out the first one (to find how many sets of 6s, 9s, and 20s are needed to exactly match the order): http://pastebin.com/9BCUHChp
But I am stuck with the next problem which asks to find the largest number of mcnuggets which is not possible to order, given that the nuggets come in sets of 6s, 9s and 20s only. Here's my code: http://pastebin.com/r9uXaVrN
It is not working the way I want it to. :(
I read through the descriptions above, but I am not familiar with those concepts. I just finished lecture 4 and did all the readings as required till lecture 4. But your code seems to be from an advanced level. I am not sure. I am newbie to programming. Any help would be greatly appreciated.

Answer 6

I finally found the after some help from another website:)
http://pastebin.com/Dute3r4k

Answer 7

answer*