Preface:
I'm NOT a professional programmer nor an undergraduate in computer science or any kind of that. I'm simply a guy who's trying to learn how to code.
After binging some Youtube playlists for python, I've decided to challenge myself with Project Euler, and this series of blogs is my attempt at solving this problems "the dumb way", meaning using brute force and not some mathematical formula to find the solution.
Project Euler n°31:
the problem ask us to find all the possible solutions to the equation :
200.a + 100.b + 50.c + 20.d + 10.e + 5.f + 2.x + 1.y = 200
the simplest idea is to loop through all the numbers < 200 and see if they verify the equation, which roughly translate to :
for i in range(200):
for i in range(200):
.......
if (equation == 200) : increment value
this kind of code can work for this particular exemple but what if we had 50 variables. It's impossible to write 50 for loops, so the best solution is to create a recursive function that'll do the work for us and cover any equation of this type.
the idea is to create a function that works for 2 variables and then generalize it by changing the equation like this :
level 1 : 200.a + 100.b + 50.c + 20.d + 10.e + 5.f + 2.x = (200 - 1.y)
level 2 : 200.a + 100.b + 50.c + 20.d + 10.e + 5.f = (200 - 1.y) - 2.x
.
.
.
level 7 : 200.a = ((((200 - 1.y) - 2.x)..... - 100.b)
We can clearly see the recursive pattern which will give us the code :
import sys
inc = 0
def Equation_solver(ceoff_array, result):
global inc
ceoff_length = len(ceoff_array)
if (result < 0) : return False
elif (result == 0):
inc += 1
return True
elif (ceoff_length > 1):
for i in range(int(result/ceoff_array[-1])+1):
Equation_solver(ceoff_array[:ceoff_length - 1],result - ceoff_array[-1] * i)
#if( x == result ): inc += 1
#return x
elif (ceoff_length == 1):
if( (result)%(ceoff_array[0]) == 0 ): inc += 1
else : sys.exit("Error")
def main():
global inc
list_ceoff = [200,100,50,20,10,5,2,1]
total = 200
Equation_solver(list_ceoff,total)
print(inc)
main()