COSC 130 - Homework 05

Kyle Anderson

In [3]:
import random

Problem 1: Argument Sort

In [4]:
def argsort(x, reverse=False):
    tuples = [(element, index) for index, element in enumerate(x, 0)]
    tuples = sorted(tuples, reverse=reverse)
    indices = [item[1] for item in tuples]
    return indices
In [5]:
list1 = [76, 81, 30, 47, 50, 18, 23, 49]
print(argsort(list1))

[5, 6, 2, 3, 7, 4, 0, 1]
In [6]:
list2 = ['Chad', 'Beth', 'Emma', 'Alex', 'Drew', 'Fred']
print(argsort(list2, True))

[5, 2, 4, 0, 1, 3]

Problem 2: Process Lines of Text

In [7]:
def process_line(line,schema,sep):
    tokens = line.split(sep)
    result = []
    for i in range(len(tokens)):
        t = tokens[i]
        dt = schema[i]
        result.append(dt(t))
    return result
In [8]:
def main():
    test_line = '6,174,Blah,Hello World,7.37'
    test_schema = [int,int,str,str,float]
    print(process_line(test_line,test_schema,','))

if __name__== "__main__":
    main()

[6, 174, 'Blah', 'Hello World', 7.37]

Problem 3: Processing File Input

In [9]:
def process_lines(lines,j,schema,sep):
    index=0
    lst=[]
    for element in lines[j].split(sep):
        if schema[index]==str:
            lst.append(str(element))
        elif schema[index]==int:
            lst.append(int(element))
        else:
            lst.append(float(element)) 
        index=index+1
    return lst

def read_file_to_list(path,schema ,sep):
    f=open(path, "r")
    contents =f.read()
    lines = contents.split('\n')
    data=[]
    header = lines[0].split(sep)
    data.append(header)
    for j in range(1,len(lines)):
        lst = process_lines(lines,j,schema,sep)
        data.append(lst)
    return(data)
In [10]:
my_schema=[int,int,str,str,int,float]
data = read_file_to_list("titanic_partial.txt",my_schema,sep='\t')
for i in data:
    print(i)

['Survived', 'Pclass', 'Name', 'Sex', 'Age', 'Fare']
[0, 3, 'Mr. Owen Harris Braund', 'male', 22, 7.25]
[1, 3, 'Miss. Laina Heikkinen', 'female', 26, 7.925]
[1, 2, 'Mrs. Nicholas Nasser', 'female', 14, 30.0708]
[1, 3, 'Miss. Marguerite Rut Sandstrom', 'female', 4, 16.7]
[1, 1, 'Miss. Elizabeth Bonnell', 'female', 58, 26.55]
[0, 3, 'Mr. William Henry Saundercock', 'male', 20, 8.05]
[0, 3, 'Mr. Anders Johan Andersson', 'male', 39, 31.275]
[0, 3, 'Miss. Hulda Amanda Adolfina Vestrom', 'female', 14, 7.8542]
[0, 3, 'Master. Eugene Rice', 'male', 2, 29.125]
[1, 2, 'Mr. Charles Eugene Williams', 'male', 23, 13.0]
In [11]:
my_schema=[float,str,str,str,int]
data = read_file_to_list("diamonds_partial.txt",my_schema,',')
for i in data:
    print(i)

['carat', 'cut', 'color', 'clarity', 'price']
[0.36, 'Ideal', 'E', 'VS2', 1013]
[0.3, 'Fair', 'J', 'VS2', 416]
[1.22, 'Ideal', 'H', 'SI1', 6541]
[0.48, 'Good', 'G', 'SI1', 914]
[0.75, 'Ideal', 'J', 'VS1', 2300]
[0.31, 'Premium', 'H', 'VVS2', 802]
[2.48, 'Very Good', 'H', 'SI2', 15746]
[1.0, 'Good', 'D', 'SI1', 5469]
[0.51, 'Very Good', 'F', 'VS1', 1627]

Problem 4: Recursive Product

In [12]:
def recursive_product(x):
    if len(x) == 1:
        return x[0]
    else:
        temp = recursive_product(x[1:])
        return temp * x[0]
In [13]:
factors = [11, 8, 17, 9, 18, 10]
print(recursive_product(factors))

2423520

Problem 5: Greatest Common Divisor

In [14]:
import random

def gcd(m, n):
    if m < n:
        return gcd(n, m)
    elif n == 0:
        return m
    else:
        return gcd(n, m % n)
In [15]:
print(gcd(72, 300))
print(gcd(180, 210))
print(gcd(20, 400))
print(gcd(30, 77))

12
30
20
1

Problem 6: Flattening Nested Lists

In [16]:
def flatten(nestedList):
    if nestedList == []:
        return nestedList

    if isinstance(nestedList[0], list):
        return flatten(*nestedList[:1]) + flatten(nestedList[1:])
    return nestedList[:1] + flatten(nestedList[1:])

nestedList = [1, [8, [5, 6, [4, 9]]], [7, 2, 3]]
print(flatten(nestedList))

[1, 8, 5, 6, 4, 9, 7, 2, 3]
In [17]:
def flatten(x):
        flat_list = []
        for i in x:
                if type(i) is list:
                        flat_list = flat_list + flatten(i)
                else:
                        flat_list.append(i)
        return flat_list

nested_list = [1, [8, [5, 6, [4, 9]]], [7, 2, 3]]
a = [1,[2],[3]]
b = [1,[2],[[4,5],6]]
print(flatten(nested_list))
print(flatten(a))
print(flatten(b))

[1, 8, 5, 6, 4, 9, 7, 2, 3]
[1, 2, 3]
[1, 2, 4, 5, 6]
In [18]:
def binary_search(x, item):

    if item < x[0] or item > x[len(x)-1]:
        return False

    mid = int(len(x) / 2)

    if item == x[mid]:
        return True

    elif item < x[mid]:
        return binary_search(x[0:mid], item)

    elif item > x[mid]:
        return binary_search(x[mid+1:], item)
In [19]:
random.seed(1)
random_list_1 = []
random_list_1 = sorted(random.choices(range(100), k=100))
print(random_list_1) 

for i in range(0, 10):
    print(i, '-', binary_search(random_list_1, i))

[0, 0, 2, 2, 2, 2, 2, 3, 3, 4, 9, 12, 13, 17, 17, 18, 21, 21, 22, 22, 23, 23, 23, 24, 25, 26, 28, 30, 33, 37, 38, 39, 39, 41, 42, 42, 42, 43, 43, 43, 44, 44, 45, 45, 48, 49, 49, 50, 50, 50, 51, 51, 52, 53, 54, 54, 54, 55, 56, 57, 58, 58, 59, 64, 65, 67, 67, 70, 70, 71, 72, 72, 74, 76, 76, 77, 77, 78, 78, 79, 80, 82, 83, 83, 83, 84, 84, 85, 86, 88, 88, 90, 93, 93, 94, 95, 95, 98, 98, 99]
0 - True
1 - False
2 - True
3 - True
4 - True
5 - False
6 - False
7 - False
8 - False
9 - True

Problem 8: Quicksort

In [20]:
def quicksort(x):
    if len(x) <=1:
        return x
    pivot = x[0]
    mid = [pivot]
    low=[]
    high=[]
    for i in range(1,len(x)):
        if x[i]<mid[0]:
            low.append(x[i])
        else:
            high.append(x[i])
    sorted_low =quicksort(low)
    sorted_high = quicksort(high)
    return sorted_low+mid+sorted_high
In [21]:
random.seed(2)

random_list_2 =random.choices(range(100),k=20)
print(random_list_2)
print(quicksort(random_list_2))

[95, 94, 5, 8, 83, 73, 66, 30, 60, 60, 58, 15, 43, 39, 72, 99, 94, 54, 44, 26]
[5, 8, 15, 26, 30, 39, 43, 44, 54, 58, 60, 60, 66, 72, 73, 83, 94, 94, 95, 99]
In [22]:
random.seed(3)

random_list_3 =random.choices(range(100),k=20)
print(random_list_3)
print(quicksort(random_list_3))

[23, 54, 36, 60, 62, 6, 1, 83, 25, 23, 99, 47, 83, 47, 63, 15, 63, 86, 52, 74]
[1, 6, 15, 23, 23, 25, 36, 47, 47, 52, 54, 60, 62, 63, 63, 74, 83, 83, 86, 99]
In [0]: