Euler31

[Randall Twede]

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

i cant see why i am getting the wrong answer

class Euler31 implements Problem
{
	public String solve()
	{
		final int pence = 200;
		int answer = 1;
		
		for(int i = pence; i >= 2;)
		{
			i = i - 2;
			answer++;
		}
		for(int i = pence; i >= 5;)
		{
			i = i - 5;
			answer++;
		}
		for(int i = pence; i >= 10;)
		{
			i = i - 10;
			answer++;
		}
		for(int i = pence; i >= 20;)
		{
			i = i - 20;
			answer++;
		}
		for(int i = pence; i >= 50;)
		{
			i = i - 50;
			answer++;
		}
		for(int i = pence; i >= 100;)
		{
			i = i - 100;
			answer++;
		}
		for(int i = pence; i >= 200;)
		{
			i = i - 200;
			answer++;
		}
		return Integer.toString(answer);
	}
	
	public String getMessage()
	{
		return "How many different ways can £2 be made using any number of coins?";
	}
}

i get 178 for the answer. i wouldn't be surprised if it was off by 1

[Randall Twede]

ohhh...i think i see the problem. it is not as simple as i first thought. any hints?

[Tim Moores]

The code I wrote for this a few years back found 73682 different ways. I've no idea if it's correct, though :-)

[Randall Twede]

well, i thought i was on to it. my new answer is 462
but it is still incorrect
am i at least on the right track?

class Euler31 implements Problem
{
	public String solve()
	{
		final int pence = 200;
		int answer = 1;
		
		for(int i = pence; i >= 2;)
		{
			i = i - 2;
			answer++;
		}
		for(int i = pence; i >= 5;)
		{
			for(int j = 5; j >= 2; j -= 2)
			{
				answer++;
			}
			i = i - 5;
			answer++;
		}
		for(int i = pence; i >= 10;)
		{
			for(int j = 10; j >= 5; j -= 5)
			{
				answer++;
			}
			for(int j = 5; j >= 2; j -= 2)
			{
				answer++;
			}
			i = i - 10;
			answer++;
		}
		for(int i = pence; i >= 20;)
		{
			for(int j = 20; j >= 10; j -= 10)
			{
				answer++;
			}
			for(int j = 10; j >= 5; j -= 5)
			{
				answer++;
			}
			for(int j = 5; j >= 2; j -= 2)
			{
				answer++;
			}
			i = i - 20;
			answer++;
		}
		for(int i = pence; i >= 50;)
		{
			for(int j = 50; j >= 20; j -= 20)
			{
				answer++;
			}
			for(int j = 20; j >= 10; j -= 10)
			{
				answer++;
			}
			for(int j = 10; j >= 5; j -= 5)
			{
				answer++;
			}
			for(int j = 5; j >= 2; j -= 2)
			{
				answer++;
			}
			i = i - 50;
			answer++;
		}
		for(int i = pence; i >= 100;)
		{
			for(int j = 100; j >= 50; j -= 50)
			{
				answer++;
			}
			for(int j = 50; j >= 20; j -= 20)
			{
				answer++;
			}
			for(int j = 20; j >= 10; j -= 10)
			{
				answer++;
			}
			for(int j = 10; j >= 5; j -= 5)
			{
				answer++;
			}
			for(int j = 5; j >= 2; j -= 2)
			{
				answer++;
			}
			i = i - 100;
			answer++;
		}
		for(int i = pence; i >= 200;)
		{
			for(int j = 200; j >= 100; j -= 100)
			{
				answer++;
			}
			for(int j = 100; j >= 50; j -= 50)
			{
				answer++;
			}
			for(int j = 50; j >= 20; j -= 20)
			{
				answer++;
			}
			for(int j = 20; j >= 10; j -= 10)
			{
				answer++;
			}
			for(int j = 10; j >= 5; j -= 5)
			{
				answer++;
			}
			for(int j = 5; j >= 2; j -= 2)
			{
				answer++;
			}
			i = i - 200;
			answer++;
		}
		return Integer.toString(answer);
	}
	
	public String getMessage()
	{
		return "How many different ways can £2 be made using any number of coins?";
	}
}

[Randall Twede]

i think i have figured it out. just had to think about it longer

[Tim Moores]

My solution ended up having 8 nested loops. It also had a variable like this: int numCoins[] = new int[] { 0, 0, 0, 0, 0, 0, 0, 0 }

[Randall Twede]

thanks Tim,
my approach doesn't seem to be working

class Euler31 implements Problem
{
	public String solve()
	{
		final int pence = 200;
		int answer = 1;
		
		for(int i = pence; i >= 2;)
		{
			i = i - 2;
			answer++;
		}
		for(int i = pence; i >= 5;)
		{
			i = i - 5;
			answer++;
			for(int j = i; j >= 2; j -= 2)
			{
				answer++;
			}

		}
		for(int i = pence; i >= 10;)
		{
			i = i - 10;
			answer++;
			for(int j = i; j >= 5; j -= 5)
			{
				answer++;
			}
			for(int j = i; j >= 2; j -= 2)
			{
				answer++;
			}
		}
		for(int i = pence; i >= 20;)
		{
			i = i - 20;
			answer++;
			for(int j = i; j >= 10; j -= 10)
			{
				answer++;
			}
			for(int j = i; j >= 5; j -= 5)
			{
				answer++;
			}
			for(int j = i; j >= 2; j -= 2)
			{
				answer++;
			}
		}
		for(int i = pence; i >= 50;)
		{
			i = i - 50;
			answer++;
			for(int j = i; j >= 20; j -= 20)
			{
				answer++;
			}
			for(int j = i; j >= 10; j -= 10)
			{
				answer++;
			}
			for(int j = i; j >= 5; j -= 5)
			{
				answer++;
			}
			for(int j = i; j >= 2; j -= 2)
			{
				answer++;
			}
		}
		for(int i = pence; i >= 100;)
		{
			i = i - 100;
			answer++;
			for(int j = i; j >= 50; j -= 50)
			{
				answer++;
			}
			for(int j = i; j >= 20; j -= 20)
			{
				answer++;
			}
			for(int j = i; j >= 10; j -= 10)
			{
				answer++;
			}
			for(int j = i; j >= 5; j -= 5)
			{
				answer++;
			}
			for(int j = i; j >= 2; j -= 2)
			{
				answer++;
			}
		}
		answer++;
		return Integer.toString(answer);
	}
	
	public String getMessage()
	{
		return "How many different ways can £2 be made using any number of coins?";
	}
}

gives answer 4509 which is incorrect

[Matthew Brown]

Tim Moores wrote:My solution ended up having 8 nested loops. It also had a variable like this: int numCoins[] = new int[] { 0, 0, 0, 0, 0, 0, 0, 0 }

My solution used a recursive approach. Let's say the first coin you choose is a £1 coin. Then you have to work out how many ways you can split the remaining £1. You also need to make sure you don't double-count any permutations.

[Matthew Brown]

Randall Twede wrote:am i at least on the right track?

I'd suggest forgetting the £2 problem to begin with, and use the program to solve one simple enough to also do by hand. That way you can get it to write out the permutations, and you should be able to see which ones it's missing.

E.g. 6p can be split up in the following ways:
5, 1
2, 2, 2
2, 2, 1, 1
2, 1, 1, 1, 1
1, 1, 1, 1, 1, 1

[Randall Twede]

a very good suggestion Matthew! i have done that to help solve other problems before

[Randall Twede]

i have been struggling with this one for several days now and i still get the wrong answer
can anyone see anything wrong with this code?
it seems way too long for one thing, most of these problems only take about 30 lines or so

class Euler31 implements Problem
{
	public String solve()
	{
		final int pence = 200;
		int answer = 1;	//all 1p
		


		for(int i = pence; i >= 2;)
		{
			i = i - 2;
			answer++;	//all 2p & 1p
		}
		for(int i = pence; i >= 5;)
		{
			i = i - 5;
			answer++;	//all 5p & 1p
			for(int j = i; j >= 2;)
			{
				j = j - 2;
				answer++;	//all 5p, 2p & 1p
			}
		}
		for(int i = pence; i >= 10;)
		{
			i = i - 10;
			answer++;	//all 10p & 1p
			for(int j = i; j >= 2;)
			{
				j = j - 2;
				answer++;	//all 10p, 2p & 1p
			}
			for(int j = i; j >= 5;)
			{
				j = j - 5;
				answer++;	//all 10p, 5p & 1p
				for(int k = j; k>= 2;)
				{
					k = k - 2;
					answer++;	//all 10p, 5p, 2p & 1p
				}
			}
		}
		for(int i = pence; i >= 20;)
		{
		System.out.println("in 20");
			i = i - 20;
			answer++;	//all 20p & 1p
			for(int j = i; j >= 2;)
			{
				j = j - 2;
				answer++;	//all 20p, 2p & 1p
			}
			for(int j = i; j >= 5;)
			{
				j = j - 5;
				answer++;	//all 20p, 5p & 1p
				for(int k = j; k>= 2;)
				{
					k = k - 2;
					answer++;	//all 20p, 5p, 2p & 1p
				}
			}
			for(int j = i; j >= 10;)
			{
				j = j - 10;
				answer++;	//all 20p, 10p & 1p
				for(int k = j; k>= 5;)
				{
					k = k - 5;
					answer++;	//all 20p, 10p, 5p & 1p
					for(int l = k; l >= 2;)
					{
						l = l - 2;
						answer++;	//all 20p, 10p, 5p, 2p & 1p
					}
				}
			}
		}
		for(int i = pence; i >= 50;)
		{
		System.out.println("in 50");
			i = i - 50;
			answer++;	//all 50p & 1p
			for(int j = i; j >= 2;)
			{
				j = j - 2;
				answer++;	//all 50p, 2p & 1p
			}
			for(int j = i; j >= 5;)
			{
				j = j - 5;
				answer++;	//all 50p, 5p & 1p
				for(int k = j; k>= 2;)
				{
					k = k - 2;
					answer++;	//all 50p, 5p, 2p & 1p
				}
			}
			for(int j = i; j >= 10;)
			{
				j = j - 10;
				answer++;	//all 50p, 10p & 1p
				for(int k = j; k>= 5;)
				{
					k = k - 5;
					answer++;	//all 50p, 10p, 5p & 1p
					for(int l = k; l >= 2;)
					{
						l = l - 2;
						answer++;	//all 50p, 10p, 5p, 2p & 1p
					}
				}
			}
			for(int j = i; j >= 20;)
			{
				j = j - 20;
				answer++;	//all 50p, 20p & 1p
				for(int k = j; k>= 10;)
				{
					k = k - 10;
					answer++;	//all 50p, 20p, 10p & 1p
					for(int l = k; l >= 5;)
					{
						l = l - 5;
						answer++;	//all 50p, 20p, 10p, 5p & 1p
						for(int m = l; m >= 2;)
						{
							m = m - 2;
							answer++;	//all 50p, 20p, 10p, 5p, 2p & 1p
						}
					}
				}
			}
		}
		for(int i = pence; i >= 100;)
		{
		System.out.println("in 100");
			i = i - 100;
			answer++;	//all 100p & 1p
			for(int j = i; j >= 2;)
			{
				j = j - 2;
				answer++;	//all 100p, 2p & 1p
			}
			for(int j = i; j >= 5;)
			{
				j = j - 5;
				answer++;	//all 100p, 5p & 1p
				for(int k = j; k >= 2;)
				{
					k = k - 2;
					answer++;	//all 100p, 5p, 2p & 1p
				}
			}
			for(int j = i; j >= 10;)
			{
				j = j - 10;
				answer++;	//all 100p, 10p & 1p
				for(int k = j; k>= 5;)
				{
					k = k - 5;
					answer++;	//all 100p, 10p, 5p & 1p
					for(int l = k; l >= 2;)
					{
						l = l - 2;
						answer++;	//all 100p, 10p, 5p, 2p & 1p
					}
				}
			}
			for(int j = i; j >= 20;)
			{
				j = j - 20;
				answer++;	//all 100p, 20p & 1p
				for(int k = j; k>= 10;)
				{
					k = k - 10;
					answer++;	//all 100p, 20p, 10p & 1p
					for(int l = k; l >= 5;)
					{
						l = l - 5;
						answer++;	//all 100p, 20p, 10p, 5p & 1p
						for(int m = l; m >= 2;)
						{
							m = m - 2;
							answer++;	//all 100p, 20p, 10p, 5p, 2p & 1p
						}
					}
				}
			}
			for(int j = i; j >= 50;)
			{
				j = j - 50;
				answer++;	//all 100p, 50p & 1p
				for(int k = j; k>= 20;)
				{
					k = k - 20;
					answer++;	//all 100p, 50p, 20p & 1p
					for(int l = k; l >= 10;)
					{
						l = l - 10;
						answer++;	//all 100p, 50p, 20p, 10p & 1p
						for(int m = l; m >= 5;)
						{
							m = m - 5;
							answer++;	//all 100p, 50p, 20p, 10p, 5p & 1p
							for(int n = m; n >= 2;)
							{
								n = n - 2;
								answer++;	//all 100p, 50p, 20p, 10p, 5p, 2p & 1p
							}
						}
					}
				}
			}
		}
		answer++;	//one 200p
		return Integer.toString(answer);
	}
	
	public String getMessage()
	{
		return "How many different ways can £2 be made using any number of coins?";
	}
}

i get answer = 64184

[fred rosenberger]

Tim Moores wrote:My solution ended up having 8 nested loops. It also had a variable like this: int numCoins[] = new int[] { 0, 0, 0, 0, 0, 0, 0, 0 }

I also used eight nested loops, but had eight int variables instead of an array of eight ints.

[Campbell Ritchie]

Matthew Brown wrote:. . . You also need to make sure you don't double-count any permutations.

If you count your coins in size order, that should obviate that problem. If, for example, the first coin you try is a 50p, you are allowed to use 50p later, or go down to 20p, but you are not allowed to go up to £1. You can of course do the same in reverse order.

[Matthew Brown]

Campbell Ritchie wrote:If you count your coins in size order, that should obviate that problem.

Yes, that's how I did it.

[Bill Krieg]

Tim Moores wrote:The code I wrote for this a few years back found 73682 different ways. I've no idea if it's correct, though :-)

I also get 73682. I wrote a program to solve the general case (variable coins, different total) which I believe is virtually impossible without recursion. Otherwise you're looking at eight nested loops.

[Koen Aerts]

I have it with 2 loops. One main loop that goes through { 1, 2, 5, 10, 20, 50, 100, 200 } and each time calls a recursive function. The function itself also contains a loop, which is only executed when the current sum is less that the value that needs to be calculated (200p in this case). However I get 73681 solutions.

Edit: I get the correct result now of 73682 solutions. And about 40 lines of code. I use a LinkedList to keep track of all unique combinations.