[Tutor] Problem

[Danny Yoo]

On Sun, Aug 28, 2016 at 7:46 AM, shahan khan <shahankhan0 at gmail.com> wrote:
> Hello
> I'm teching myself Python using MIT opencourse ware. I'm a beginner and
> have some what knowledge of c and c++. I'm using Python version



> Here is my code:
[code cut]

Before showing code, try to express what you're trying to do in
English first.  That is, your explanation near the bottom:

>  I'm using for loops to give possible valutes to a,b and c and then using the equation (6*a)+(9*b)+(20*c) to determine possible values for a,b and c for
satisfying the equation.

... this should actually be presented because it's the most important
part!  The problem with code is that code just executes. Any
expectations we have about what that code does is a matter of human
interpretation.



Anyway, from looking at your original code (modulo indentation), I
*think* the treatment as a search problem, looking for the values of
the parameters a, b, c is reasonable, with the way you're doing nested
for loops,

>  for a in range(1,10):
>      for b in range(1,5):
>          for c in range(1,5):

However, I am not entirely convinced that the search bounds are
actually sound.  Here's why: I don't know why the numbers 1, 10, 5,
and 5 were chosen in the loop: they seem arbitrary, and you need to
say where those numbers came from.  I suspect there's a problem with
them anyway.


One concrete reason why I don't think it works: change the problem
slightly.  Say that we're trying to find a solution for the parameters
where the Diophantine equation evaluates to 6.  Basically, the really
simple edge case.

What change would you make to your code for this simpler case?  I'd
assume that the simplest thing to do would be to change the target
value in the test expression, from:

    if mc==50: ...

to

    if mc == 6: ...


Now, before we even try your program, we *know* there's a trivial
solution for a, b, and c such that the equation sums to six!

    a = 1
    b = 0
    c = 0

However, looking back at program structure, we can see, even without
looking at the rest of the code, that it can't possibly consider such
parameters, because it's assuming that all three variables have to be
positive.

So that's something that we know needs to be fixed in some way.



My take on the problem: this sounds very much like a question begging
for a dynamic programming approach, rather than a nested loop
approach.  The reason I say this is because of the part of the problem
statement:

###############################################################
Theorem: If it is possible to buy x, x+1,…, x+5 sets of McNuggets, for some
x, then it is possible to buy any number of McNuggets >= x, given that
McNuggets come in 6, 9 and 20 packs.
###############################################################

would be the beginning of a mathematical induction proof, which is the
scent of a dynamic programming problem.


I'd sketch this as follows: let's call M(n) a boolean function on the
natural numbers that's true if we can buy n McNuggets by *any*
combination of 6, 9, and 20 packs.

We know that:

    * M(6) is true
    * M(9) is true
    * M(20) is true

Why?  Because we can take a single 6-pack, or a single 9-pack, or a
single 20-pack, and each of these is a way to buy 6, 9, or 20
McNuggets.

>From that core collection of knowledge, that inductive base, we can
start investigating what else we can discover by building upon that
knowledge inductively.


Example: we know that since M(6) is true, that M(12) is true, because
we can include another 6-pack to the one that built up M(6).
Furthermore, we know that M(15) is true, because M(6) is true, and we
can include another 9-pack to the one that built up M(6).


What about M(50)?  Well, not quite sure.  However, I do know this: if
M(50) is true, then *at least one* of the following has to be true:

   a.  M(44) is true
   b.  M(41) is true
   c.  M(30) is true

How in the world would we know this?

Because if we were able to make 50 McNuggets out of a collection of 6,
9, or 20 packs, then we have to have picked one of those packs.  And
the remainder, outside of that pack, is where we get 44, 41, or 30.

We don't have absolute knowledge here: it's *conditional* because we
don't yet know if M(44), M(41), or M(30) is true.  But it's a start.

I don't want to say too much more about this.  The reason is because
if I state the idea just a little bit more formally, it suddenly looks
a heck of a lot like a direct problem solution.  But I hope that gives
you some ideas.

See: https://mail.python.org/pipermail/tutor/2016-July/109391.html for
some links to dynamic programming material.