Iterating a Diophantine equation over a list of itself in python

Question

I'm self-studying MIT Open Courseware Introduction to Computer Science and Programming. Problem Set 2 involves Diophantine equations based on counting sums of chicken nugget boxes (6, 9, or 20).

The way I thought about creating an algorithm was like creating a virtual measuring stick (like in wood shop), where the sizes of measurements (values) are noted on the stick and then transferred to another piece.

If I imagined it being used on a number line, it would point out the initial values, where I would mark those spots and, then, I'd move the zero point to the first mark it came across and make new marks, and repeat that, always going forwards.

So, take a formula of sums: x=0, a=x+6, b=x+9, c=x+20, which each get appended to a list, which now looks like this: [6,9,20]. What I then want to do, is have x switch to the next greatest value in the list, creating new values for the other variables which are also appended to the list. The next value for x would be 6, changing the other variables and resulting in a list that looks like this: [6,9,20,12,15,26]. Then, 9, and so on.

My first problem was duplicates and the order of the list causing infinite loops. I corrected that by adding a line that created a set of the list that turned back into the list again. This worked mostly.

But, and here is the problem, it doesnt fill the list with all the values that are possible. It doesnt put 48 into the list, for example, which is an obvious multiple of 6.

My guess is that my problem has something to do with the fact that I'm iterating over a list that is constantly being edited and/or appended to.

I know that there are algorithms I could redesign the assignment with using, because I did the research and even saw how others coded answers for this problem, and I understand that now, but I'd still like to fix my own way of programming a solution to the problem. Here's my code so far:

## Name some initial variables in diophantine equations
x=0
a, b, c= x+6, x+9, x+20

## Create a list to catch values, aka fish
fish = [a,b,c]
## Here goes
while x <= 60:
    for i in fish:
        x = i
        fish = list(sorted(fish))
        a, b, c= x+6, x+9, x+20
        ## option to see what its doing
        print x,a,b,c
        ## catch the values into the list
        fish.append(a)
        fish.append(b)
        fish.append(c)
        ## get rid of duplicate numbers in the list
        fish = list(set(fish))
        a, b, c= x+6, x+9, x+20


else:
    print fish
## Create new list of values NOT caught by the equation

lastMissingFish = list(set(range(0,50))-set(fish))

## Print the last number not reached by the equation
print lastMissingFish [-1]

Answer 1

Modifying the same collection you are iterating over is almost always not a good idea, because iteration expects the underlying collection to not get modified. In particular, iterating over a list in Python while modifying it seems to have...quirky results. Try changing it to explicitly index the list and increment the index instead, like so:

## Create a list to catch values, aka fish
fish = [0]
## Here goes
x, i = 0, 0
while x <= 60 and i < len(fish):
        x = fish[i]
        a, b, c = x+6, x+9, x+20
        ## catch the values into the list
        fish.append(a)
        fish.append(b)
        fish.append(c)
        ## get rid of duplicate numbers in the list.
        fish = sorted(set(fish))
        i = i + 1

For reference, here's how I'd solve it. The numbers we want to add to the set are all those that can be expressed as a multiple of 6 + a multiple of 9 + a multiple of 20. So let's just iterate over all of them, then create a list out of our set with all elements less than or equal to the max:

def solvechickenboxes(max, x, y, z):

    sums = set()

    for a in range((max/x)+1):
        for b in range((max/y)+1):
            for c in range ((max/z)+1):
                sums.add(a*x + b*y + c*z)

    return [x for x in sums if x <= max]

solvechickenboxes(50, 6, 9, 20)

[0, 6, 9, 12, 15, 18, 20, 21, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 40, 41
, 42, 44, 45, 46, 47, 48, 49, 50]