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.

1 thought on “Euler 107 – Back to Python

  1. tiwari_mukesh

    “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” I think this the good sign of learning Haskell. I would rather say don’t leave using Haskell because of some cabal and IDE issues. It’s still one of the best language and I wrote the above solution in approximately 11-12 lines and besides it looks more cool than python 🙂

    Reply

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