Wednesday, October 24, 2012

Progress. Whoa..

It's been a bit of a hiatus, but I've been at it the whole time.  I'm finally starting to feel comfortable writing code.  That sounds a bit silly when I say it out loud; I've been reading and writing code on a daily basis for several weeks now.  And yet, I never felt a sense of mastery over the concept I was trying to model, or the solution I was trying to implement.  I've been unable to craft 100% exactly what I want into a set of precise instructions, though I've caught a glimpse of what that feels like here and there.

So there's this set of math-oriented programming challenges on the interwebs, called Project Euler.  I'm (slowly) completing them, one-by-one.  A maths wizard I am not, by any means, and I constantly feel like I'm in over my head when working some of these problems.  They get progressively harder in succession, and with every one of these I knock down, inevitable fist pumping ensues.

Here's problem #5:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.  What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Now the cool thing about Euler problems is they are open-ended in their implementation.  You can use any language, any model, and any algorithm, so long as you reach the correct solution.  I really like this method of learning, as opposed to a problem set like pyschools. Pyschools does a lot of hand-holding in helping frame the problem and shape your program.  Euler does not care about how you solve the problem in the slightest, and I think being 'stranded' in this way forces you to pull up your bootstraps and design your solution from the ground-up.  I think us beginner programmers face an uneasiness once we step out of Tutorial Land and into Outer Problem Space.  The only way to overcome this obstacle is to grab the nearest handhold and start climbing.

Anyway, I haven't yet reached a solution for this one, but I'm close.  Thus far, I've been able to write a small program to tackle the smaller problem: producing the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.  This gives me the ability to test a small-scale solution before I blow it up for the actual problem (all digits 1-20).

divisors = [2,3,4,5,6,7,8,9,10]

def euler_5(*divs):
    start = divs[0]
    for d in range(1, len(divs) + 1):
        start *= d
    g = 0
    for n in range(start, 0, -divs[0]):
        g += 1
        check = 0
        for d in divs:
            check += n % d
        if check == 0:
            ans = n
    print ans, g


In the first part, I'm trying to determine a starting number to begin testing for divisibility.  I ended up multiplying all the numbers in the range of divisors and counting down from there.  Why?  I wanted to begin with a number that I knew already had to be divisible by all the members of the divisor set.... plus that was just the first method I could think of.   This part could really use some work, generating a better guess is essential to having a fast iterative algorithm.

The second loop increments my guess counter, g, and then in a nested loop iterates through each element d in divisors, checking to see if they divide evenly.  This is accomplished through the modulus operator (%), which instead of returning the result of a division, returns the remainder only.  If a number passes all checks, I then store it in the variable ans, continuing on to see if I can find a smaller number.

I've been able to get it to spit out the number 2520 given a divisor list of the numbers 1 through 10, so I know it works.  My current problem is when I try divisors from 11 to 20 my initial guess is too high.  IDLE is giving me an error, I think the Python list object is unable to hold a range of numbers 670,442,572,800 digits long, and I wouldn't expect it to.  That's quite big.

So I've gotta figure a workaround for that, but confidence abounds!  Happy coding.

No comments:

Post a Comment

Let me know what you think!