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
return 0
d = (n/x).to_i
cnt = 0
xc = coefficients.collect{|p| p} #must copy since we pop array
cnt += solve(n-x*y,xc)
return cnt

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


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).

Dylan Eales said...

Sample Assignment has a a Professional and Experienced project management assignment help Experts from Australia, UK and US. They are highly qualified and skilled professional writers who have vast experience in writing assignments, dissertations, essays, research Report  writing etc. Our writers meet all the requirements of students or those who search taxation assignment help guide them in a positive manner. They follow each and every instruction given by our customers.

Maria Garcia said...

After reading your blog, I came to know how these assignment help services are making the work easier for a large portion of students in the world. However, there is one such website who I personally prefer goes by the name of My Assignment Services. They are the indeed the problem solver whenever I took their Nursing assignment help Australia. They are the experts when it comes to do any assignment writing; be it essays of 200 words or even dissertations of 20000 words. The most surprising thing that I come across is that they are offering Nursing case study help at 25% discounted rates so as to make the students understand those complex case study assignments. That is why, my personal preference goes to My Assignment Services and their section of Nursing assignment help Australia.