Euler Problem 31 states:
‘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?
‘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?
Over in the Euler Problem 16 thread, dbb provided his answer. This is dbb’s code, copied from there, with 8 loops for eight coins:
Sub P31()
Dim P1 As Long, P2 As Long, P5 As Long, P10 As Long, P20 As Long
Dim P50 As Long, P100 As Long, P200 As Long
Dim n1 As Long, n2 As Long, n5 As Long, n10 As Long, n20 As Long
Dim n50 As Long, n100 As Long, n200 As Long
Dim n As Long
For P1 = 0 To 200 Step 1
n1 = P1
For P2 = 0 To 200 – n1 Step 2
n2 = n1 + P2
For P5 = 0 To 200 – n2 Step 5
n5 = n2 + P5
For P10 = 0 To 200 – n5 Step 10
n10 = n5 + P10
For P20 = 0 To 200 – n10 Step 20
n20 = n10 + P20
For P50 = 0 To 200 – n20 Step 50
n50 = n20 + P50
For P100 = 0 To 200 – n50 Step 100
n100 = n50 + P100
For P200 = 0 To 200 – n100 Step 200
If n100 + P200 = 200 Then
n = n + 1
End If
Next P200
Next P100
Next P50
Next P20
Next P10
Next P5
Next P2
Next P1
Debug.Print n
End Sub
Dim P1 As Long, P2 As Long, P5 As Long, P10 As Long, P20 As Long
Dim P50 As Long, P100 As Long, P200 As Long
Dim n1 As Long, n2 As Long, n5 As Long, n10 As Long, n20 As Long
Dim n50 As Long, n100 As Long, n200 As Long
Dim n As Long
For P1 = 0 To 200 Step 1
n1 = P1
For P2 = 0 To 200 – n1 Step 2
n2 = n1 + P2
For P5 = 0 To 200 – n2 Step 5
n5 = n2 + P5
For P10 = 0 To 200 – n5 Step 10
n10 = n5 + P10
For P20 = 0 To 200 – n10 Step 20
n20 = n10 + P20
For P50 = 0 To 200 – n20 Step 50
n50 = n20 + P50
For P100 = 0 To 200 – n50 Step 100
n100 = n50 + P100
For P200 = 0 To 200 – n100 Step 200
If n100 + P200 = 200 Then
n = n + 1
End If
Next P200
Next P100
Next P50
Next P20
Next P10
Next P5
Next P2
Next P1
Debug.Print n
End Sub
It runs in a second and a half on my machine. Problem 76 looks very similar.
‘It is possible to write five as a sum in exactly six different ways:
‘
‘4 + 1
‘3 + 2
‘3 + 1 + 1
‘2 + 2 + 1
‘2 + 1 + 1 + 1
‘1 + 1 + 1 + 1 + 1
‘
‘How many different ways can one hundred be written as a sum of at least
‘two positive integers?
‘
‘4 + 1
‘3 + 2
‘3 + 1 + 1
‘2 + 2 + 1
‘2 + 1 + 1 + 1
‘1 + 1 + 1 + 1 + 1
‘
‘How many different ways can one hundred be written as a sum of at least
‘two positive integers?
Does that mean 100 loops are required?
…mrt
Hi Dick – is there a limit to the extent of a potential post that can be previewed. I have Problem 55 in draft that continually gets truncated at the same spot, and I’ve lost all track of what might be below ;-) if anything?
Happy New Year to All.
…Michael
Iteration will solve problem 76, taking nearly 9 minutes, but VBA is not the quickest. Essentially the code below starts with a number (running backwards from 100 to 1 for no particular reason) and finds all the sequences of that number or smaller numbers that make up 100.
Sub P76()
Dim m As Long
fP76 100, 0, m
Debug.Print m - 1
End Sub
'n = number currently being added
'S = total sum so far
'm = number of solutions
Sub fP76(ByVal n As Long, ByVal S As Long, ByRef m As Long)
Dim i As Long
Dim t As Long
For i = n To 1 Step -1
t = S + i
'tell you when it has a new starting number
If S = 0 Then Debug.Print i; m
Select Case t
Case Is
Sorry, my first response got truncated, here is the rest of my code
If S = 0 Then Debug.Print i; m
Select Case t
Case Is
aha, I think I figured out the problem both Michael and I are having. The comment editor truncates everything after a “less than” symbol because it thinks it’s an HTML tag
Here is my full code with a text substitute for the “less than” sign
Sub P76()
Dim m As Long
Dim t As Single
t = Timer
fP76 100, 0, m
Debug.Print m – 1, (Timer – t) / 60
End Sub
Sub fP76(ByVal n As Long, ByVal S As Long, ByRef m As Long)
Dim i As Long
Dim t As Long
For i = n To 1 Step -1
t = S + i
If S = 0 Then Debug.Print i; m
Select Case t
Case Is LESSTHAN 100
fP76 i, t, m
Case 100
m = m + 1
End Select
Next i
End Sub
No limit, as far as I know. I can’t imagine what’s cutting it off. Can you send me the text of the post in an email?
Use a recursive approach for both Euler 31 and Euler 76 — they are nearly the same problem!
A recursive approach can be easily generalized to search for a target T with N possible ‘buckets’ whereas a nested loops approach requires a code change whenever N changes. For example, how many ways can you come up with $250 using bills / coins of denomination 100, 50, 20, 10, 5, 2, 1, 50c, 25, 10, 5, and 1? With a recursive approach, only the input data set would change.
The recursive code for 31 should be easily adaptable to 76! Just use 99 buckets, 1, 2, …, 99. The big difference is that we must use at least 2 buckets in 76 whereas in 31 a single bucket is acceptable.
It should not be very difficult to generalize the VBA code at
Find a set of amounts that match a target value
http://www.tushar-mehta.com/excel/templates/match_values/index.html
The only difference between the code on that page and the requirement for 31 is that the code imposes an implicit restriction that each bucket (value) be used only once. For 31 each value can be used as often as required. But, that should be a trivial change to the code. I’ll try it tomorrow and share the results. Adapting the code for 31 to 76 will require some additional work. But that too should not be too difficult. Hopefully, I will not have to eat my claim that the recursive approach requires a trivial change. {grin}
Hi Dick –
Email on it’s way from my work address. dbb may be right.
…mrt (Happy New Year to all!)
OK. The recursive solution to Euler 31 based on the template I’d mentioned in my last comment is now on my website. Visit http://www.tushar-mehta.com/misc_tutorials/project_euler/euler031.html
I’ve tried a recursive routine which is more elegant & versatile. But for Project Euler we want speed… and recursive routines take too much ticks on the stack.
Thus nesting: start with the largest coin, then try to fill the (declining) remaining balance.
Dim t!: t = Timer
Dim p002&, p005&, p010&, p020&, p050&, p100&, p200&
Dim n002&, n005&, n010&, n020&, n050&, n100&, n200&
Dim amnt&, rslt&
amnt = 200
For p200 = 0 To amnt Step 200: n200 = amnt – p200
For p100 = 0 To n200 Step 100: n100 = n200 – p100
For p050 = 0 To n100 Step 50: n050 = n100 – p050
For p020 = 0 To n050 Step 20: n020 = n050 – p020
For p010 = 0 To n020 Step 10: n010 = n020 – p010
For p005 = 0 To n010 Step 5: n005 = n010 – p005
For p002 = 0 To n005 Step 2: rslt = rslt + 1
Next: Next: Next: Next: Next: Next: Next
Debug.Print amnt; rslt; Timer – t
End Sub
One way is big-endian (so to speak) and the other little-endian. Does is matter?
…mrt
Recursion: see Recursion
(don’t remember where I saw this)
keepITcool: You might want to try the recursive approach rather than simply concluding that the performance is unacceptable because it is recursive.
“But for Project Euler we want speed…”
I think different people want different things. Looking at the comments it seems that a lot of people are keen to write the most elegant or the shortest code they can. For me the point is to come up with the code that gives the correct answer (within the program run time constraint) in the shortest possible time spent working on it. In other words if I can reduce the solution time from 59 seconds to 1 microsecond with less than 58 seconds worth of coding, that’s worth doing, otherwise it isn’t and I’ll move onto something else. The only proviso is that if the code is re-useable (either in Project Euler or elsewhere) then it’s worth spending some time optimising it.