Thursday, April 24, 2008

Diophantine Equation

Earlier today I solved Problem 31 on Project Euler. The problem is to find the number of ways of making change for 2 British pounds (or 200 pence) given 8 types of coins. For a mathematical person like myself, the problem reduces to a Diophantine Equation:

a + 2b + 5c + 10d + 20e + 50f + 100g + 200h = 200

Where 1,2,5,10,20,50,100,200 are the values of the various types of coins. I had some meetings to go to, so I wrote a brute force solution (in Ruby) and let it run. I got back an hour later, and it was still running. I felt quite stupid. I then came up with a much better solution using some dynamic programming and recursion. It ran in 0.23s. Here it is:


def solve(n,coefficients)
x = coefficients.pop
if (coefficients.length == 0)
if (n % x == 0)
return 1
else
return 0
end
else
d = (n/x).to_i
cnt = 0
0.upto(d){|y|
xc = coefficients.collect{|p| p} #must copy since we pop array
cnt += solve(n-x*y,xc)
}
return cnt
end
end

c = [1,2,5,10,20,50,100,200]
n = 200
puts solve(n,c)

5 comments:

Anonymous said...

Good algorithm! When your solution takes time to compile or execute, the only problem is that your algorithm to solve the problem is slow. Recursive algorithm must be made and use some functions that are predefined or available in the programming language that you are using to run the program faster. I prefer to use those advance programming language because hey have lots of available functions and you don't need to make your own function.

Anonymous said...

Nice post! good algorithm. It is more faster to run a program when you use recursive algorithm rather than a iterative algorithm or solution.

Unknown said...

Yes, an iterative solution usually has better performance than a recursive one. I welcome other folks to post their own solutions, in Ruby or any other programming language they like.

willr said...

My first cut Java solution:

int solve(int total, int[] coefs)
{
if (total == 0) return 1;
if (total < 0) return 0;

int num = 0;
for (int value : coefs)
{
num += solve(total - value, coefs);
}

return num;
}


I wasn't completely sure why you needed to manipulate the array of coefficients, except for perhaps an optimization.

Having said that, I don't know (with a capital K) that my solution above works.

Unknown said...

I don't think that solution works. I tried it for n=5 and c=[1,2], i.e. solutions to a + 2b = 5. It gave 8, but there are clearly only 3 solutions (1,2), (3,1), and (5,0).