Problem 031

[JPGargoyle]

Hi.

I've searched the forum from help on problem 31 and haven't find any so here it goes:

In combining the coins to get £2, the combinations (for example) £1, 50p, 2x20p, 10p and
10p, £1, 2x20p, 50p are considered two different solutions or are considered the same?

Thank you.

Best regards.

[stijn263]

they are the same

[JPGargoyle]

Thanks a lot stijn263.

That means I am doing some really stupid twist on my logic on an (apparently) simple problem.

I've reviewed it lots and lots of times and still haven't found what I am doing wrong.

Well. I think it's time to make another pause, and come back at it later he he.


Best regards.

[quilan]

If you're having difficulties with that particular problem, sometimes solving a related problem can help as well. For example problems 76-77, 114-117, you could potentially use many of the same techniques to start solving the problem. If you can figure out one of them, you can probably adapt your new methods onto the others.

[JPGargoyle]

Thank you quilan.

I was trying to do them all in a row. I guess I will have to start letting some to try later.

Best regards.

[dconrad]

Problem 31, making change for English money...

I solved this one a while ago. I was just writing an email to an old friend, and mentioned what I'd been up to lately. I quoted a few of the problems, just to give him a feel for what this site entails. I mentioned this problem.

Then, just for fun, I took my old code and ran it for some different target values. (Don't worry, I'll be careful not to give any spoilers.) My code (in Java) didn't do anything too clever. It just enumerated all the possibilities. Problem 31 calls for making change for two quid. I tried it with 5 quid (it runs in under a second). 10 quid (takes almost 5 seconds). 700 pence, 800 pence.

I was looking to see what it could do in 1 second. (1 second rule....) And I noticed something odd.

777 pence took a little over a second. 775 took a little MORE time. Consistently.

767 and 769 take a bit over a second. 768 takes around 0.8 seconds. 8/10 of a second. Consistently.

Weird. WEIRD!

The number of ways to make change is monotonically increasing with the amount of money. I cannot fathom why there should be "holes" that are easier/faster to calculate.

I suspect it may just be some odd thing with the JIT (the just-in-time compiler for Java that kicks in when a method or a loop is being run a lot, and compiles it down to native machine code). Maybe one pattern of execution is triggering the JIT sooner, or something. I can't imagine what else could explain it.

Okay, I just modified my code to do it 50 times in a loop to warm up the JIT, and then solve the problem 20 times and show the average time. First of all, they all got faster, which shows that "warming up" the code is important and microbenchmarks are tricky. (Both of which I knew, and should have been on guard against to begin with.) But:

767 pence, average time 0.365693071 seconds
768 pence, average time 0.340371754 seconds
769 pence, average time 0.372852044 seconds

Who can explain this? Why is 768 pence faster, when there are more combinations of coins than for 767 pence? Is it because of that tupenny? ("Feed the birds, tuppence a bag, tuppence, tuppence, tuppence a bag.") It somehow finds those even bundles of change more readily?

Hmm, the times creep up from 769 to 774, then drop a bit at 775. Up again at 776 and 777, but back down to 0.368 seconds at 778. (Yes, that's right, 778 is faster than 769, even though there're millions more solutions. WHY!?)

If anyone wants to see my code, PM me. If I see that you've solved Problem 31, I'll be happy to send it to you.

But, mostly, I'd just like to hear if anyone else sees similar odd, nonlinear patterns in the running time of their programs, for increasing quantities of pommy trinkgeld. Especially if their programs are written in compiled languages like asm or C where vagaries of JIT and GC don't apply (although my code allocates no memory in the loop), and their program enumerates all the solutions (whether it prints them or not), without trying any memoizing tricks.

And I'd really love it if anyone can explain what I'm seeing.

If any part of this is considered a spoiler, I'll edit it.

Thanks,
Dave Conrad

(Apologies if any poms were offended by "pommy trinkgeld", or if any Germans were made thirsty by it. It's all meant in good fun.)

[dconrad]

Well, I've been tweaking my code, including taking out the call to the method that would (optionally) print the solutions:

Code: Select all

public static final boolean DEBUG = false;

. . .

public static void note() {
    ++count;
    if (DEBUG) {
        // ... display the solution ...
    }
}

This method would both count and display the solutions, or just count them when DEBUG is false. After simplifying my code so that it just counts the solutions, I no longer see the effect. The times just monotonically increase with the amount.

This method could be called in two places, at different times. When there were several coins left to try, or when there were only pence left. I don't want to say more as it might be a spoiler. The modified code doesn't call this method at all; it just increments the counter. At any rate, I think that was behind the strange times I was seeing.

Cheers,
Dave Conrad

[kaddkaka]

I misunderstood this problem and made a solution counting the combinations if the available coins were: 1p, 2p, 3p, 4p, 5p, 6p, 7p, 8p, 9p, ..., 200p
At first it took such a long time that I didn't bother to wait (10+ min). I made a change and now it's very fast. It calculates the answer for 400p divided into coins in [1:400] in well under a second.

Maybe this could be a new problem, or is it too easy?
cheers!

PS. The solution for 1000|1000 takes about 2-3 seconds to calculate but the answer is too big to store in a 64 bit int.
PPS: 500|500 is too large.

[thelma]

I'm told that the answer i've submitted for this problem is wrong. My code succeeds on the few tiny cases where I've been able to count the results myself and compare with the program's answer. Can someone please suggest what I can do to try to correct this?

The question seems completely straightforward, but could I yet be trying to answer the wrong question? [I tried the same code, with the same negative result, for problem 076]

[TripleM]

If you want to PM me your small results, I can clarify whether you're solving the right problem or not.