Problem #107 concerns determining the Minimum Spanning Tree for a weighted graph. The question reads:
As it turns out, the formal term for this type of minimal network is the Minimum Spanning Tree of the graph. There are many well known algorithms for finding the minimum spanning tree of an arbitrary graph. I used Prim’s Algorithm because I thought it would be the easiest to implement. Here’s my solution:
Solution #1: Prim’s Algorithm Approach
Prim’s Algorithm involves choosing an arbitrary starting point and growing the Minimum Spanning Tree one vertex at a time by choosing the potential edge with the lowest weight. I recommend checking the wikipedia article linked above for a clearer description of this algorithm. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #107
'''
import time
f = open("PE107Grid.txt","r")
if f.mode=="r":
contents = f.readlines()
realContents = []
for x in contents:
coords = x.split(",")
new = []
for x in coords:
if x=="-" or x=="-\n":
new.append(0)
else:
new.append(int(x))
realContents.append(new)
else:
raise ValueError("Cannot read from file")
def minimumSpanningTree(myList):
l = len(myList)
vertices = [0]
edges = []
while(len(vertices)<l):
newV = []
newW = []
newC = []
for x in vertices:
for i in range(l):
if(x!=i):
v = myList[x][i]
if(v>0 and i not in vertices):
if i in newV:
a = newV.index(i)
w = newW[a]
if(v<w):
newW[a] = v
newC[a] = x
else:
newV.append(i)
newW.append(v)
newC.append(x)
lw = len(newW)
if(lw==0):
return -1
else:
myMin = newW[0]
minIndex = 0
for i in range(lw):
if(newW[i]<myMin):
myMin = newW[i]
minIndex = i
vertices.append(newV[minIndex])
edges.append(sorted([newC[minIndex],newV[minIndex]]))
return edges
def projectEulerProblemOneHundredSeven(myList):
mySum = 0
for x in myList:
mySum+=sum(x)
mySum/=2
a = minimumSpanningTree(myList)
total = 0
for x in a:
total+=myList[x[0]][x[1]]
return mySum-total
start = time.time()
print projectEulerProblemOneHundredSeven(realContents)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
259679
--- 0.0105230808258 seconds ---
for input of given grid of weights.
'''
And with that, we’re done. Prim’s Algorithm was more than efficient enough for a graph of degree 40. I may come back to this problem at some point to investigate the other well known algorithms for this problem. I apologize for skipping Project Euler Problem #106. Unfortunately, I have not solved it yet.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 