When I heard from my friend about the new programming praxis problem I started thinking how to implement the solution. I wrote down the numbers from 1 to 20 and made the following observation:
if S is a McNugget number it’s either trivial (zero) or you can represent it as a sum K+M where K is a smaller McNugget and M is one of: 6, 9 or 20.
Well, this looked like a recipe for a very simple case of dynamic programming. In fact it’s enough to keep track of the status of 20 previous numbers and using no more than 3 operations you can find if the current one is a McNugget. But where should I stop?
Intuitively I knew there was a constant above which all numbers were McNuggets. Unfortunately I did not remember my discrete math lectures that well to prove it. But I made another observation:
Once 6 numbers in a row are McNugget numbers, you can represent any greater one by adding as many “6″ as needed.
This gave me the stop condition. I put together Python code (below) – note it actually uses more memory than necessary. Then I wrote the C version – more effective because of using just a 20-element array. Unfortunately the source code was even longer and rather unreadable. And that’s the story.
known = [ 0 ]
i = 1
consecutive_success = 0
while True:
if i - 6 in known or i - 9 in known or i - 20 in known:
known.append(i)
consecutive_success += 1
if consecutive_success == 6:
print "All numbers >= %d are mcnugget" % (i - 5)
break
else:
print i
consecutive_success = 0
i += 1
