I'm glad my programming classes are in object pascal at the moment... that C++ code looks like it would make my brain melt
of course, half the problem is not knowing how to mathematically solve the initial problem in the first place =)
Personal computing discussed
Moderators: renee, SecretSquirrel, just brew it!
MorgZ wrote:wats the quickest java implementation?
Im tempted to give it a go since im pretty nifty at speedy algorithsm
blitzy wrote:I'm glad my programming classes are in object pascal at the moment... that C++ code looks like it would make my brain melt
of course, half the problem is not knowing how to mathematically solve the initial problem in the first place =)
just brew it! wrote:My family probably thought I was on drugs or something a couple of nights ago during dinner -- I was trying to work through potential algorithms in my head, and must've seemed like I was on another planet.
mac_h8r1 wrote:Yahoolian, 928131635 is the value I get when I run your program for 55.75. Any thoughts?
JBI, Glad to keep you on your toes!
So, considering that this was one problem of 9, who thinks that, working with two others, they could win a competition given 4.5 hours?
This was not the most difficult, btw . I posted this one 'cause it was the only one I worked on that didn't get accepted. There may be another that I post, as I'm COMPLETELY in the dark regarding that one.
mac_h8r1 wrote:Yahoolian, 928131635 is the value I get when I run your program for 55.75. Any thoughts?
Yahoolian wrote:That would explain it. I'd doubt that Java is faster than C++/C, because it does bounds checking on all array lookups.
MorgZ wrote:wats the quickest java implementation?
Im tempted to give it a go since im pretty nifty at speedy algorithsm
But in an iterative implementation, it probably wouldn't be too hard to convince the JVM that array bounds checks are unnecessary.
Assuming, of course, that your JVM contains a just-in-time compiler.
Did you just copy-paste his code, or could it be a transcription error?
int cents = (int)Double.parseDouble( s ) * 100;
int cents = (int)(Double.parseDouble( s ) * 100);
JustBrewIt wrote:Seriously... if you actually want to get a job programming, C++, Java, or even specialized (but "real world") languages like Transact-SQL are more marketable skills than Object Pascal (which is used commercially to some extent, but not much). Pascal is great for teaching general algorithm and data structure concepts though; that's why it is used a lot in programming classes.
blitzy wrote:anyone care to show how the program works through pseudocode? It's quite an interesting problem
This algorithim recursively calculates the number of unique ways to
make change for a given amount of money, using coins of specified
denominations. Inputs are the list of denominations to be used, and
the value to make change for. All values are in cents.
If list of denominations to use is empty, then
the result is 0.
Else if amount to make change for is 0, then
the result is 1.
Else if we've already calculated a value for this list of denominations and
amount of money, then
the result is the value calculated previously (retrieve from 2D
array indexed by the largest denomination of coin currently in the
list, and amount we're making change for).
Else if the largest denomination in the list is less than or equal to
the amount we're making change for, then
subtract the largest denomination from the amount we're
making change for, and recursively calculate how many ways we can
make change for the remaining amount, using the same list of denominations.
Also recursively calculate the number of ways we can make change for the
total amount, using only denominations smaller than the largest one.
The sum of these two values is the result.
Else
recursively try again using the total amount, but only considering denominations
smaller than the largest one currently in the list.
If we calculated a new value, save it in a 2D array indexed by the largest
denomination in the list of coins, and the amount we're making change for.
if (cache[start][target] != 0)
return cache[start][target];
import java.io.*;
import java.util.*;
class Money{
public static final int MAX_CENTS = 30000;
final static int value[] = { 0, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
static long cache[][] = new long[ value.length ][ MAX_CENTS + 1 ];
static final String filePath = "D:\\Money\\src\\";
public static void main ( final String []args)
{
long beginTime = System.currentTimeMillis();
try {
BufferedReader file = new BufferedReader (new FileReader (filePath + "dollars.txt") );
String s = file.readLine();
while (s != null)
{
int cents = (int)(Double.parseDouble( s ) * 100);
System.out.println( s + "\t" + maxWaysToMake( cents ) );
s = file.readLine();
}
} catch (Exception e) {
System.out.println(e);
}
System.out.println( "Elapsed milliseconds: " + ( System.currentTimeMillis() - beginTime ) );
}
public static long maxWaysToMake( final int cents )
{
int start = value.length - 1;
while ( value[start] > cents )
start--;
return maxWaysToMake( start, cents );
}
public static long maxWaysToMake( int start, final int cents)
{
// System.out.println( "\ncall: " + ++call + "\nstart: " + start + "\ntarget: " + target);
// if value already computed, return previously computed value
// doing this first results in a huge speed up
if (cache[start][cents] != 0)
return cache[start][cents];
// check for trivial terminal conditions
else if (start == 0)
return 0;
else if (cents == 0)
return 1;
else if (value[start] <= cents)
cache[start][cents] = maxWaysToMake(start, cents - value[start]);
cache[start][cents] += maxWaysToMake(start - 1, cents);
return cache[start][cents];
}
}
Yahoolian wrote:Oh yeah, I forgot to add that I moved theCode: Select allif (cache[start][target] != 0)
return cache[start][target];
lines to the front of the function, that makes it go from 16 milliseconds to 0 on my computer( AXP 2500+ @ 200 * 10.5 ).
Interesting... I would not have expected that. The only other two tests ahead of it were simple tests for values being equal to 0, which should be nearly instantaneous in the grand scheme of things.
I suspect that this may be a peculiarity of the Java compiler, or within the margin of error of the timing routine used.
Yahoolian wrote:Well for the input of 55.75 the function is called 4939 times, and 1348 times when the value is cached, I guess those two less comparisions and one less array lookup add up quite a bit.