Reply To: Programming

Solution for Question 3:
Here are the first, and last 10 sets, as requested.

1p: 0 | 2p: 0 | 5p: 0 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 1
1p: 0 | 2p: 0 | 5p: 0 | 10p: 0 | 20p: 0 | 50p: 2 | 100p: 0
1p: 0 | 2p: 0 | 5p: 0 | 10p: 0 | 20p: 5 | 50p: 0 | 100p: 0
1p: 0 | 2p: 0 | 5p: 0 | 10p: 1 | 20p: 2 | 50p: 1 | 100p: 0
1p: 0 | 2p: 0 | 5p: 0 | 10p: 2 | 20p: 4 | 50p: 0 | 100p: 0
1p: 0 | 2p: 0 | 5p: 0 | 10p: 3 | 20p: 1 | 50p: 1 | 100p: 0
1p: 0 | 2p: 0 | 5p: 0 | 10p: 4 | 20p: 3 | 50p: 0 | 100p: 0
1p: 0 | 2p: 0 | 5p: 0 | 10p: 5 | 20p: 0 | 50p: 1 | 100p: 0
1p: 0 | 2p: 0 | 5p: 0 | 10p: 6 | 20p: 2 | 50p: 0 | 100p: 0
1p: 0 | 2p: 0 | 5p: 0 | 10p: 8 | 20p: 1 | 50p: 0 | 100p: 0
…
1p: 90 | 2p: 0 | 5p: 2 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0
1p: 90 | 2p: 5 | 5p: 0 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0
1p: 91 | 2p: 2 | 5p: 1 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0
1p: 92 | 2p: 4 | 5p: 0 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0
1p: 93 | 2p: 1 | 5p: 1 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0
1p: 94 | 2p: 3 | 5p: 0 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0
1p: 95 | 2p: 0 | 5p: 1 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0
1p: 96 | 2p: 2 | 5p: 0 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0
1p: 98 | 2p: 1 | 5p: 0 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0
1p: 100 | 2p: 0 | 5p: 0 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 0

Surprisingly, I could just bruteforce this question without any optimisations.

Initially, I was gonna make a recursive solution that would prune branches if the sum exceeded 100, but it looks like that wasn’t necessary.

print("1p: 0 | 2p: 0 | 5p: 0 | 10p: 0 | 20p: 0 | 50p: 0 | 100p: 1")
for i in range(101): # 1p coins
    for j in range(51): # 2p coins
        for k in range(21): # 5p coins
            for m in range(11): # 10p coins
                for n in range(6): # 20p coins
                    for o in range(3): # 50p coins
                        if sum([i, 2*j, 5*k, 10*m, 20*n, 50*o]) == 100:
                            print("1p:", i, "| 2p:", j, "| 5p:", k, "| 10p:", m, "| 20p:", n, "| 50p:", o, "| 100p: 0")