I've managed to stump myself on some pretty elementary shit so I'm sending up the help flare, but I figured if there's enough people with random coding questions/problems maybe this can be used like a random question-ish thread, if so I'll stick it later on...
Currently working on the MIT OCW 6.00 Introduction to CompSci/Programming course, I know a few other people here on BG have taken it already as well, the class is in Python, for the record I have had almost zero coding experience prior to this minus working with Spellcast XMLs, so I'll probably be asking some dumb questions.
The problem at hand: http://ocw.mit.edu/courses/electrica...ents/pset2.pdf
Here's the code that I've come up with, which does not currently work:Solving a Diophantine Equation
Using this theorem, we can write an exhaustive search to find the largest number of McNuggets that cannot be bought in exact quantity. The format of the search should probably follow this outline:
- Hypothesize possible instances of numbers of McNuggets that cannot be purchased exactly, starting with 1
- For each possible instance, called n, Test if there exists non-negative integers a, b, and c, such that 6a+9b+20c = n. (This can be done by looking at all feasible combinations of a, b, and c)
- If not, n cannot be bought in exact quantity, save n
- When you have found six consecutive values of n that in fact pass the test of having an exact solution, the last answer that was saved (not the last value of n that had a solution) is the correct answer, since you know by the theorem that any amount larger can also be bought in exact quantity
Problem 3.
Write an iterative program that finds the largest number of McNuggets that cannot be bought in exact quantity. Your program should print the answer in the following format (where the correct number is provided in place of <n>): “Largest number of McNuggets that cannot be bought in exact quantity: <n>”
Hint: your program should follow the outline above.
Hint: think about what information you need to keep track of as you loop through possible ways of buying exactly n McNuggets. This will guide you in deciding what state variables you will need to utilize.
and here's an example of a working one from someone else:Code:consecFound = 0 # confirmed amounts which can be purchased lastFail = 0 # last confirmed impossible amount while consecFound < 6: # operation to run until 'consecFound' is 6 for i in range(1, 50): # positive integers >= 50 already proven for a in range(0, i/9 + 1): # amounts of a > 8 will have value > 50 for b in range(0, i/6 + 1): # amounts of b > 5 will have value > 50 for c in range(0, i/3 + 1): # amounts of c > 2 will have value > 50 n = (6 * a) + (9 * b) + (20 * c) if n == i: # if i is solvable with given amounts, consecFound += 1 # increase 'consecFound' else: # otherwise, reset 'consecFound' to zero, and log last consecFound = 0 # known impossible amount lastFail = i print lastFail # output the last known impossible amount
The for loops for a/b/c I did not come up with, those seemed to be widely used in the answers I found posted, and I'm not exactly sure how they're working/supposed to work. I was trying to come up with a working code largely on my own without just putting exactly what someone else who already figured it out did, but I'm having a really hard time understanding what's keeping mine from working while the other example is.Code:foundInARow = 0 maxThatCannotBePurchased = 0 for i in range(0, 50): canPurchaseThisAmount = False for a in range(0, i / 6 + 1): for b in range(0, i / 9 + 1): for c in range(0, i / 20 + 1): solution = (6 * a) + (9 * b) + (20 * c) if solution == i: canPurchaseThisAmount = True if canPurchaseThisAmount: foundInARow += 1 if 6 == foundInARow: break; else: foundInARow = 0 maxThatCannotBePurchased = i print "Largest number of McNuggets that cannot be bought in exact quantity: %d" % maxThatCannotBePurchased
Been trying to debug it for a few hours now, I figure maybe a fresh set of eyes would help. Any pointers in the write direction, or ideally an english explanation of those for loops would be appreciated.