[Tutor] Euler Spoiler

[Danny Yoo]

To be concrete, I think you're looking at Problem 31, right?

    http://projecteuler.net/problem=31

in which case, we have a few choices for denomination:

    1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p

and we're trying to _count_ how many ways to make 200p.



Here's a sketch of how I'd attack this by considering a DP-style
approach.  If you want to avoid any spoilers, please skip this
message.

Otherwise, I'll try to be as transparent as to my thought process as I can.

-----------------------------------------------------------------------

We first want to "name and conquer".

Let C(k) be the number of ways to make change for 'k' pence.

Why C(k)?  Because I think C(200) is what we're looking for.  I'm
making 'k' be the parameter here because I think an approach that
tries to figure out C, where n ranges from [0-200], should do the
trick.


Note: for now, let's assume that C does not remember _how_ we're
making the change.  It should only remember the number of ways to do
so.



What are some values for C?  Let us try to reason what C must be for
low values of 'k'.

------

C(0) = 1.  There's one way to make change for zero pence, namely the
empty case.  It might be important to argue this edge case, so that's
why I'm considering it.

------

C(1) = 1.  We know we can do this one trivially.

    1p

------

C(2) = 2.  We can either do it as:

    1p + 1p, or
    2p

------

C(3) = 2.  We can do it as:

    2p + 1p, or
    1p + 1p + 1p.



Note: we don't want to treat:

    1p + 2p

as another possibility!

Why not?  Because that would be a duplicate of

    2p + 1p

which we already counted for already.

Believe it or not, this observation is important, because we'll find
in a few moments that it forces us to reconsider an amendment to our
approach.

-----------------------------------------------


One observation so far: it looks like we can construct more of C by
looking at previous elements of C.  That would mean we just run
through constructing C "bottom-up", from k=1 through 200.  If that's
the case, then we're golden.  We can just keep the intermediate values
of C as an array of ints.

Easy.

Or not.  :P  Let's see what happens.


------

C(4) = ...?

This is starting not to be so obvious.

Let's try to reason it out.  From our observation, let's see if we can
just take previous elements that we computed for C and just sum it up
in some nice way.

If we're trying to make change for four pence, then...

1.  If there's a change-making sequence that starts of as:

    "2p + ...",

for example, the "..." would stand for ways of making change for the
remainder 4p - 2p == 2p.

Looking back at how we computed C(2), we could make C(2) out of:

    1p + 1p, or
    2p

So if we just put "2p" in front of those, that gives us:

    2p + 1p + 1p, or
    2p + 2p.

Good!


2.  If there's a change-making sequence that starts off as "1p + ...",
for example, the "..." would stand for the ways of making change for
the remainder 4p - 1p == 3p.

Looking back at how we computed C(3), we know that it was constructed out of:

    2p + 1p, or
    1p + 1p + 1p.

So maybe we can just put 1p in front of those!

    1p + ... <ways of making C(3)>

    ==>

    1p + 2p + 1p, or
    1p + 1p + 1p + 1p.


... Oh!  But wait, we don't want to count:

    1p + 2p + 1p

because we already did that, essentially, when we did

    2p + 1p + 1p

In fact, we ran into this issue earlier on when we were trying to
figure out C(3).


So C(4) is 3, because we can make it out of:

    2p + 1p + 1p, or
    2p + 2p, or
    1p + 1p + 1p + 1p.

---

Huh.  That wasn't as simple as just adding up previous values for C.  Nuts.


Let's think about this a bit.  Earlier, we were hoping we could just
naively look at C for previous values of k, and just add them up.  But
we want to make sure we DON'T over-count ways of making the change.


The difficulty that we're running across is due to the structure of C:
it doesn't let us know if we're counting a change-making that already
takes into consideration something we already counted.

What to do?

Maybe our earlier approach, to not remember how exactly we're making
the change, can be amended.

One approach might be to change the return type of C.  Rather than
have it keep track of just the number of ways of counting change, we
might instead hold onto a description of the change sums themselves.
This should work!  But it would mean that we have to hold a list of
list of denominations.  And we'd have to do an additional
duplication-filtering step.  But we know we can do it this way, if we
really needed to.



But there is another approach.  I will sketch this approach out
because I'm pretty sure it's the one the problem writers intended.

Let's look again at that troublesome change-making that's causing us grief:

    1p + 2p + 1p

We don't want this because it's a duplicate of:

    2p + 1p + 1p

Well, what's different about it?  The numbers are in a different
order.  The case we don't care particularly for, 1p + 2p + 1p, have
numbers in a "mixed up" order.

Crazy idea: how about we force it so we're only consider
"nonincreasing" configurations?

Maybe we can amend things so we don't consider 1p + 2p + 1p.  What
made us consider this in the first place?  Well, we were trying to
figure out C(4).  We took 1p out, and then started looking at how we
figured out C(3).  But we know we don't want to look at 2p+1p here: we
took 1p out, so anything that uses anything bigger than 1p would have
already been counted earlier!


So how about we add an additional parameter to C?  Name and conquer!


We revise the type of C so it takes in two arguments.  Let C(k, d) be
the number of ways of making change for k pence, when d is the highest
denomination to be used in making that change.


For example, consider C(k, 1).  If we're only allowed to use one pence
to make change, then there's only one way to make change for k pence:
by using only single pences.

    C(k, 1) = 1               for all k.


How does adding this 'd' parameter help us?  Well, if we're trying to
figure out all the ways of making change for 4 pence, and we start off
asking out to make:

    1p + ...,

we can just use the answer from C(3, 1).

That fixes the problem of considering 1p + 2p + 1p: we eliminate that
case by filtering it out via using appropriately small denominations
'd' for the remainder.


-------

More generally, how do we compute C(k, d)?

We can sum up

   C(k - c, c)

for all candidate coins c that are smaller than or equal to d.

------

Let's look at how that'd work for C(4, 2), the case that we were
having difficulty before.  We have two candidate coins we get to use
here, 1p, and 2p.

Let's say we start off using 1p.  Then we want:

        C(4-1, 1)
    -> C(3, 1)

which asks: how many ways to make change out for 3p, when we're only
allowed to us single pence.  And we know this already.  C(3, 1) = 1,
due to reasoning out what C(k, 1) means for any k.


Ok, what if we start with 2p?  Then we want:

        C(4-2, 2)
    -> C(2, 2)

How many ways can we make change for 2 pence, if we're allowed to use
as high a denomination as 2p?  We know this already as well: we did
this when working out the original C(2), when we weren't thinking of
the second argument 'd'.  C(2) = 2.


That is, we now know that:

    C(4, 2) = C(3, 1) + C(2, 2)
               = 1 + 2
               = 3
-----


And that's really a way we can nail this problem.  Once you understand
what's happening, the code to compute the solution to Euler Problem 31
ends up being only a few lines long!  Not only that, but the concepts
the code uses is nothing more complicated than a 2d array and a few
loops.  No power sets, no itertools, just some basic fundamental
types.

It's astonishingly "simple-looking" code, even if the reasons why the
code works is non-obvious.



Apologies for the length of the post.  But hopefully it helps a little.