This is the final code of my individual project from Algorithm class CSCI 3101 Hawaii Pacific University.
알고리듬 수업에서 수행한 개인 프로젝트의 결과물입니다.
Freckles – Skiena and Revilla Programming Challenges book.
알고리즘 트레이닝 북에 실린 주근깨 문제입니다.
I implemented Prim and Kruskal algorithms for this project with Python. See attached files on the bottom of this post if you need.
You are allowed to edit attached source codes, but please do not remove my name as an author on the top.
참고로, 한국에서 판매하는 책에 해답(C로 작성된 소스코드)이 실려있지만, 실제로 작성해서 컴파일/실행해본 결과 제대로 작동이 되질 않았습니다. 따라서, 이것을 필자가 파이썬으로 재작성했고, 프로젝트의 조건은 Prim과 Kruskal 두 개의 알고리즘으로 구현해야하는 것이었습니다. 소스코드는 첨부된 하단에 파일을 참고해주세요. 내용은 수정해도 되지만, 제 이름은 삭제하지 말아주세요.
The below is the problem from the book.
아래는 알고리즘 트레이닝 북에 실린 문제의 원문입니다.
In an episode of the Dick Van Dyke television show, Dick’s son Richie connects the freckles on his father’s back to form a picture of the Liberty Bell. Consider Dick’s back to be a plane with freckles at various (x, y) locations. Your job is to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.
대강 번역하자면, 아버지의 등에 나있는 주근깨들을 가장 가까운 주근깨로 한 번에 하나씩 연결하여 모든 주근깨를 연결하는 것입니다.
Input
The input begins with a single positive integer on a line by itself indicating the number of test cases, followed by a blank line.
The first line of each test case contains 0 < n <= 100, giving the number of freckles on Dick’s back. For each freckle, a line follows; each following line contains two real numbers indicating the (x, y) coordinates of the freckle.
Put a blank line between each two consecutive test cases.
Output
For each test case, your program must print a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles. The output of each two consecutive cases must be separated by a blank line.
Sample Input
3 1.0 1.0 2.0 2.0 2.0 4.0
Sample Output
3.41
———————————————————————————————————
My source codes
Prim:
#!/usr/bin/python
# -*- coding: UTF-8 -*-
"""
Class: CSCI 3101
Name: Seowon Jung
Professor: Yi Zhu
Filename: SeowonJung_Prim.py
Programming Project from Skienna and Revilla Programming Challenge book.
This script has been written with Python v2.7.1.
"""
import math, sys
# Declare a global variable
result = 0
searchedNode = 1
# Creat a class to store node and visited info into each object
# for each node
class Freckle:
def __init__(self, curX, curY, visited, distances, freckles):
self.x = curX # Current X-Coordinate
self.y = curY # Current Y-Coordinate
self.visitedList = [] # Store visited list
self.distances = [0]*(freckles+1) # Store all distances between current node and other nodes.
# Calculate distance between two nodes
def CalcDistance(currentNode, closestNode):
if closestNode == 0:
return 0
else:
dist = round(math.sqrt(pow(abs(float(node[currentNode].x) - float(node[closestNode].x)), 2) + pow(abs(float(node[currentNode].y) - float(node[closestNode].y)), 2)), 2)
return dist
# Create a visited list for a "starting node", which tries to connect.
# Search all nodes in a same group
def VisitedList(nodeInCurrentGroup):
global visitList
visitList = []
def visitedListFromAllSubNode(subNode):
global visitList
for nodeFS in node[subNode].visitedList:
if nodeFS in visitList:
visitList = list(set(visitList)) # Removing duplicated elements
elif nodeFS == nodeInCurrentGroup:
visitList = list(set(visitList))
else:
visitList.append(nodeFS)
visitedListFromAllSubNode(nodeFS)
for nodeF in node[nodeInCurrentGroup].visitedList:
visitList.append(nodeF)
visitedListFromAllSubNode(nodeF)
visitList = list(set(visitList))
return visitList
# Updated visited nodes list for each node to avoid being re-searched by the same closest node
def UpdateVisitedList(srcNode, destNode):
node[srcNode].visitedList.append(destNode)
node[destNode].visitedList.append(srcNode)
# Remove duplicated nodes
node[srcNode].visitedList = list(set(node[srcNode].visitedList))
node[destNode].visitedList = list(set(node[destNode].visitedList))
# Cycle test, True/False
def CycleTest(srcNode, destNode):
srcVisitedList = VisitedList(srcNode)
destVisitedList = VisitedList(destNode)
cycleMagicVar = False
for magicNode in srcVisitedList:
if magicNode in destVisitedList:
cycleMagicVar = True
break
return cycleMagicVar
def nodeLocationShortestDistance(distanceList):
# To avoid an error that searches a minimum value except zero if the distanceList has all zero value,
# which means, there is a no more closest node.
zeroCheck = 0
for i in distanceList:
if i > 0:
zeroCheck += 1
if zeroCheck > 0:
dist = min([x for x in distanceList if not x ==0])
location = distanceList.index(dist)
return dist, location
else:
return 0, 0
def prim(currentNodesList):
#print '\n', currentNodesList, '------------------------------------'
global result
# To avoid an infinite loop
if len(currentNodesList) == freckles:
print 'No more node'
print 'Prim: ', result
sys.exit(0)
# Create a dictionary for storing the shortest path and both node
# numbers on an edge for each node.
tempDistanceList = {}
# Calculate the shortest path from current nodes list
for eachNode in currentNodesList:
for i in range(1, freckles+1, 1):
# If a node which needs to be investigated is in a visited list,
# a distance will be zero to avoid re-searching
if i in node[eachNode].visitedList:
node[eachNode].distances[i] = 0
else:
node[eachNode].distances[i] = CalcDistance(eachNode, i)
#print eachNode, ': ', node[eachNode].distances
dist, location = nodeLocationShortestDistance(node[eachNode].distances)
#print '\tdist: ', dist, ', location: ', location
tempDistanceList[dist] = [eachNode,location]
#print "List: ", tempDistanceList
# To figure out whether no more shortest path exists or not
zeroCheck = 0
for i in tempDistanceList.keys():
if i > 0:
zeroCheck += 1
if zeroCheck > 0:
# If the minimum value except zero exists
minValue = min([x for x in tempDistanceList.keys() if not x == 0])
minEdge = tempDistanceList.get(minValue)
else:
print 'No more node'
print 'Prim: ', result
sys.exit(0)
del zeroCheck
# Cycle test
if CycleTest(minEdge[0], minEdge[1]) == True:
UpdateVisitedList(minEdge[0], minEdge[1])
prim(currentNodesList)
else:
# Update visited list for both nodes on the edge
UpdateVisitedList(minEdge[0], minEdge[1])
result += minValue
print 'Min value: ', minValue, ', Min edge: ', minEdge, ', Result: ', result
# Add both nodes on the edge to the investigating list
currentNodesList.append(minEdge[0])
currentNodesList.append(minEdge[1])
# Remove duplicated nodes
currentNodesList = list(set(currentNodesList))
prim(currentNodesList)
def main():
# Sample cases for testing
A = ['407.00 805.00','514.00 603.00','974.00 666.00','100.00 129.00','733.00 704.00','266.00 607.00','973.00 602.00','242.00 94.00','538.00 296.00','284.00 466.00','584.00 447.00','580.00 81.00','380.00 57.00','344.00 906.00','207.00 989.00','45.00 778.00','794.00 723.00','545.00 769.00','553.00 646.00','62.00 286.00','515.00 328.00','57.00 488.00','95.00 300.00','582.00 633.00','597.00 867.00','263.00 181.00','477.00 7.00','426.00 22.00','228.00 934.00','929.00 435.00','923.00 974.00','377.00 882.00','698.00 923.00','651.00 415.00','570.00 877.00','701.00 249.00','369.00 758.00','737.00 464.00','222.00 483.00','98.00 819.00','514.00 525.00','164.00 992.00','532.00 754.00','14.00 761.00','688.00 943.00','360.00 612.00','82.00 737.00','658.00 944.00','661.00 310.00','359.00 395.00','187.00 224.00','644.00 557.00','146.00 545.00','186.00 368.00','29.00 448.00','351.00 706.00','973.00 679.00','699.00 669.00','433.00 877.00','594.00 121.00','984.00 954.00','897.00 67.00','856.00 555.00','175.00 681.00','29.00 697.00','76.00 380.00','85.00 884.00','101.00 395.00','593.00 288.00','763.00 786.00','736.00 278.00','492.00 873.00','957.00 355.00','543.00 554.00','233.00 138.00','676.00 218.00','256.00 737.00','448.00 113.00','293.00 787.00','794.00 486.00','485.00 34.00','867.00 734.00','82.00 132.00','129.00 676.00','420.00 56.00','626.00 320.00','334.00 118.00','193.00 455.00','474.00 900.00','9.00 871.00','38.00 849.00','89.00 458.00','586.00 701.00','571.00 879.00','488.00 529.00','529.00 137.00','728.00 396.00','871.00 810.00','529.00 164.00','650.00 113.00'] # A: 6658.39
B = ['1.4 0.4', '1.0 0.3'] # B: 0.41
C = ['3.4 5.0'] # C: 0
D = ['4.2 1.6', '0.3 4.6', '6.2 0.0', '8.9 6.8', '3.9 6.7', '6.0 3.3', '9.7 7.4', '1.5 0.7', '6.5 8.9', '2.1 3.0'] # D: 23.94
E = ['6.6 7.3'] # E: 0
F = ['8.0 3.2', '0.9 9.7', '6.8 7.6', '8.9 2.1', '9.6 6.0', '8.6 6.2', '6.4 9.1', '5.0 8.8', '3.1 1.8'] # F: 20.06
G = ['4.0 7.7', '4.4 1.7', '8.3 2.0', '1.8 8.2', '2.8 7.0', '2.4 2.2', '4.4 0.1', '7.9 2.4', '7.3 6.2'] # G: 18.22
H = ['0.6 4.0', '9.1 8.5'] # H: 9.62
I = ['8.0 3.4', '7.7 5.4', '7.7 4.6', '9.9 0.3', '8.7 6.9', '3.4 1.6'] # I: 12.42
J = ['6.7 7.5'] # J: 0
K = ['9.1 0.8', '8.0 9.0', '9.0 9.1', '7.5 5.1'] # K: 9.52
L = ['1.0 1.0', '2.0 2.0', '2.0 4.0'] # L: # 3.41
sampleInput = A
# Declare variables and matrix
maxNum = 101
# Create a list for nodes filled up with 0
global node, freckles
node = [0]*maxNum
# Get an input for the number of test case
# testCase = input('How many test cases: ')
testCase = 1
# Just enter
# raw_input('')
for x in range(1, testCase+1, 1):
print "Case #"+str(x)+"----------------"
# freckles = input('How many freckles: ')
freckles = len(sampleInput)
for i in range(1, freckles+1, 1):
# dots_raw = raw_input('Two real numbers for X and Y coodinates #'+str(i)+': ')
dots_raw = sampleInput[i-1]
# Split input to x and y node by a blank token
dots = dots_raw.strip().split(" ")
node[i] = Freckle(dots[0], dots[1], None, None, freckles)
prim([1])
print "\n\nPrim: "+str(result)
#print visitedNodeList
if(x > 0):
print "\n"
print '\n'
if __name__ == "__main__":
main()
Kruskal:
#!/usr/bin/python
# -*- coding: UTF-8 -*-
"""
Class: CSCI 3101
Name: Seowon Jung
Professor: Yi Zhu
Filename: SeowonJung_Kruskal.py
Programming Project from Skienna and Revilla Programming Challenge book.
This script has been written and worked with Python v2.7.1.
"""
import math, operator, sys
# Declare a global variable
result = 0
# Creat a class to store node and visited info into each object
# for each node
class Freckle:
def __init__(self, curX, curY, closest, dist, visited):
self.x = curX # Current X-Coordinate
self.y = curY # Current Y-Coordinate
self.visitedList = [] # Store visited list
# Calculate distance between two nodes
def calcDistance(currentNode, closestNode):
if closestNode == 0:
return 0
else:
dist = round(math.sqrt(pow(abs(float(node[currentNode].x) - float(node[closestNode].x)), 2) + pow(abs(float(node[currentNode].y) - float(node[closestNode].y)), 2)), 2)
# print "calcDistance--------- currentNode: "+str(currentNode)+"\tClosestNode: "+str(closestNode)+"\tDistance: "+str(dist)
return dist
# This function returns two values - a closest distance and its a node
def nodeLocationShortestDistance(distanceList):
# To avoid an error that searches a minimum value except zero if the distanceList has all zero value,
# which means, there is a no more closest node.
zeroCheck = 0
for i in distanceList:
if i > 0:
zeroCheck += 1
if zeroCheck > 0:
dist = min([x for x in distanceList if not x ==0])
location = distanceList.index(dist)
return dist, location
else:
return 0, 0
# This function removes two-way closest path in the list.
def removeTwoWayNode(shortest):
for j in range(1, freckles+1, 1):
if j in shortest:
if shortest[j][1] in shortest:
if j == shortest[shortest[j][1]][1]:
#print j, ': ', shortest[j], ', ', shortest[j][1], 'deleted'
del shortest[shortest[j][1]]
return shortest
# Create a visited list for a "starting node", which tries to connect
# Search all nodes in a same group
def visitedListFrom(nodeFrom):
global fromVisitList
def visitedListFromAllSubNode(subNode):
global fromVisitList
for nodeFS in node[subNode].visitedList:
if nodeFS in fromVisitList:
fromVisitList = list(set(fromVisitList))
elif nodeFS == nodeFrom:
fromVisitList = list(set(fromVisitList))
else:
fromVisitList.append(nodeFS)
visitedListFromAllSubNode(nodeFS)
for nodeF in node[nodeFrom].visitedList:
fromVisitList.append(nodeF)
visitedListFromAllSubNode(nodeF)
fromVisitList = list(set(fromVisitList))
return fromVisitList
# Create a visited list for a "ending node", which is a destination
# Search all nodes in a same group
def visitedListTo(nodeTo):
global destVisitList
def visitedListToAllSubNode(subNode):
global destVisitList
for nodeDS in node[subNode].visitedList:
if nodeDS in destVisitList:
destVisitList = list(set(destVisitList))
elif nodeDS == nodeTo:
destVisitList = list(set(destVisitList))
else:
destVisitList.append(nodeDS)
visitedListToAllSubNode(nodeDS)
for nodeD in node[nodeTo].visitedList:
destVisitList.append(nodeD)
visitedListToAllSubNode(nodeD)
destVisitList = list(set(destVisitList))
return destVisitList
# Updated visited node list for each node to avoid re-search its the same closest node
def updateVisitedList(srcNode, destNode):
node[srcNode].visitedList.append(destNode)
node[destNode].visitedList.append(srcNode)
def kruskal():
global result
shortest = {}
# Calculate all distances for each node
for i in range(1, freckles+1, 1): # From
tempDistanceList = [0]*(freckles+1)
for j in range(1, freckles+1, 1): # To
tempDistanceList[j] = calcDistance(i, j)
# Closest node number and its distance
dist, location = nodeLocationShortestDistance(tempDistanceList)
if dist == 0 and location == 0:
# print "No more closest node"
print "Kruskal: ", result
sys.exit(0)
else:
shortest[i] = [dist, location]
# print i, ": ", " Distance: ", shortest[i][0], ", Closest node: ", shortest[i][1]
del tempDistanceList
# Remove two-way nodes
shortest = removeTwoWayNode(shortest)
# print '\nBefore sort: ', shortest
# print shortest
# Sort the shortest list by distances
shortest = sorted(shortest.iteritems(), key=operator.itemgetter(1))
# print '\nAfter sort: ', shortest, '\n'
# Link nodes!!! - Initial
for each in shortest:
# each[0] = From
node[each[0]].visitedList.append(each[1][1]) # Closest node
# Add the current node into the Closest Node's visit list.
# Because, the shortest distance and closest node are same each other.
# Therefore, all nodes are connected
node[each[1][1]].visitedList.append(each[0])
# Calculate the total length.
result += each[1][0]
print 'Link ', each[0], ' -> ', each[1][1], ",\t", each[1][0], node[each[0]].visitedList
# print ''
# Delete shortest list to be used for second closest node
del shortest
# This function is for searching next connections after the initial connection.
# This function finds the next closest node and then do cycle-test. If it is OK, then it connects to the node.
# But, if it is a cycle, it updates each node's visited list, and then re-create a distance list for each node.
# And then do cycle-test
def findAnotherClosestNode():
global result
shortest = {}
# Next closest node for all single node in order to figure out whether another closest node exists or not.
# Create a distance list except the linked shortest node
for i in range(1, freckles+1, 1):
tempDistanceList = [0]*(freckles+1)
for j in range(1, freckles+1, 1):
if j in node[i].visitedList:
tempDistanceList[j] = 0
else:
tempDistanceList[j] = calcDistance(i, j)
# Closest node number and its distance
dist, location = nodeLocationShortestDistance(tempDistanceList)
# If closest distance and node number are empty, it's done.
if dist == 0 and location == 0:
# print "No more closest node"
print "Kruskal: ", result
sys.exit(0)
else:
dist, location = nodeLocationShortestDistance(tempDistanceList)
shortest[i] = [dist, location]
# print i, ": ", " Distance: ", shortest[i][0], ", Closest node: ", shortest[i][1]
# To avoid duplicated distances and locations
del tempDistanceList
# print shortest
# Remove two-way nodes
shortest = removeTwoWayNode(shortest)
# Sort in ascending order
shortest = sorted(shortest.iteritems(), key=operator.itemgetter(1))
# print '\nAfter sort: ', shortest, '\n'
cycleMagicNum = False # For figure out a destination node is a cycle or not
# Cycle test
for each in shortest:
# each[0] = Source node
# each[1][1] = Destination node
# If the destination node's visited list has at least one same element in the From node's visited list, it's cyclic
# Create a list for storing visited nodes
global fromVisitList, destVisitList
fromVisitList = []
destVisitList = []
# print each[0],' ---------------------------------------------------'
# A visit list for a source node
fromVisitList = visitedListFrom(each[0])
# A visit list for a destination
destVisitList = visitedListTo(each[1][1])
# print 'From visit list: '#,fromVisitList
# print 'Dest visit list: '#,destVisitList
# Test that the source and destination nodes have at least one common node
for nodeCycle in fromVisitList:
if nodeCycle in destVisitList:
# print '\t\tIt is a cycle, ', each[0], ' -> ', each[1][1]
# print ''
# print '\t\t', each[0], ': ', node[each[0]].visitedList, ', ', each[1][1], ': ', node[each[1][1]].visitedList
# Update visited list for both source and destination nodes to avoid including the distance list
updateVisitedList(each[0], each[1][1])
# print '\t\t', each[0], ': ', node[each[0]].visitedList, ', ', each[1][1], ': ', node[each[1][1]].visitedList
cycleMagicNum = True
break
# If no cycle found, link this node!
if not cycleMagicNum == True:
updateVisitedList(each[0], each[1][1])
print 'Added: ', each[1][1],' -> ', each[0], '\tResult: ', result
result += each[1][0]
# print ''
# To create new lists every loop
del fromVisitList, destVisitList
return cycleMagicNum
for i in range(1, freckles+1, 1):
# print i, ' ---------------------------------------------'
findAnotherClosestNode()
def main():
A = ['407.00 805.00','514.00 603.00','974.00 666.00','100.00 129.00','733.00 704.00','266.00 607.00','973.00 602.00','242.00 94.00','538.00 296.00','284.00 466.00','584.00 447.00','580.00 81.00','380.00 57.00','344.00 906.00','207.00 989.00','45.00 778.00','794.00 723.00','545.00 769.00','553.00 646.00','62.00 286.00','515.00 328.00','57.00 488.00','95.00 300.00','582.00 633.00','597.00 867.00','263.00 181.00','477.00 7.00','426.00 22.00','228.00 934.00','929.00 435.00','923.00 974.00','377.00 882.00','698.00 923.00','651.00 415.00','570.00 877.00','701.00 249.00','369.00 758.00','737.00 464.00','222.00 483.00','98.00 819.00','514.00 525.00','164.00 992.00','532.00 754.00','14.00 761.00','688.00 943.00','360.00 612.00','82.00 737.00','658.00 944.00','661.00 310.00','359.00 395.00','187.00 224.00','644.00 557.00','146.00 545.00','186.00 368.00','29.00 448.00','351.00 706.00','973.00 679.00','699.00 669.00','433.00 877.00','594.00 121.00','984.00 954.00','897.00 67.00','856.00 555.00','175.00 681.00','29.00 697.00','76.00 380.00','85.00 884.00','101.00 395.00','593.00 288.00','763.00 786.00','736.00 278.00','492.00 873.00','957.00 355.00','543.00 554.00','233.00 138.00','676.00 218.00','256.00 737.00','448.00 113.00','293.00 787.00','794.00 486.00','485.00 34.00','867.00 734.00','82.00 132.00','129.00 676.00','420.00 56.00','626.00 320.00','334.00 118.00','193.00 455.00','474.00 900.00','9.00 871.00','38.00 849.00','89.00 458.00','586.00 701.00','571.00 879.00','488.00 529.00','529.00 137.00','728.00 396.00','871.00 810.00','529.00 164.00','650.00 113.00'] # A: 6658.39
B = ['1.4 0.4', '1.0 0.3'] # B: 0.41
C = ['3.4 5.0'] # C: 0
D = ['4.2 1.6', '0.3 4.6', '6.2 0.0', '8.9 6.8', '3.9 6.7', '6.0 3.3', '9.7 7.4', '1.5 0.7', '6.5 8.9', '2.1 3.0'] # D: 23.94
E = ['6.6 7.3'] # E: 0
F = ['8.0 3.2', '0.9 9.7', '6.8 7.6', '8.9 2.1', '9.6 6.0', '8.6 6.2', '6.4 9.1', '5.0 8.8', '3.1 1.8'] # F: 20.06
G = ['4.0 7.7', '4.4 1.7', '8.3 2.0', '1.8 8.2', '2.8 7.0', '2.4 2.2', '4.4 0.1', '7.9 2.4', '7.3 6.2'] # G: 18.22
H = ['0.6 4.0', '9.1 8.5'] # H: 9.62
I = ['8.0 3.4', '7.7 5.4', '7.7 4.6', '9.9 0.3', '8.7 6.9', '3.4 1.6'] # I: 12.42
J = ['6.7 7.5'] # J: 0
K = ['9.1 0.8', '8.0 9.0', '9.0 9.1', '7.5 5.1'] # K: 9.52
L = ['1.0 1.0', '2.0 2.0', '2.0 4.0'] # L: 3.41
sampleInput = D
# Declare a variable for total number. First location in the list [0] won't be used.
maxNum = 101
# All node and a number of freckles need to be global variables.
global node, freckles
node = [0]*maxNum
# Get an input for the number of test case
# testCase = input('How many test cases: ')
testCase = 1
# Just enter
# raw_input('')
for x in range(1, testCase+1, 1):
print "Case #"+str(x)+"----------------"
# freckles = input('How many freckles: ')
freckles = len(sampleInput)
for i in range(1, freckles+1, 1):
# dots_raw = raw_input('Two real numbers for X and Y coodinates #'+str(i)+': ')
dots_raw = sampleInput[i-1]
# Split input to x and y node by a blank token
dots = dots_raw.strip().split(" ")
node[i] = Freckle(dots[0], dots[1], None, None, None)
kruskal()
print "\n\nKruskal: "+str(result)
if(x > 0):
print "\n"
print '\n'
if __name__ == "__main__":
main()
Leave a Reply