Project euler N 31 | the dumb way

in #python7 years ago

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