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

About these ads