Saturday, April 2, 2011

Programming praxis

So I am going to start using this blog as a place to sharpen my programming skills in addition to trying to keep track of my projects. anyway I am using the website http://programmingpraxis.com/ to try and play with python. The problem for today looks rather interesting. http://programmingpraxis.com/2011/04/01/maximum-difference-in-an-array/ and while I haven't actually written any code yet it was an interesting thought exercise. At first I thought of course very simple solution just run through and keep track of the max and min, but of course it is not really that easy. I thought of the case
3236189
When you are iterating along the array and you are at the point of(let () be the current min and [] be the max) and then {} be the item you are looking at)
3(2)3[6]{1}89
At this point you have a 2 as the min and a 6 as the max so your total min-max = 4 and you are looking at the 1 which has the potential to be a better candidate.  However that depends on what comes after, if instead of 89 you had 34 then the 2,6 pair would be the best in the bunch. You need to know(or at least I thought) all of the later items to figure out the current item. So I thought well stink there is no clean solution(even thought the website mentioned that there was) and you are at best O(n^2) but as I thought further I realized that you could easily sort the array O(nln(n)) and then step through the original array and know what the future holds so you could evaluate the pair as you are on that item. That would give you O(nln(n) + n) which is of course O(nln(n) so even if you did a dumb way the did way more work than required you could do better then n^2 so I thought about it some more and I think I found the solution. Just a sec while I go write some code to verify that.

Ok here we go, now keep in mind I am not a python guy so I probably did not do things the python way. Sorry recovering c++ programmer here.

import random

class pair:
"Storing a pair of values and the magnitude of the difference"
def __init__(self, minimum, minIndex, maximum, maxIndex):
self.minimum = minimum
self.maximum = maximum
self.minIndex = minIndex
self.maxIndex = maxIndex

def magnitude(self):
return self.maximum - self.minimum

def updateMax(self, newMaximum, maxIndex):
if newMaximum > self.maximum:
self.maximum = newMaximum
self.maxIndex = maxIndex

def getMin(self):
return self.minimum

def getMax(self):
return self.maximum

def printResults(self):
return "The answer is %d at the index of %d with a maximum of %d at the index of %d" %(self.minimum, self.minIndex, self.maximum, self.maxIndex)

randList = []

for i in range(100):
randList.append(random.randint(0,100))

current = pair(randList[0], 0, randList[0], 0);
theory = pair(randList[0], 0, randList[0], 0);

for i in range(100):
current.updateMax(randList[i],i)
theory.updateMax(randList[i],i)
if theory.magnitude() > current.magnitude():
current = theory
if theory.getMin() > randList[i] :
theory = pair(randList[i], i, randList[i], i)


print current.printResults()
print theory.printResults()

No comments:

Post a Comment