Tag Archives: Python

Cloud Envy

6356-1600x1200Everything is about the cloud today. Seeing as I don’t have a cloud to stand on, I thought I should learn me some.

Purely as a proof-of-concept, I whipped up a web application using only cloud development tools and PaaS deployment. The concept of web-based Cubbyholes for text might seem overly simplistic, but all coding was done in the cloud using Exo IDE (now called Codenvy) which provides Python code to be directly deployed to Google’s AppEngine PaaS.

Google-App-Engine-Finally-Graduates-Ready-for-Business

Users can register using their Google account and privately save text in their ‘cubbyholes’, which can also be embedded (need HTML5 for that). Must admit Google’s API is super, plus I’m allowed something like a few million hits per day before any money needs to be thrown at it. So scalability becomes transparent too. Quite honestly I’m really impressed. Programming everything using JQuery UI also made things very simple. Although I can’t stand javascript, and html, this project was fun.

Follow up: Trying to mix JQuery Mobile framework for iPhone with Google AppEngine. Trickier than I thought because of the python handler…
Building Project-2-Factor to be a customizable and mobile (iPhone web app) version of PasswordCard. Bit of a headache.

Euler 221 – Alexandrian Numbers


When I came upon this Euler problem, and saw it was based on my namesake, I couldn’t help going for it. As with many of the Project Euler problems, the trick is to find a technique that reduces the brute force solution into something more efficient.

The functions from the original problem can be re-written to:
A = p(p + d)((p^2 + 1)/d + p)

The Alexandrian numbers are calculated from the new function, where d runs over divisors of p^2+1 and p runs over all positive integers. Used a fast Divisor routine that I Googled, then started building a Set (which is speed optimized to avoid duplicates) until length is 15K. Convert to a List, then sort and display 150,000th number. Numbers 1 thru 6 also listed to verify computation working. Runs in about 10 mins on my quad core iMac.

# e221.py

from math import sqrt
from functools import reduce


def appendEs2Sequences(sequences, es):
    result = []
    if not sequences:
        for e in es:
            result.append([e])
    else:
        for e in es:
            result += [seq + [e] for seq in sequences]
    return result


def primefactors(n):
    i = 2
    while i <= sqrt(n):
        if n % i == 0:
            l = primefactors(n // i)
            l.append(i)
            return l
        i += 1
    return [n]


def factorGenerator(n):
    p = primefactors(n)
    factors = {}
    for p1 in p:
        try:
            factors[p1] += 1
        except KeyError:
            factors[p1] = 1
    return factors


def divisors(n):
    factors = factorGenerator(n)
    divisors = []
    listexponents = [list(map(lambda x:k ** x, list(range(0, factors[k] + 1)))) for k in factors.keys()]
    listfactors = reduce(appendEs2Sequences, listexponents, [])
    for f in listfactors:
        divisors.append(reduce(lambda x, y: x * y, f, 1))
    divisors.sort()
    return divisors


if __name__ == "__main__":
    A = set()
    p = 1
    while len(A) <= 1500001:
        for d in divisors((p * p) + 1):
            A.add(int(p * (p + d) * (p + ((p * p) + 1) / d)))
        p += 1
    L = list(A)
    L.sort()
    for i in [1,2,3,4,5,6,150000]:
        print (str(i) + ": " + str(L[i-1]))

Euler 113 – Bouncy Numbers


This one has to do with combinatorics and we use the good old fashion binomial coefficient identity (built from factorials or Bang!). Any increasing number can be represented using binary strings. For example, all 3-digit increasing numbers using 0, 1, 2 can be represented with 5-digit binary numbers:

11100 = 000
11010 = 001
11001 = 002
10110 = 011
10101 = 012
10011 = 022
01110 = 111
01101 = 112
01011 = 122
00111 = 222

Which means that there are (5 choose 3) - 1 = 9 of these numbers. The reason for subtracting 1 is that we don’t want to count the number “000”. By extension, all 3-digit increasing numbers with the digits 0-9 requires a binary string containing 3 ones and 9 zeroes and so on. The same can be extended to 10^100.

For decreasing numbers, the only difference is that we might have a zero in the front and end of the string. Note the following pattern of zeros.

111000 = 000
110100 = 002
110010 = 001
110001 = 000 *
101100 = 022
101010 = 021
101001 = 020
100110 = 011
100101 = 010
100011 = 000 *
011100 = 222
011010 = 221
011001 = 220
010110 = 211
010101 = 210
010011 = 200
001110 = 111
001101 = 110
001011 = 100
000111 = 000 *

You can see for 3-digit numbers that “000” will be repeated 3 times after the initial time. For an n-digit number the pattern repeats n times. This gives us (n+10 choose 10) -1 -n. Additionally, numbers like 222 and 11 have both properties. Since we have counted them twice, they need to be removed. There are 9*100 of these numbers which are counted twice.

So this gives us:

Here's the Python code. Its pretty short since we've simplified everything down to a couple binomial calculations.

def bang (x):
    return x > 1 and x * bang (x - 1) or 1

def choose (n, k):
    return bang (n) / (bang (k) * bang (n-k))

if __name__ == "__main__":
    print (int (choose (110, 10) + choose (109, 9) - 1002))

Euler 107 – Back to Python


Haskell has a lot going for it. It is brilliantly conceived to ensure functional programming paradigm purity, has hardly any squiggly brackets and most importantly, no freaking semi-colons on every single freaking line. But I digress. I’ve found that package and module management is spotty at best, with Cabal choking regularly. There’s no decent IDE, although I’ve been able to find loads of text editors that can run GHCi in a console. I did finally manage to wrap my brain around functional programming concepts, but interestingly I found that I was spending too much time thinking about how to write it, rather than actually writing. So back to Python. Its might be slow, but its still the best all round language.

Euler problem 107 piqued my interest immediately due to the practical application. Minimum Spanning Tree (MST) routing problems are a cornerstone of networking theory. This solution employs a simple implementation of Kruskal’s algorithm. Also used a very handy Disjointed Set class.

# e107.py

from operator import itemgetter

class DisjointSet (dict):
    def add(self, item):
        self[item] = item
    
    def find(self, item):
        parent = self[item]
        while self[parent] != parent:
            parent = self[parent]
        self[item] = parent
        return parent
    
    def union(self, item1, item2):
        self[item2] = self[item1]

def kruskal (nodes, edges):
    forest = DisjointSet ()
    mst = []
    for n in nodes:
        forest.add (n)
    sz = len(nodes)-1
    for e in sorted (edges, key = itemgetter(2)):
        n1, n2, _ = e
        t1 = forest.find (n1)
        t2 = forest.find (n2)
        if t1 != t2:
            mst.append (e)
            sz -= 1
            if sz == 0:
                return mst
            forest.union (t1, t2)

def convert2Edges (m):
    e = []
    for i in range (1, len(m)):
        for j in range (0,i):
            if m[i][j] != 0:
                e.append ([str(i), str(j), m[i][j]])
    return e

def generateNodes (m):
    n = []
    for i in range(0, len(m)):
        n.append(str(i))
    return n

def calcWeight(e):
    w = 0
    for i in e:
        w += i[2]
    return w

def generateMatrix ():
    m = []
    f = open ("network.txt", "r")
    for line in f.read().split ('\n'):
        m.append (line.split (","))
    f.close()
    num = len(m)
    for i in range (0, num-1):
        for j in range (0, num-1):
            if m[i][j] == '-' or m[i][j] == '-\r':
                m[i][j] = '0'
            m[i][j] = int (m[i][j])
    m.pop()
    return m
    
if __name__=="__main__":
    m = generateMatrix()
    e = convert2Edges (m)
    n = generateNodes (m)
    e1 = kruskal (n,e)
    w1 = calcWeight (e)
    w2 = calcWeight (e1)
    print ("Original weight: " + str (w1))
    print ("New weight: " + str (w2))
    print ("Difference: "+ str (w1-w2))

Sweet! Just found out that Python supports list comprehensions — sort of. Definitely the most useful part of Haskell’s functional syntax. As an example, the weight function can be lightened down to (pun intended):

def calcWeight (e): return sum ([x[2] for x in e])

Pretty cool to use for the simple stuff.

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"

Euler 89 – Roman Numerals

Finally got over my programmer’s block and completed another Euler problem. This one deals with optimizing roman numerals.

Created a couple routines to convert between decimals and roman numerals. Simply read in each number, convert it to decimal, and back to numeral again. This essentially optimized the numeral. Add up the savings and presto!

Yeah, yeah, I know there are probably really cool shortcuts you can do, but with these routines, I can convert anything now. And its more fun this way.

def num2dec (numeral):
    decimal = 0
    for n in range(0,len(numeral)):
        if numeral[n] == "M":
            decimal += 1000
        if numeral[n] == "D":
            decimal += 500
        if numeral[n] == "C":
            decimal += 100
            if n != len(numeral)-1:
                if numeral[n+1] == "D" or numeral[n+1] == "M":
                    decimal -= 200
        if numeral[n] == "L":
            decimal += 50
        if numeral[n] == "X":
            decimal += 10
            if n != len(numeral)-1:
                if numeral[n+1] == "L" or numeral[n+1] == "C":
                    decimal -= 20
        if numeral[n] == "V":
            decimal += 5
        if numeral[n] == "I":
            decimal += 1
            if n != len(numeral)-1:
                if numeral[n+1] == "V" or numeral[n+1] == "X":
                    decimal -= 2
    return decimal
def dec2num (decimal):
    numeral = ""
    for i in range (0, decimal // 1000):
        numeral += "M"
        decimal -= 1000
    if decimal >= 900:
        numeral += "CM"
        decimal -= 900
    for i in range (0, decimal // 500):
        numeral += "D"
        decimal -= 500
    if decimal >= 400:
        numeral += "CD"
        decimal -= 400
    for i in range (0, decimal // 100):
        numeral += "C"
        decimal -= 100
    if decimal >= 90:
        numeral += "XC"
        decimal -= 90
    for i in range (0, decimal // 50):
        numeral += "L"
        decimal -= 50
    if decimal >= 40:
        numeral += "XL"
        decimal -= 40
    for i in range (0, decimal // 10):
        numeral += "X"
        decimal -= 10
    if decimal == 9:
        numeral += "IX"
        decimal -= 9
    for i in range (0, decimal // 5):
        numeral += "V"
        decimal -= 5
    if decimal == 4:
        numeral += "IV"
        decimal -= 4
    for i in range (0, decimal // 1):
        numeral += "I"
        decimal -= 1
    return numeral
if __name__=="__main__":
    sum = 0
    for n in open("C://Python27//roman.txt", "r"):
        n = n.rstrip('\n')
        sum += len(n) - len(dec2num(num2dec(n)))
    print "Answer =", sum