TR Forums

Wed May 19, 2004 5:09 pm

Popular request [okay, just Yahoolian] has prompted me to post this question, which was from a competition I participated in.

I got it working at the competition, but when I entered it, it was rejected on the premise that it took to long to return a result.

Here is my original program
Here is the revised version.
This is the third and current version.

To run, you may want to place this file, dollars.txt, in the same directory.

I'm not going to post the source, as it's really space-consuming. It's available via links provided. I think right click+ save as will be most efficient.

I ran it on my computer. Small values work fine. Arbitrarily I chose $55.75 as a test value. It completed in 3:57 (min:sec), returning a correct value of 1004770130.

I set to work revising it. My first revision eliminates the total(int) call in each loop. Rather, it uses an int that is updated before and after each nested for loop.

This version completes in 2:07, correctly again. Still way too long.

SO, I changed the arrays of values to individual ints.

It runs correctly, and takes 1:27.

I don't believe this is fast enough, but do not know where to move. I thought there would be some sort of combination/permutation algorithm to give me instantaneous results, but have not been able to come up with it.

Even a more efficient counting method escapes me. For example, every time .20 is part of a combination, I can also count a combination with 2 .10's, one with 2 .05's and a .10, and one with 4 .05's. I know this could work, but nothing clicks as far as implementation, especially when counting beyond a simple denomination.

SO, codemasters, my challenge to you is to help me optimize the program to run better. My goal is under 5 seconds, if possible. However, I believe that a counting principle such as outlined above can run in real time. Oh, and if possible, if you supply code, if you provide reasons for the code as well.

Thank you thank you thank you.

Hawkwing74 · Wed May 19, 2004 5:16 pm

My knowledge of the subject is peripheral at best, but I'm curious. If you're going for speed why use a class? I would think constructing the class object would take some time. Or does Java require a class?

Wed May 19, 2004 5:50 pm

Hawkwing74 wrote:
My knowledge of the subject is peripheral at best, but I'm curious. If you're going for speed why use a class? I would think constructing the class object would take some time. Or does Java require a class?

Well, there has to be at least one class, in which public static void main() lies. It isn't relevant in this case, 'cause it is accessed only 3 times per value in dollars.txt. All of the work in the program is done in the numCrunch() method of the MoneyList class.

UberGerbil · Wed May 19, 2004 6:40 pm

Does it have to be in Java?

Wed May 19, 2004 7:02 pm

UberGerbil wrote:
Does it have to be in Java?

Well, the competition is over. It doesn't even have to be done. I'd just like the practice, learning things along the way.

If you have something else in mind, you can write out pseudocode and I'll change it to java. You can even write it in another [hopefully OO] language (C++) and I can change it.

Hawkwing, I realized that the cash integer wasn't passed to the numCrunch method, so I added another minor method to pass the value. Thx for the comment, it shaved 2 seconds off the processing time!

Wed May 19, 2004 7:42 pm

Update for anyone looking at the code over the past hour:

Yahoolian and I have been working on it for a bit, and by removing that nested if statement, I got it to run, correctly, in 38 secs.

Still not at the speed I'd like. At this point, I'm still just optimizing a brute force method. It can be better!

Wed May 19, 2004 7:59 pm

'nother update:

by modifying that last for loop to:

for(j=0;j<=((cash-money)/10);j++)
{
//        money+=(10*j);
//        k=((cash-money)/5);
//        if(total()==cash)
          numTimes++;
//        money-=(10*j);
}

It's now down to :21. I think that's the best we're gonna get with the modified brute-force. Time to put on the bigger thinking caps to get some algorithms a-flowin!

Hawkwing74 · Thu May 20, 2004 12:02 am

It would be curious to port the code to C++ (wouldn't be that different) and see if the time is quicker or slower. C++ of course doesn't require a class.

Thu May 20, 2004 1:23 am

Caching is the answer. Whenever you compute the number of combinations for a given dollar value and maximum denomination, cache the result and reuse it on subsequent sub-iterations.

<a href="http://justbrewit.net/trstuff/money.cpp">This version</a> computes the result for your $55.75 test input in ~50 milliseconds on an Athlon XP 2100+.

And yeah, it's C/C++ instead of Java, and I didn't use classes, and I used recursion instead of an inner loop... but that's not what makes the difference. The caching is the key. (I tried a straight brute-force approach in C++, and it took for-freaking-ever to run.)

I used a double for the counter because for the maximum input value ($300.00), the result exceeds a 32-bit int.

Edit: I actually didn't hit the "aha!" moment on this puzzle until I started drinking. I'm not exactly certain how I feel about that; is it a commentary on the puzzle... or on me? :lol:

Earlier in the day -- while hopped up on caffeine instead of alcohol -- I had the idea of using a recursive partitioning algorithm (no caching), which turned out to be a complete red herring -- yeah, it ran fast, but I couldn't get it to produce correct results! :-?

Edit edit: Hope the recursion didn't obfuscate things too much; it's just the way I tend to conceptualize problems like this. Recursion actually tends to be slightly less efficient than a nested loop implementation, but in some cases (like this one) I find it easier to follow.

Thu May 20, 2004 10:49 am

Just a few additional notes on my version... might help you convert it to Java...

Rather than using the nested loops, it decomposes the problem using recursion -- divide and conquer. The algorithm computes the number of combinations associated with each branch of the search tree by subtracting off the value of the current coin, and calling itself recursively for each sub-branch. I think organizing it this way also makes the caching algorithm easier to understand.

The key to the caching algorithm is the realization that in the brute force approach, the same computations are repeated many, many times. E.g., for any large initial amount, we will -- at some level -- be asking the question "How many ways can I make change for $1 using only 50 cent or smaller coins?" thousands (maybe even millions) of times. The cache array guarantees that that computation -- and every other possible "How do I make change for x using only y or smaller coins?" sub-computation -- is done once, and only once. This improves the efficiency of the brute force approach by many orders of magnitude (at the cost of a couple of megabytes of additional RAM to store the cache array).

I am certain there is a way to compute it combinatorically as well (i.e., the "elegant" approach you were looking for). But the reference material I was able to find via Google (like <a href="http://home.att.net/~numericana/answer/counting.htm#uschange">this page</a>) made my brain hurt! :lol:

After staring at that page (and a couple of others like it) for a while, I decided to give up on the combinatorics (which was never one of my strong subjects anyway), have a couple of beers, and have another go at improving the efficiency of the "brute force" algorithm. :wink:

Cheers!

Thu May 20, 2004 12:16 pm

Further improvements <a href="http://justbrewit.net/trstuff/money2.cpp">here</a>.

Eliminated the loop to initialize the cache (not needed since the C++ compiler fills static arrays with zeros), and got rid of the calculation loop too (all of the heavy lifting is done via recursion now). The entire core algorithm (including the cache management) has been condensed down to 9 lines of code. It takes about 30 milliseconds to execute your test case.

This was really fun! :lol:

(Damn, I'm such a hopeless geek... :roll:

)

Edit: Minor tweak to improve code readability.

Hawkwing74 · Thu May 20, 2004 1:02 pm

just brew it! wrote:
It takes about 30 milliseconds to execute your test case.

Amazing

you should teach advanced C++ or something. (of course they don't make any money I suppose)

moog · Thu May 20, 2004 1:25 pm

just brew it! wrote:
"How many ways can I make change for $1 using only 50 cent or smaller coins?" thousands (maybe even millions) of times. The cache array guarantees that that computation -- and every other possible "How do I make change for x using only y or smaller coins?" sub-computation -- is done once, and only once. This improves the efficiency of the brute force approach by many orders of magnitude (at the cost of a couple of megabytes of additional RAM to store the cache array).

Nice way to do it.

Yahoolian · Thu May 20, 2004 2:09 pm

I can see that JBI like the tertiary operator... (So do I.)

I ported it to java.

import java.io.*;
import java.util.*;

class Money{
  public static final int MAX_CENTS = 30000;
  static final int values[] = { 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 0 };
  static final long cache[][] = new long[ values.length ][ MAX_CENTS + 1 ];
   
  public static void main (String []args){
    long beginTime = System.currentTimeMillis();
    try {
      BufferedReader in = new BufferedReader (new FileReader ("D:\\Money\\src\\dollars.txt"));
      String s = in.readLine();
      while (s != null)
      {
        int cents = (int)(Double.parseDouble( s ) * 100);
        System.out.println( s + "\t" + maxWaysToMake( 0, cents ) );
        s = in.readLine();
      }

    } catch (Exception e) {
      System.out.println(e);
    }
    System.out.println( "Elapsed milliseconds: " + ( System.currentTimeMillis() - beginTime ) );

  }
   
  public static long maxWaysToMake(int start, int target)
  {
    // Check for trivial terminal conditions and compute value if needed
    if (values[start] == 0)
      return 0;
    else if (target == 0)
      return 1;
   
    else if (cache[start][target] != 0)
        return cache[start][target];
   
    else
      return (cache[start][target] = ((values[start] <= target)
        ? maxWaysToMake(start, target - values[start]) : 0)
          + maxWaysToMake(start + 1, target));
  }
 
}

edit1: removed one of the tertiary operators for code clarity, following in JBI's foosteps.

edit2: added timing, fixed bug where overflow would occur at higher values of cents.

edit3: put back edit1.

edit4: fix time calculation

edit5: fixed rounding error, thanks mac_h8r1!

Thu May 20, 2004 2:16 pm

Hawkwing74 wrote:
Amazing you should teach advanced C++ or something. (of course they don't make any money I suppose)

Thanks... that's really more of a C program than a C++ one though. While I'm reasonably good at C++, I don't really consider myself an expert on the language.

And no, I don't think programming instructors make much money...

moog wrote:
Nice way to do it.

Thanks... the breakthrough was realizing that there was a lot of redundant calculation going on, and figuring a way to avoid doing any given piece of work twice.

Yahoolian wrote:
I can see that JBI like the tertiary operator... (So do I.)

Heh... I actually took one of 'em out (turned it back into a normal 'if') a few minutes ago, to improve readability. :wink:

I ported it to java.

So how's the performance of the Java version?

Hawkwing74 · Thu May 20, 2004 2:16 pm

And the results???

Thu May 20, 2004 2:32 pm

BTW Yahoolian... if Java 'int' data type is 32 bit signed, the program will fail for input values greater than 62... that's why I used doubles in the C++ version.

Yahoolian · Thu May 20, 2004 2:38 pm

Performance seems to be comparable. It says 0 milliseconds elapsed, when I add

long beginTime = System.currentTimeMillis();

at the beginning of main and

System.out.println( "Elapsed milliseconds: " + ( System.currentTimeMillis() - beginTime ) );

after main, it says 0 for an input of 55.75.

From my limited testing, results are the same.

Thu May 20, 2004 2:43 pm

Yahoolian wrote:
Performance seems to be comparable. It says 0 milliseconds elapsed, when I add
Code: Select all
long beginTime = System.currentTimeMillis();
at the beginning of main and
Code: Select all
System.out.println( "Elapsed milliseconds: " + (beginTime - System.currentTimeMillis()) );
after main, it says 0.

From my limited testing, results are the same.

So the algorithm takes less time to execute than the granularity of your system's time-of-day clock. Cool!

Come to think of it, when I reported my 30ms time, I was using the Linux (well actually Cygwin) 'time' command to clock execution of the program... so that 30ms figure actually includes program load time!

Yahoolian · Thu May 20, 2004 2:59 pm

So the algorithm takes less time to execute than the granularity of your system's time-of-day clock. Cool!

Come to think of it, when I reported my 30ms time, I was using the Linux (well actually Cygwin) 'time' command to clock execution of the program... so that 30ms figure actually includes program load time!

That would explain it. I'd doubt that Java is faster than C++/C, because it does bounds checking on all array lookups.

BTW Yahoolian... if Java 'int' data type is 32 bit signed, the program will fail for input values greater than 62... that's why I used doubles in the C++ version.

Well I noticed that it was overflowing when I tried an input of 200, thanks for the heads-up. I changed it to longs, that solves it.

Thu May 20, 2004 2:59 pm

Yahoolian wrote:
From my limited testing, results are the same.

I'm pretty confident that the algorithm is sound. Since it's recursive, verifying that it gives correct results for a single large input value (like 55.75) implicitly tests it for all smaller input values as well.

The other cute thing about this version is that you can change the denominations of currency used in the simulation just by changing the values in the array -- the code is completely generic. E.g, if you want to include pennies, all you need to do is add a 1 to the array between the 5 and the 0...

Yahoolian · Thu May 20, 2004 3:03 pm

The other cute thing about this version is that you can change the denominations of currency used in the simulation just by changing the values in the array -- the code is completely generic. E.g, if you want to include pennies, all you need to do is add a 1 to the array between the 5 and the 0...

Well you'd also have to change the 11 to a 12 in the line below. A nice feature of java is that arrays know their length.

static double cache[11][MAX_CENTS + 1];

Thu May 20, 2004 3:10 pm

Yahoolian wrote:
Well you'd also have to change the 11 to a 12 in the line below. A nice feature of java is that arrays know their length.
Code: Select all
static double cache[11][MAX_CENTS + 1];

I've changed it to:

static double cache[sizeof(values) / sizeof(values[0])][MAX_CENTS + 1];

Not quite as clean as Java, but the end result is the same. :wink:

Edit: Jeez, code reviews on a forum thread... how geeky can you get? :lol:

Thu May 20, 2004 5:06 pm

Wow, you guys are good. The only thing I don't understand about the code is

else 
      return (cache[start][target] = ((values[start] <= target) 
        ? maxWaysToMake(start, target - values[start]) : 0) 
          + maxWaysToMake(start + 1, target));

mainly the ?...: part. I assume it sets the value in cache[][] and something else [?]

Thu May 20, 2004 5:23 pm

It's the C/C++/Java "conditional expression" operator. In an expression of the form:

A ? B : C

A is evaluated first; if it is non-zero (true) then B is evaluated; otherwise C is evaluated. Whichever of B or C gets evaluated becomes the final value of the entire expression.

Edit: That one convoluted expression is basically the guts of the optimized algorithm. It essentially says, "If the amount we're currently trying to make change for is equal to or greater than the denomination we're currently dealing with, then figure out how many ways there are to make change for the remaining amount after we subtract that denomination, and how many ways there are to make change for the current denomination using smaller ones. Otherwise, try again starting with the next smaller denomination." Or something like that. It's kind of hard to express recursive algorithms in English. :wink:

IntelMole · Thu May 20, 2004 9:37 pm

JBI, maybe I'm being an idiot wrt your c++ source.

But here goes:

It doesn't do anything. I've compiled the program on Bloodshed Dev C++, and run it in an MS DOS window, but it doesn't bring anything up on screen, and doesn't create any files...

Like I said, I'm probably being a retard somehow...
-Mole

Yahoolian · Thu May 20, 2004 9:39 pm

It doesn't do anything. I've compiled the program on Bloodshed Dev C++, and run it in an MS DOS window, but it doesn't bring anything up on screen, and doesn't create any files...

It's supposed to read a file called dollars.txt, which contains the input(s).

IntelMole · Thu May 20, 2004 9:45 pm

Cheers yahoolian, I should learn to read code better.

Not that it was badly written or anything, far from it :-D

,
-Mole

Thu May 20, 2004 9:48 pm

Yahoolian wrote:
It's supposed to read a file called dollars.txt, which contains the input(s).

Yup. Please refer to the original specs for the program that mac_h8r1 posted at the start of the thread... :wink:

MorgZ · Fri May 21, 2004 5:33 am

wats the quickest java implementation?

Im tempted to give it a go since im pretty nifty at speedy algorithsm

TR Forums

Program optimization?

Program optimization?

Who is online