# 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):
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:
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")
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 🙂