## Saturday, June 25, 2011

### More Sample Programs

Sample 1 : Two sorted lists are given. We need to merge them and keep the merged list also in ascending order. Don't use sort/sorted functions.

def merge(a, b):
list1=a
list2=b
list3=[]

while len(list1) and len(list2):
if list1 < list2:
list3.append(list1.pop(0))
else:

list3.append(list2.pop(0))
list3.extend(list1)
list3.extend(list2)
return list3

def main():
assert(merge(, ) == [1,2])
assert(merge([10, 20], ) == [10, 20, 30])
assert(merge([10, 30, 40], [32, 33, 45, 57]) == [10,30,32,33,40,45,57])
assert(merge([20, 25, 27, 34], [1, 10, 23]) == [1,10,20,23,25,27,34])
assert(merge(, []) == )
assert(merge([], [1, 2]) == [1,2])
if __name__=='__main__':
main()

Sample 2 : Insert an integer number to the sorted list and keep the list in sorted order even after the insertion. Don't use sort/sorted functions.

def insert_into(a, n):
list1=a
if len(list1)==0:
list1=[n]
return list1
i=0
while i<len(list1):
if list1[i]>n:
list1.insert(i,n)
return list1
elif i==(len(list1)-1):
list1.append(n)
return list1
else:
i=i+1

def main():
assert(insert_into([10, 20, 30], 24) == [10,20,24,30])
assert(insert_into([5, 10, 20], 3) == [3,5,10,20])
assert(insert_into([1, 10, 20], 30) == [1,10,20,30])
assert(insert_into([], 10) == )
assert(insert_into([1, 4, 18, 24, 27, 35, 87], 19) == [1,4,18,19,24,27,35,87])
if __name__=='__main__':
main()

Sample 3 : This program is used to flatten the lists. i.e a list like this [1, [2, [3, ]]] will be flatten to a list [1,2,3,4].

def flatten(a):
main_list=a
lista=[]
for small_list in main_list:
if isinstance(small_list,list):
listb=flatten(small_list)
lista.extend(listb)
else:
lista.append(small_list)
return lista

def main():
assert(flatten([[1,[2,3]]]) == [1,2,3])
assert(flatten([[[1,2]]]) == [1, 2])
assert(flatten([[[]]]) == [])
assert(flatten([1, [2, [3, ]]]) == [1,2,3,4])
if __name__=='__main__':
main()

Sample 4 : We have to partition a given list into two lists based on the first element of the list. We will have two partitioned lists as output, one holds all elements that are lesser than the first element of the input list and the second list holds all elements that are greater than the first element of the input list.

def partition(a):
list1=a
list2=[]
list3=[]
list4=[]
for item in list1:
if item<list1:
list2.append(item)
elif item>list1:
list3.append(item)
list4=[list2]
list4.extend([list3])
return list4

def main():
assert(partition([10,8,2,11,14,6,1,13]) == [[8,2,6,1],[11,14,13]])
assert(partition([1,2,3,4]) == [[],[2,3,4]])
assert(partition() == [[],[]])
assert(partition([4,3,2,1]) == [[3,2,1],[]])
if __name__ == '__main__':
main()

Sample 5 : Here we have to define two functions. add() adds a key "k" with value "v" to dictionary "d". get() return value corresponding to key "k" or return None if key k is not present. Main objective is to simulate a dictionary using  a list.

if len(d)==0:
list1=[k,v]
d.append(list1)
return d
for lists in d:
if lists==k:
lists=v
return d
list1=[k,v]
d.append(list1)
return d

def get(d, k):
for lists in d:
if lists==k:
v=lists
return v
return None

def main():
assert(add([], "hello", 10) == [["hello", 10]])
assert(add([["hello", 10]], "world", 20) == [["hello", 10], ["world", 20]])
assert(get([["hello",10],["world",20]], "world") == 20)
assert(get([["abc",1],["def",2]], "ijk") == None)
if __name__=='__main__':
main()

I hope you will learn the basic concepts through these sample programs. You can also download these programs as a zip file. Download here.

Thanks

AJAY