#solves Towers of Hanoi puzzle
def doTowers(topN, src, inter, dest):
if topN == 1: #display
print 'Disk 1 from', src, 'to', dest
else:
doTowers(topN - 1, src, dest, inter) #src to inter
print 'Disk', topN, 'from', src, 'to', dest #display
doTowers(topN - 1, inter, src, dest) #inter to dest
nDisks = int(raw_input('Enter number of disks: ')) #get # of disks
doTowers(nDisks, 'A', 'B', 'C') #solve iter
#demonstrates merging two arrays into a third
from pylab import array
def merge(arrayA, sizeA, arrayB, sizeB, arrayC): #merge A and B into C
aDex = 0
bDex = 0
cDex = 0
while aDex < sizeA and bDex < sizeB: #neither array empty
if arrayA[aDex] < arrayB[bDex]:
arrayC[cDex] = arrayA[aDex]
cDex += 1
aDex += 1
else:
arrayC[cDex] = arrayB[bDex]
cDex += 1
bDex += 1
while aDex < sizeA: #arrayB is empty,
arrayC[cDex] = arrayA[aDex] #but arrayA isn't
cDex += 1
aDex += 1
while bDex < sizeB: #arrayA is empty,
arrayC[cDex] = arrayB[bDex] #but arrayB isn't
cDex += 1
bDex += 1
def display(theArray, size): #display array
print theArray
arrayA = array([23, 47, 81, 95]) #source A
arrayB = array([7, 14, 39, 55, 62, 74]) #source B
arrayC = array([None] * 10) #destination
merge(arrayA, 4, arrayB, 6, arrayC) #merge A+B-->C
display(arrayC, 10) #display result
#end
def recMergeSort(workSpace, lowerBound, upperBound):
if lowerBound == upperBound: #if range is 1,
return #no use sorting
else:
#find midpoint
mid = (lowerBound + upperBound) / 2
#sort low half
recMergeSort(workSpace, lowerBound, mid)
#sort high half
recMergeSort(workSpace, mid + 1, upperBound)
#merge them
merge(workSpace, lowerBound, mid + 1, upperBound)
#end else
#end recMergeSort()
#demonstrates recursive merge sort
from pylab import array
class DArray:
def __init__(self, max): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._theVect = array([None] * max) #array of Nones
self._nElems = 0 #number of data items
def _recMergeSort(self, workSpace, lowerBound, upperBound):
if lowerBound == upperBound: #if range is 1,
return #no use sorting
else:
#find midpoint
mid = (lowerBound + upperBound) / 2
#sort low half
self._recMergeSort(workSpace, lowerBound, mid)
#sort high half
self._recMergeSort(workSpace, mid + 1, upperBound)
#merge them
self._merge(workSpace, lowerBound, mid + 1, upperBound)
#end else
#end _recMergeSort()
def _merge(self, workSpace, lowPtr, highPtr, upperBound):
j = 0 #workspace index
lowerBound = lowPtr
mid = highPtr - 1
n = upperBound - lowerBound + 1## of items
while lowPtr <= mid and highPtr <= upperBound:
if self._theVect[lowPtr] < self._theVect[highPtr]:
workSpace[j] = self._theVect[lowPtr]
j += 1
lowPtr += 1
else:
workSpace[j] = self._theVect[highPtr]
j += 1
highPtr += 1
while lowPtr <= mid:
workSpace[j] = self._theVect[lowPtr]
j += 1
lowPtr += 1
while highPtr <= upperBound:
workSpace[j] = self._theVect[highPtr]
j += 1
highPtr += 1
for j in xrange(n):
self._theVect[lowerBound + j] = workSpace[j]
#end _merge()
def insert(self, value): #put element into array
self._theVect[self._nElems] = value #insert it
self._nElems += 1#increment size
def display(self): #display array contents
for j in xrange(self._nElems): #for each element,
print self._theVect[j], #display it
print
def mergeSort(self): #called by main()
#provides workspace
workSpace = array([None] * self._nElems)
self._recMergeSort(workSpace, 0, self._nElems - 1)
#end class DArray
maxSize = 100 #array size
arr = DArray(maxSize) #create 'array'
arr.insert(64) #insert items
arr.insert(21)
arr.insert(33)
arr.insert(70)
arr.insert(12)
arr.insert(85)
arr.insert(44)
arr.insert(3)
arr.insert(99)
arr.insert(0)
arr.insert(108)
arr.insert(36)
arr.display() #display items
arr.mergeSort() #merge sort the array
arr.display() #display items again
#end