Euler Problem 31

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?

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

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?

Does that mean 100 loops are required?

…mrt

Posted in Uncategorized

13 thoughts on “Euler Problem 31

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

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

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

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

  5. 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}

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

    Sub kic31()
      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

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

Leave a Reply

Your email address will not be published. Required fields are marked *