Problem #53

This prob­lem over at Project Euler turned out to be a lot sim­pler than expected.  Forty-Three other prob­lems have been solved more times than this one; yet, it was dead sim­ple. Really, there is noth­ing inter­est­ing in its solu­tion, unlike Prob­lem #97 that I posted about yes­ter­day.

It’s straight com­bi­na­torics and fac­to­ri­als. So read the prob­lem page and be amazed at what a gimme this one is :)

Result: [snip]
Time: 0.321524143219

#!/usr/bin/python
import time
def fac­to­r­ial(n):
    if n > 1:
        return n * fac­to­r­ial(n–1)
    else:
        return 1

def com­bi­na­tions(r,n):
    return fac­to­r­ial(n)/(fac­to­r­ial(r)*fac­to­r­ial(n-r))

total = 0
start = time.time()
for n in range (1,101):
    for r in range(1, n+1):
        if com­bi­na­tions(r,n) > 1000000:
            total += 1
stop = time.time()
print “Result:”, total
print “Time:”, str(stop-start)

Problem #97

Now this prob­lem was inter­est­ing! It asked for us to find the last 10 dig­its of a very large Mersenne Prime dis­cov­ered in 2004 of the form 28433×27830457+1.

I solved this prob­lem three dif­fer­ent ways. The first was by my own logic, the other two, due to some research. My thought was that cal­cu­lat­ing 2n can be done in a loop that mul­ti­plies the pre­vi­ous value by 2 on each iter­a­tion. Rais­ing it to the 7,830,457th power though would not only take for­ever, but could be hard to store in mem­ory. So I fig­ured that we really only care about the last 10 dig­its. This meant I could mul­ti­ple the pre­vi­ous value by 2 on each iter­a­tion, but store for the next iter­a­tion a con­sist­ing of only the last ten dig­its. Python’s list syn­tax of [-10:] came in mighty handy for this.

My Method
==============
Result: 8739992577
Time: 9.89434504509

def my_method():
    print ““
    print “My Method“
    print “==============“
    last=“2”
    start = time.time()
    for p in range(2,7830458):
        last = str(int(last)*2)
        last = last[-10:]
    result =  str(28433*int(last)+1)
    stop = time.time()
    print “Result: “+result[-10:]
    print “Time: “+str(stop-start)

It was fairly quick, sub 10 sec­onds, but not as fast as it could be.

The next method I tried was to uti­lize the bit­wise shift oper­a­tor. I saw this for a C++ solu­tion in the forums after solv­ing it and won­dered if Python had a bit­wise shift. Turns out it does. Hav­ing a base of 2 for the pow­ers is what makes this pos­si­ble. Rather than mul­ti­ply­ing a num­ber by 2, we can shift it’s binary value to the left by one posi­tion for the same affect. CPU’s are typ­i­cally faster at bit shift­ing than they are at mul­ti­ply­ing. This solu­tion took less than 2 sec­onds! That’s quite an improvement.

Bit­wise Method
==============
Result: 8739992577
Time: 1.6119530201

def bit­wise():
    print ““
    print “Bit­wise Method“
    print “==============“
    start = time.time()
    ans = 1
    for n in range(1,7830458):
        ans = ans « 1
        ans = ans % 10000000000
    ans = ans * 28433
    ans = ans % 10000000000
    ans = ans + 1
    stop = time.time()
    print “Result: “+str(ans)
    print “Time: “+str(stop-start)

I’m not sure how, but I ended up read­ing this arti­cle on OSIX about quickly cal­cu­lat­ing inte­ger pow­ers. It pro­posed a func­tion in C# that used recur­sion to cal­cu­late a power in O(logn) time rather than the O(n) time that the first two meth­ods imple­mented. I trans­lated the code to Python, and sure enough, it solves this prob­lem in less than half of a second!

Power Method
==============
Result: 8739992577
Time: 0.471854925156

def get_power(a,n): # a^n
    if n==0:
        return 1
    if a==0:
        return 0
    if n%2==0:
        return get_power(a*a, n/2)
    else:
        return a*get_power(a*a, n/2)
    return 0

def power():
    print ““
    print “Power Method“
    print “==============“
    start = time.time()
    value = get_power(2,7830457)
    ans = 28433*value+1
    ans = ans % 10000000000
    stop = time.time()
    print “Result: “+str(ans)
    print “Time: “+str(stop-start)

Thinking in Code vs. Thinking in Mathematics

Lately I’ve been hooked on the web­site Project Euler. Today I sat down to solve Prob­lem #15:

Start­ing in the top left cor­ner of a 2×2 grid, there are 6 routes (with­out back­track­ing) to the bot­tom right cor­ner.
How many routes are there in a 20x20 grid?

My ini­tial thought with this was “recur­sion!” So I sat down and thought about graphs and trees from pre­vi­ous CS classes, debated cre­at­ing a node class with down and right attrib­utes that would be check off after they were used, etc. Then I real­ized that it could be solved with a sin­gle recur­sion func­tion, given two argu­ments (the x and y posi­tion). My ini­tial code in ruby is below:
[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Con­struc­tor
def ini­tial­ize (n = 10)
@n = n.to_i
@paths = 0
end

# Solve it
def solve
node(0,0)
puts “Found #{@paths} paths“
end

# Recur­sively check for paths
def node(x, y)
# First, are we the end node?
if x == @n && y == @n
@paths += 1
return
end

# Lets go “right“
node(x+1,y) if x < @n # Lets go “down“ node(x,y+1) if y < @n end end if __FILE__ == $0 # Ini­tial­ize the pro­gram p = Problem.new ARGV[0] || 2 p.solve end [/sourcecode] This works quite well for small val­ues of n. The issue is that it’s basi­cally a brute force method, and per­for­mance of this falls off rather quickly as n increases.

n   ms  paths
============================
2   5   6
3   5   20
4   5   70
5   6   252
6   8   924
7   17  3432
8   57  12870
9   176 48620
10  668 184756
11  2513    705432
12  9401    2704156

This forced me to take another look at the prob­lem. If I approach it from a math­e­mat­i­cal view­point I can see that there is def­i­nitely a pat­tern. To get from the top left to the bot­tom right we must always go N moves to the right, and N moves down­ward. If we call the left and right posi­tions X and the up and down posi­tions Y, and write out our path with X’s and Y’s, we’ll get XXYY for one of the posi­tions of the 2x2 grid. Another would be XYYX. And so forth. What this is rep­re­sent­ing is the per­mu­ta­tion of indis­tin­guish­able objects, where (x+y)!/(x!y!) gives the num­ber of permutations.

My code for this is below:
[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Cre­ate the object
def ini­tial­ize (n = 10)
@n = n.to_i
@paths = 0
end

# Solve it
def solve
@paths = f(@n*2)/(f(@n)**2)
puts “Found #{@paths} paths“
end

# Fac­to­r­ial of n
def f(n)
n == 1 ? 1 : n*f(n-1)
end

end

if __FILE__ == $0

# Ini­tial­ize the pro­gram
p = Problem.new ARGV[0] || 2
p.solve

end
[/sourcecode]

This is much quicker. It actu­ally is able to cal­cu­late the num­ber of paths for a give NxN grid in just a cou­ple mil­lisec­onds. It takes 5ms for N up to 115. Thats what I call improvement!

The les­son learned from this prob­lem is that even though a “cod­ing” solu­tion is read­ily appar­ent (and works!) it may not nec­es­sar­ily be the best or most effi­cient solu­tion to the prob­lem. That is why a good under­stand­ing of math will never hurt ;)