### python exercise

##################################
#####    random exercises    #####
##################################

###
###  subsequence check
###

---------------------------------
def subseqCheck(a,b):  # is b a seubsequence of a?
j = 0
for i in a:
if i == b[j]:
j += 1
if j == len(b):
return True
return False
---------------------------------

###
###  fibonacci
###

------------------------------------

#  fibonacci with recursion

def fiboRec(n):
if n == 1 or n == 2:
return 1
else:
return fiboRec(n-1) + fiboRec(n-2)

#  fibonacci with iteration

def fiboIte(n):
fib = [1,1]
if n == 1 or n == 2:
return 1
for i in range(2,n):
fib.append(fib[i-1] + fib[i-2])
return fib.pop()

print fiboRec(5)
print fiboIte(6)

-----------------------------------

###
###  singly linked list; loop detection demo
###

-----------------------------------
#!/usr/bin/python

class node:
def __init__(self,data):
self.next = None
self.data = data

class LL:
def __init__(self):
self.tail = None
else:
self.tail.next = node(data)
self.tail = self.tail.next
def printLL(self):
while tmp != None:
print tmp.data
tmp = tmp.next

def detectLoop1(ll):  # keep track of visited nodes, so when any reappears, it is a loop
visited = []      # time O(n) is ok, but auxiliary space O(n) can be a problem

while tmp != None:
if visited.count(tmp):
return True
visited.append(tmp)
tmp = tmp.next

return False

def detectLoop2(ll):  # slow iterater iterates one by one, fast iterator iterates every second node
# in theory, fastItr will catch up with slowItr if any loop
# time O(n), and auxiliary space(1) in that regard this is a better version.

while(slowItr != None and fastItr != None):
if fastItr.next == None:
break
fastItr = fastItr.next.next
slowItr = slowItr.next
if slowItr == fastItr:
return True

return False

if __name__ == "__main__":

ll = LL()
ll.printLL()             #  foo-bar-yen-pen

# lets test two functions

print detectLoop1(ll)    # False
print detectLoop2(ll)    # False

ll.tail.next = ll.head.next   #  lets connect "pen"->"bar" thus causing an infinite loop

#    ll.printLL()    # inifite loop

print detectLoop1(ll)    # True
print detectLoop2(ll)    # True

------------------------------------------------------------

###
###  rotate the elements of an array by k pos
###

##  (a typical interview question)  #(ref)  http://leetcode.com/2010/04/rotating-array-in-place.html

-----------------------------------------------------// rotateArr.py
def reverseElem(array,begin,end):
if begin == end: # one elem array, nothing to do
return array
size = end - begin + 1
for i in range(size/2):
array[begin+i] = array[begin+i] + array[end-i]
array[end-i] = array[begin+i] - array[end-i]
array[begin+i] = array[begin+i] - array[end-i]
return array

array = [1,2,3,4,5]
k = 3

array = reverseElem(array,0,len(array)-1)
array = reverseElem(array,k,len(array)-1)
array = reverseElem(array,0,k-1)

print array

------------------------------------------------------//

##
## There is a sorted array of integers. rotate it by N index positions. write a function to determine N.
##

# e.g.
rotatedList = [3,4,5,1,2]    # n = 3

# O(n) ver.
def findRotationCount(rotatedList):
min = rotatedList[0]
idx = -1
prev = -1
for i in range(len(rotatedList)):
if prev > rotatedList[i]:
idx = i
break
if min > rotatedList[i]:
min = rotatedList[i]
idx = i
prev = rotatedList[i]
return idx

# O(log n) ver.
def findRotationCount2(rotatedList,begin,end):
if end == -1:
print "empty list"
return -1
if begin == end:  # single elem array
return 0
# if only two elem, the latter's idx is n (assuming the ascending order in the original array)
if begin == (end-1):
if(rotatedList[begin] == rotatedList[end]): # just a special case where every elem in the array is the same val
return 0
return end
mid = (end+begin)/2
if rotatedList[begin] <= rotatedList[mid]:
return findRotationCount2(rotatedList,mid,end)
elif rotatedList[begin] > rotatedList[mid]:
return findRotationCount2(rotatedList,begin,mid)

print findRotationCount(rotatedList)                        # 3
print findRotationCount2(rotatedList,0,len(rotatedList)-1)  # 3

##
##  given a sorted array of integers. rotate it by N index positions.
##  Now write a function to sort it in O(n) in-place.
##

# just combines solutions from the prev two questions.

--------------------------------------------------

def rotateBackToSorted(rotatedList):
size = len(rotatedList)
idx = findRotationCount2(rotatedList,0,size-1)
rotatedList = reverseElem(rotatedList,0,idx-1)
rotatedList = reverseElem(rotatedList,idx,size-1)
rotatedList = reverseElem(rotatedList,0,size-1)
return rotatedList

print rotateBackToSorted(rotatedList)

--------------------------------------------------

###
###  self-printing code
###

demonstrates "recursion theorem" from computation theory.

Th: Let T be a Turing machine that computes a function t: Z*,Z* -> Z*
There is a Turing machine R that computes a function r: Z* -> Z*, where for every w,
r(w) = t(<R>,w)

many examples on the web. here is a python example.

-----------quine.py--------------
s = "print \"s = \\\"\"+s.replace(\"\\\\\",\"\\\\\\\\\").replace(\"\\\"\",\"\\\\\\\"\")+\"\\\"\"+\"\\n\"+s"
print "s = \""+s.replace("\\","\\\\").replace("\"","\\\"")+"\""+"\n"+s
---------------------------------

Essentially the string defines the program core while the program core prints the string and the rest of the code (which may include header, footer, variable declaration, etc). Notice we print the string twice, first time for the string definition itself, and the second time for printing the program core itself which is defined in the string. The only tricky part is taking care of escape characters, which is the source of the headache as shown above. There are many more elegant examples on the web that makes use of each language's builtin functions, etc.

###
###  vwap calc
###

def calc_vwap(filename):   # suppose an input csv file with ticker,px,qty,ts   # ts = timestamp
ticker2data = {}        # that contains a whole day tick history
with open(infile, 'r') as infile:
while(True):
if line == "\n":
continue
elif line == '':  # EOF
break
[ticker,px,qty,ts] = line.strip(',')
if ticker not in ticker2data.keys():
ticker2data[ticker] = {}
ticker2data[ticker][vwap] = 0
ticker2data[ticker][mktcap] = 0
ticker2data[ticker][cumqty] = 0
ticker2data[ticker][mktcap] += px * qty
ticker2data[ticker][cumqty] += qty
ticker2data[ticker][vwap] = ticker2data[ticker][mktcap] / ticker2data[ticker][cumqty]
for t in ticker2data.keys():
print(t,':'ticker2data[t][vwap])   # EOD vwap

###
###  twap
###

def calc_twap(filename):   # suppose an input csv file with ticker,px,qty,ts   # ts = timestamp
ticker2data = {}        # that contains a whole day tick history
with open(infile, 'r') as infile:
while(True):
if line == "\n":
continue
elif line == '':  # EOF
break
[ticker,px,qty,ts] = line.strip(',')
if ticker not in ticker2data.keys():
ticker2data[ticker] = {}
ticker2data[ticker][twap] = 0
ticker2data[ticker][sumup] = 0
ticker2data[ticker][sumts] = 0
ticker2data[ticker][prevpx] = 0
ticker2data[ticker][prevts] = 0
ticker2data[ticker][sumup] = ticker2data[ticker][prevpx] * (ts - ticker2data[ticker][prevts])
ticker2data[ticker][sumts] += (ts - ticker2data[ticker][prevts])
ticker2data[ticker][prevpx] = px
ticker2data[ticker][prevts] = ts
ticker2data[ticker][twap] = ticker2data[ticker][sumup] / ticker2data[ticker][sumts]