Problem Thirty One

7 Dec

Here’s problem thirty one:

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

My solution to this wasn’t very pretty — just look at the monstrous for loop below.

result = 2

for b in range(2):
	for c in range(5):
		if 100*b + 50*c > 200: continue
		for d in range(11):
			if 100*b + 50*c + 20*d > 200: continue
			for e in range(21):
				if 100*b + 50*c + 20*d + 10*e > 200: continue
				for f in range(41):
					if 100*b + 50*c + 20*d + 10*e + 5*f > 200: continue
					for g in range(101):
						if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g > 200: continue
						for h in range(201):
							if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g + h == 200:
								result += 1

print(result)

Yeah…zero points for style there. I know for a fact that there is a “clever” way of solving this problem, but its explanation was pretty over my head. Essentially this code works by trying (almost) every combination of coins possible and testing it to see if its value is 200. This is slightly streamlined by initially considering two possibilities, 200 and 100 + 100, so that there are less total calculations. This is the reason why result is initialized to 2 and there is no loop for the 200 coin. The number of calculations is also reduced by continuing (skipping to the next iteration) the for loop whenever the current value is greater than 200, which also skips all corresponding inner nested loops.

This slight detail allows us to skip most of the 1,922,707,710 calculations needed for a complete brute force solution, and returns an answer in a reasonable amount of time.

Answer: 73682

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: