Euler 145 – Brute Force Solution

Testing for reversible properties of a billion numbers sounds like a simple premise. And it is. But it takes time. There are a number of shortcuts you can find on the Internet, like if a number is reversible then its reverse is also reversible. But after messing around with whether or not a number and its reverse are part of a set with certain starting or ending numbers etc, so as to avoid even numbers, I came to the conclusion that good old-fashioned brute force gets the job done best.

The routine below runs in about 1.8 hours on a 6-year old dual-core machine. Not blazingly fast. Python is SLOOOOW. I have a need for speed, but hate C/C++. Hmmm, being a sucker for punishment, I’m going to translate the same code into Haskell and see what happens. Haskell compiler speeds have a reputation of being epic. We shall see…

import time
if __name__=="__main__":
    t0 = time.time()
    c = 0
    i = 1
    while i < 10**9:
        if i % 10**6 == 0:
            print "i:"+str(i)+" -> c:"+str(c)
        if i % 10 == 0:
            i += 1
            continue
        rev = str(int(str(i))+int(str(i)[::-1]))
        if '0' in rev or '2' in rev or '4' in rev or '6' in rev or '8' in rev:
            i += 1
            continue
        c += 1
        i += 1
    print "Answer = "+str(c)
    print time.time() - t0, "seconds"

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s