4-2주차: 5/22/2023 - 5/28/2023

• Algorithm
  - A process or set of rules to be followed in calculations or other problem-solving operations
  

Search

Linear search

• Sequentially check each element of the list until a match is found or the whole list has been searched

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

searchData = int(input('Input an integer to be found: '))
searchResultIdx = -1

n = 0
while True:

    if n == len(datas):
        searchResultIdx = -1
        break

    elif datas[n] == searchData:
        searchResultIdx = n
        break

    n += 1

print(f'searchResultIdx = {searchResultIdx}')

Sentinel

• Sentinel value
  - A special value in an algorithm which uses its presence as a condition of termination
• Sentinel method
  - Add a sentinel value at the last index to simplify the search

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

searchData = int(input('Input an integer to be found: '))
searchResultIdx = -1

datas.append(searchData)

n = 0
while True:

    if datas[n] == searchData:
        if n != len(datas) - 1:
            searchResultIdx = n
        break

    n += 1

print(f'datas = {datas}')
print(f'datas length = {len(datas)}')
print(f'searchResultIdx = {searchResultIdx}')

Binary search

• Sort the data and compare the target value to the middle element of the array
• If they are not equal, the half in which the target cannot lie is eliminated
• The search continues on the remaining half
• Again take the middle element to compare to the target value
• Repeat this until the target value is found
• If the search ends with the remaining half being empty, the target is not in the array

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
print(f'nums: {nums}')

nums.sort()
print(f'nums: {nums}')

searchData = int(input('Input an integer to be found: '))
searchResultIdx = -1

startIdx = 0
endIdx = len(nums) - 1
midIdx = (startIdx + endIdx) // 2
midVal = nums[midIdx]

while nums[0] <= searchData < nums[len(nums)-1]:

    if searchData == nums[len(nums)-1]:
        searchResultIdx = len(nums)-1
        break

    if searchData > midVal:
        startIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midVal = nums[midIdx]

    elif searchData < midVal:
        midIdx = (startIdx + endIdx) // 2
        midVal = nums[midIdx]

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: {searchResultIdx}')

Exercises

def searchNumber(ns, sn):

    searchResultIdx = -1

    print(f'Numbers: {ns}')
    print(f'Search numbers: {sn}')

    n = 0
    while True:

        if n == len(ns):
            print('Search failed')
            break

        if ns[n] == sn:
            searchResultIdx = n
            print('Search successful')
            print(f'Search result index: {searchResultIdx}')
            break

        n += 1

    return searchResultIdx

import lineMod
import random

if __name__ == '__main__':

    rNums = random.sample(range(1, 21), 10)
    searchNum = int(input('Input a search number: '))

    resultIdx = lineMod.searchNumber(rNums, searchNum)

    if resultIdx == -1:
        print('Result not found')
        print(f'Search result index: {resultIdx}')

    else:
        print('>>> Search results <<<')
        print(f'Search result index: {resultIdx}')
        print(f'Search result number: {rNums[resultIdx]}')

def searchNumber(ns, sn):

    searchResultIdx = -1

    startIdx = 0
    endIdx = len(ns) - 1
    midIdx = (startIdx + endIdx) // 2
    midVal = ns[midIdx]

    print(f'startIdx: {startIdx}, endIdx: {endIdx}')
    print(f'midIdx: {midIdx}, midVal: {midVal}')

    while ns[0] <= sn <= ns[len(ns) - 1]:

        if sn == ns[len(ns) - 1]:
            searchResultIdx = len(ns) - 1
            break

        if startIdx + 1 == endIdx:
            if ns[startIdx] != sn and ns[endIdx] != sn:
                break

        if sn > midVal:
            startIdx = midIdx
            midIdx = (startIdx + endIdx) // 2
            midVal = ns[midIdx]
            print(f'+startIdx: {startIdx}, endIdx: {endIdx}')
            print(f'+midIdx: {midIdx}, midVal: {midVal}')

        elif sn < midVal:
            endIdx = midIdx
            midIdx = (startIdx + endIdx) // 2
            midVal = ns[midIdx]
            print(f'-startIdx: {startIdx}, endIdx: {endIdx}')
            print(f'-midIdx: {midIdx}, midVal: {midVal}')

        elif sn == midVal:
            searchResultIdx = midIdx
            break

    return searchResultIdx

import binaryMod

if __name__ == '__main__':

    nums = [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
    searchNum = int(input('Input a search number: '))

    resultIdx = binaryMod.searchNumber(nums, searchNum)
    print(f'nums: {nums}')

    if resultIdx == -1:
        print('Result not found')
        print(f'Search result index: {resultIdx}')

    else:
        print('>>> Search Results <<<')
        print(f'Search result index: {resultIdx}')
        print(f'Search result number: {nums[resultIdx]}')

Sorting

Ranking

• A procedure that ranks items in a dataset according to some criterion

import random

nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]

print(f'nums: {nums}')
print(f'ranks: {ranks}')

for idx, num1 in enumerate(nums):
    for num2 in nums:
        if num1 < num2:
            ranks[idx] += 1

print(f'nums: {nums}')
print(f'ranks: {ranks}')

for idx, num in enumerate(nums):
    print(f'nums: {num} \t rank: {ranks[idx] + 1}')

class RankDeviation:

    def __init__(self, mss, ess):
        self.midStuScos = mss
        self.endStuScos = ess
        self.midRanks = [0 for i in range(len(mss))]
        self.endRanks = [0 for i in range(len(ess))]
        self.rankDeviation = [0 for i in range(len(ess))]

    def setRank(self, ss, rs):
        for idx, sco1 in enumerate(ss):
            for sco2 in ss:
                if sco1 < sco2:
                    rs[idx] += 1

    def setMidRank(self):
        self.setRank(self.midStuScos, self.midRanks)

    def getMidRank(self):
        return self.midRanks

    def setEndRank(self):
        self.setRank(self.endStuScos, self.endRanks)

    def getEndRank(self):
        return self.endRanks

    def printRankDeviation(self):

        for idx, mRank in enumerate(self.midRanks):
            deviation = mRank - self.endRanks[idx]

            if deviation > 0:
                deviation = '↑' + str(abs(deviation))
            elif deviation < 0:
                deviation = '↓' + str(abs(deviation))
            else:
                deviation = '=' + str(abs(deviation))

            print(f'mid_rank: {mRank} \t end_rank: {self.endRanks[idx]} \t Deviation: {deviation}')

import rankMod as rm

import random

midStuScos = random.sample(range(50, 101), 20)
endStuScos = random.sample(range(50, 101), 20)

rd = rm.RankDeviation(midStuScos, endStuScos)
rd.setMidRank()
print(f'midStuScos: {midStuScos}')
print(f'mid_rank: {rd.getMidRank()}')

rd.setEndRank()
print(f'endStuScos: {endStuScos}')
print(f'end_rank: {rd.getEndRank()}')

rd.printRankDeviation()

Bubble sort

• Examine each set of adjacent elements in the string, from left to right
• Switch their positions if they are out of order
• Repeat until no two elements need to be swapped

nums = [10, 2, 7, 21, 0]

print(f'Unsorted nums: {nums}')

# length = 4
length = len(nums) - 1

for i in range(length): # 0, 1, 2, 3
    for j in range(length - i): # 0, 1, 2, 3
        if nums[j] > nums[j+1]:
            # temp = nums[j]
            # nums[j] = nums[j+1]
            # nums[j+1] = temp
            nums[j], nums[j+1] = nums[j+1], nums[j]

        print(nums)
    print()

print(f'Sorted nums: {nums}')

import copy

def bubbleSort(ns, deepCopy=True):

    if deepCopy:
        cns = copy.copy(ns)
    else:
        cns = ns

    length = len(cns) - 1
    for i in range(length):
        for j in range(length - i):
            if cns[j] > cns[j+1]:
                cns[j], cns[j+1] = cns[j+1], cns[j]

    return cns

import random as rd
import sortMod as sm

students = []

for i in range(20):
    students.append(rd.randint(170, 185))

print(f'students: {students}')

# shallow copy
sortedStudents = sm.bubbleSort(students, deepCopy=False)

print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')

Insertion sort

• Build the final sorted array (or list) one item at a time by comparisons

# ascending

nums = [5, 10, 2, 1, 0]


def ascendingSort(nums):

    for i1 in range(1, len(nums)): # 1, 2, 3, 4
        i2 = i1 - 1
        cNum = nums[i1]

        while nums[i2] > cNum and i2 >= 0:
            nums[i2 + 1] = nums[i2]
            i2 -= 1

        nums[i2 + 1] = cNum

        print(f'nums: {nums}')

    return nums

nums = ascendingSort(nums)

# descending

nums = [0, 5, 2, 10, 1]


def descendingSort(nums):

    for i1 in range(1, len(nums)): # 1, 2, 3, 4
        i2 = i1 - 1
        cNum = nums[i1]

        while nums[i2] < cNum and i2 >= 0:
            nums[i2 + 1] = nums[i2]
            i2 -= 1

        nums[i2 + 1] = cNum

        print(f'nums: {nums}')

    return nums

nums = descendingSort(nums)

class SortNumbers:

    def __init__(self, ns, asc=True):
        self.nums = ns
        self.isAsc = asc

    def isAscending(self, flag):
        self.isAsc = flag

    def setSort(self):

        for i1 in range(1, len(self.nums)): # 1, 2, 3, ...
            i2 = i1 - 1 # 0, 1, 2, ...
            cNum = self.nums[i1]

            if self.isAsc:
                while self.nums[i2] > cNum and i2 >= 0:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1
            else:
                while self.nums[i2] < cNum and i2 >= 0:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1

            self.nums[i2 + 1] = cNum

    def getSortedNumbers(self):
        return self.nums

    def getMinNumber(self):
        if self.isAsc:
            return self.nums[0]
        else:
            return self.nums[len(self.nums) - 1]

    def getMaxNumber(self):
        if self.isAsc:
            return self.nums[len(self.nums) - 1]
        else:
            return self.nums[0]

import random
import sortMod as sm

nums = random.sample(range(1, 1000), 100)
print(f'Not sorted numbers: {nums}')

# Constructing objects
sn = sm.SortNumbers(nums)

# Ascending
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by ascending order: {sortedNumbers}')

# Descending
sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by descending order: {sortedNumbers}')

# Min & max
print(f'min: {sn.getMinNumber()}')
print(f'max: {sn.getMaxNumber()}')

Selection sort

• Repeatedly select the smallest (or largest) element from the unsorted portion of the list
• Move it to the sorted portion of the list

nums = [4, 2, 5, 1, 3]
print(f'nums: {nums}')

for i in range(len(nums) - 1):
    minIdx = i

    for j in range(i+1, len(nums)):
        if nums[minIdx] > nums[j]:
            minIdx = j

    # tempNum = nums[i]
    # nums[i] = nums[minIdx]
    # nums[minIdx] = tempNum

    nums[i], nums[minIdx] = nums[minIdx], nums[i]
    print(f'nums: {nums}')

print(f'Final nums: {nums}')

def sortNumber(ns, asc=True):

    if asc:
        for i in range(len(ns) - 1):
            minIdx = i

            for j in range(i+1, len(ns)):
                if ns[minIdx] > ns[j]:
                    minIdx = j

            ns[i], ns[minIdx] = ns[minIdx], ns[i]
    else:
        for i in range(len(ns) - 1):
            maxIdx = i

            for j in range(i+1, len(ns)):
                if ns[maxIdx] < ns[j]:
                    maxIdx = j

            ns[i], ns[maxIdx] = ns[maxIdx], ns[i]

    return ns

import random
import sortMod as sm
import copy

scores = random.sample(range(50, 101), 20)

print(f'scores: {scores}')
result = sm.sortNumber(copy.deepcopy(scores))
print(f'result: {result}')

print()

print(f'scores: {scores}')
result = sm.sortNumber(copy.deepcopy(scores), asc=False)
print(f'result: {result}')

Merge sort

• Divide the unsorted list into n sublists, each containing one element
• Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining

def mSort(ns, asc=True):

    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx], asc=asc)
    rightNums = mSort(ns[midIdx:len(ns)], asc=asc)

    # print(f'leftNums: {leftNums}')
    # print(f'rightNums: {rightNums}')

    mergeNums = []
    leftIdx = 0
    rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        if asc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1

            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1
        else:
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1

            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1

        # print(f'mergeNums: {mergeNums}')

    mergeNums += leftNums[leftIdx:]
    # print(f'mergeNums: {mergeNums}')
    mergeNums += rightNums[rightIdx:]
    # print(f'mergeNums: {mergeNums}')

    return mergeNums

import random as rd
import sortMod as sm

rNums = rd.sample(range(1, 101), 10)
print(f'Unsorted rNums: {rNums}')
print(f'Sorted rNums ASC: {sm.mSort(rNums)}')
print(f'Sorted rNums DESC: {sm.mSort(rNums, asc=False)}')

Quick sort

• Pick an element as a pivot
• Partition the given array around the picked pivot

def qSort(ns, asc=True):

    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    midVal = ns[midIdx]

    smallNums = []
    sameNums = []
    bigNums = []

    for n in ns:
        if n < midVal:
            smallNums.append(n)
        elif n == midVal:
            sameNums.append(n)
        else:
            bigNums.append(n)
    if asc:
        return qSort(smallNums, asc=asc) + sameNums + qSort(bigNums, asc=asc)
    else:
        return qSort(bigNums, asc=asc) + sameNums + qSort(smallNums, asc=asc)

import random as rd
import sortMod as sm

rNums = rd.sample(range(1, 100), 10)
print(f'Unsorted rNums: {rNums}')
print(f'Sorted rNums ASC: {sm.qSort(rNums)}')
print(f'Sorted rNums DESC: {sm.qSort(rNums, asc=False)}')

Exercises

datas = [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
print(f'datas: {datas}')

asciiDatas = []
for data in datas:
    if str(data).isalpha():
        asciiDatas.append(ord(data))
        continue

    asciiDatas.append(data)

print(f'asciiDatas: {asciiDatas}')

ranks = [0 for x in range(len(asciiDatas))]
print(f'ranks before: {ranks}')

for idx, data1 in enumerate(asciiDatas):
    for data2 in asciiDatas:
        if data1 < data2:
            ranks[idx] += 1

print(f'ranks after: {ranks}')

for i, d in enumerate(datas):
    print(f'data: {d:>2} \t rank: {ranks[i] + 1}')

import copy


def sortBubble(ns, asc=True):
    c_ns = copy.copy(ns)

    length = len(c_ns) - 1
    for i in range(length):
        for j in range(length - i):

            if asc:
                if c_ns[j] > c_ns[j+1]:
                    c_ns[j], c_ns[j+1] = c_ns[j+1], c_ns[j]
            else:
                if c_ns[j] < c_ns[j+1]:
                    c_ns[j], c_ns[j+1] = c_ns[j+1], c_ns[j]

            print(f'ns: {c_ns}')
        print()

    return c_ns

import random
import bubbleMod

if __name__ == '__main__':

    nums = random.sample(range(1, 21), 10)
    print(f'Unsorted nums: {nums}')

    result = bubbleMod.sortBubble(nums)
    print(f'Sorted nums by ASC: {result}')

    print()

    result = bubbleMod.sortBubble(nums, asc=False)
    print(f'Sorted nums by DESC: {result}')

import copy

def sortInsert(ns, asc=True):

    c_ns = copy.copy(ns)

    for i1 in range(1, len(c_ns)):
        i2 = i1 - 1
        cNum = c_ns[i1]

        if asc:
            while c_ns[i2] > cNum and i2 >= 0:
                c_ns[i2 + 1] = c_ns[i2]
                i2 -= 1
        else:
            while c_ns[i2] < cNum and i2 >= 0:
                c_ns[i2 + 1] = c_ns[i2]
                i2 -= 1

        c_ns[i2 + 1] = cNum
        print(f'c_ns: {c_ns}')

    return c_ns

import random
import insertMod

if __name__ == '__main__':

    nums = random.sample(range(1, 21), 10)

    print(f'Unsorted nums:\n{nums}')
    result = insertMod.sortInsert(nums)
    print(f'Sorted nums by ASC:\n{result}')

    print(f'Unsorted nums:\n{nums}')
    result = insertMod.sortInsert(nums, asc=False)
    print(f'Sorted nums by DESC:\n{result}')

import copy


def sortSelect(ns, asc=True):
    c_ns = copy.copy(ns)

    for i in range(len(c_ns) - 1):
        minIdx = i

        for j in range(i + 1, len(c_ns)):

            if asc:
                if c_ns[minIdx] > c_ns[j]:
                    minIdx = j
            else:
                if c_ns[minIdx] < c_ns[j]:
                    minIdx = j

        c_ns[i], c_ns[minIdx] = c_ns[minIdx], c_ns[i]
        print(f'nums: {c_ns}')

    return c_ns

import random
import selectMod

if __name__ == '__main__':

    nums = random.sample(range(1, 21), 10)
    print(f'Unsorted nums: \t {nums}')

    result = selectMod.sortSelect(nums)
    print(f'Sorted nums by ASC: \t {result}')

    result = selectMod.sortSelect(nums, asc=False)
    print(f'Sorted nums by DESC: \t {result}')
    

def mSort(ns, asc=True):

    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx], asc=asc)
    rightNums = mSort(ns[midIdx:len(ns)], asc=asc)

    mergeNums = []
    leftIdx = 0
    rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        if asc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1
        else:
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1

    mergeNums += leftNums[leftIdx:]
    mergeNums += rightNums[rightIdx:]

    print(f'mergeNums: {mergeNums}')
    return mergeNums

import random
import mergeMod

rNums = random.sample(range(1, 101), 20)
print(f'rNums: {rNums}')
print(f'mergeMod.mSort(rNums): {mergeMod.mSort(rNums)}')
print(f'mergeMod.mSort(rNums, asc=False): {mergeMod.mSort(rNums, asc=False)}')

Descriptive statistics

Maximum

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0

    def getMaxNum(self):
        self.maxNum = self.nums[0]

        for n in self.nums:
            if self.maxNum < n:
                self.maxNum = n

        return self.maxNum


ma = MaxAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])
maxNum = ma.getMaxNum()
print(f'maxNum: {maxNum}')

Minimum

class MinAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.minNum = 0

    def getMinNum(self):
        self.minNum = self.nums[0]

        for n in self.nums:
            if self.minNum > n:
                self.minNum = n

        return self.minNum


nums = [-2, -4, 5, 7, 10, 0, 8, 20, -11]
ma = MinAlgorithm(nums)
minNum = ma.getMinNum()
print(f'minNum: {minNum}')

Mode

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumIdx = 0

    def setMaxIdxAndNum(self):
        self.maxNum = self.nums[0]
        self.maxNumIdx = 0

        for i, n in enumerate(self.nums):
            if self.maxNum < n:
                self.maxNum = n
                self.maxNumIdx = i

    def getMaxNum(self):
        return self.maxNum

    def getMaxNumIdx(self):
        return self.maxNumIdx


nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]
maxAlgo = MaxAlgorithm(nums)
maxAlgo.setMaxIdxAndNum()
maxNum = maxAlgo.getMaxNum()
print(f'maxNum: {maxNum}')

indices = [0 for i in range(maxNum + 1)]
print(f'indices: {indices}')
print(f'indices length: {len(indices)}')

for n in nums:
    indices[n] = indices[n] + 1
print(f'indices: {indices}')

maxAlgo = MaxAlgorithm(indices)
maxAlgo.setMaxIdxAndNum()
maxNum = maxAlgo.getMaxNum()
maxNumIdx = maxAlgo.getMaxNumIdx()
print(f'maxNum: {maxNum}')
print(f'maxNumIdx: {maxNumIdx}')

print(f'The frequency of {maxNumIdx} is the highest at {maxNum}')

import random
import maxScore as ms

scores = []

for i in range(100):
    rn = random.randint(71, 100)
    if rn != 100: rn = rn - (rn % 5)
    scores.append(rn)

print(f'scores: {scores}')
print(f'scores length: {len(scores)}')

# Maximum algorithm
maxAlgo = ms.MaxAlgorithm(scores)
maxAlgo.setMaxNumIdxAndNum()
maxNum = maxAlgo.getMaxNum()
print(f'maxNum: {maxNum}')

# Construct a list of indices
indices = [0 for x in range(maxNum + 1)]
print(f'indices: {indices}')
print(f'indices length: {len(indices)}')

# Save the frequency in the indices list
for n in scores:
    indices[n] = indices[n] + 1
print(f'indices: {indices}')

n = 1
while True:

    maxAlgo = ms.MaxAlgorithm(indices)
    maxAlgo.setMaxNumIdxAndNum()
    maxNum = maxAlgo.getMaxNum()
    maxNumIdx = maxAlgo.getMaxNumIdx()
    # print(f'maxNum: {maxNum}')
    # print(f'maxNumIdx: {maxNumIdx}')

    if maxNum == 0:
        break

    print(f'{n}. Frequency of {maxNumIdx}: {maxNum}\t', end='')
    print('+' * maxNum)

    indices[maxNumIdx] = 0

    n += 1

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumAndIdx = 0

    def setMaxNumIdxAndNum(self):
        self.maxNum = self.nums[0]
        self.maxNumIdx = 0

        for i, n in enumerate(self.nums):
            if self.maxNum < n:
                self.maxNum = n
                self.maxNumIdx = i

    def getMaxNum(self):
        return self.maxNum

    def getMaxNumIdx(self):
        return self.maxNumIdx

Approximation

import random

nums = random.sample(range(0, 50), 20)
print(f'nums: {nums}')

inputNum = int(input('Input a number: '))
print(f'inputNum: {inputNum}')

nearNum = 0
minNum = 50

for n in nums:
    absNum = abs(n - inputNum)
    # print(f'absNum: {absNum}')

    if absNum < minNum:
        minNum = absNum
        nearNum = n

print(f'nearNum: {nearNum}')

Average

# Average of numbers between 50 and 90

import random
nums = random.sample(range(0, 100), 30)
print(f'nums: {nums}')

total = 0
targetNums = []
for n in nums:
    if n >= 50 and n <= 90:
        total += n
        targetNums.append(n)

average = total / len(targetNums)
print(f'targetNums: {targetNums}')
print(f'average: {round(average, 2)}')

class Top5Scores:

    def __init__(self, cs, ns):
        self.currentScores = cs
        self.newScore = ns

    def setAlignScores(self):

        nearIdx = 0
        nearScore = 0
        minNum = 10.0

        for i, s in enumerate(self.currentScores):
            absNum = abs(self.newScore - s)

            if absNum < minNum:
                minNum = absNum
                nearIdx = i
                nearScore = s

        if self.newScore >= nearScore:
            for i in range(len(self.currentScores)-1, nearIdx, -1):
                self.currentScores[i] = self.currentScores[i-1]

            self.currentScores[nearIdx] = self.newScore

        else:
            for i in range(len(self.currentScores)-1, nearIdx+1, -1):
                self.currentScores[i] = self.currentScores[i-1]

            self.currentScores[nearIdx+1] = self.newScore

    def getFinalTop5Scores(self):
        return self.currentScores

import near

scores = [8.9, 7.6, 8.2, 9.1, 8.8, 8.1, 7.9, 9.4, 7.2, 8.7]
top5Scores = [9.12, 8.95, 8.12, 7.90, 7.88]

print(f'top5Scores: {top5Scores}')

total = 0
for n in scores:
    total += n

average = round(total / len(scores), 2)
print(f'total: {total}')
print(f'average: {average}')

tp = near.Top5Scores(top5Scores, average)
tp.setAlignScores()
top5Scores = tp.getFinalTop5Scores()
print(f'top5Scores: {top5Scores}')

Exercises

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumCnt = 0

    def setMaxNum(self):
        self.maxNum = 0

        for n in self.nums:
            if self.maxNum < n:
                self.maxNum = n

    def getMaxNum(self):
        self.setMaxNum()
        return self.maxNum

    def setMaxNumCnt(self):
        self.setMaxNum()

        for n in self.nums:
            if self.maxNum == n:
                self.maxNumCnt += 1

    def getMaxNumCnt(self):
        self.setMaxNumCnt()
        return self.maxNumCnt

import random
import maxMod

if __name__ == '__main__':

    nums = []
    for n in range(30):
        nums.append(random.randint(1, 50))

    print(f'nums: \n {nums}')
    ma = maxMod.MaxAlgorithm(nums)
    print(f'Max num: {ma.getMaxNum()}')
    print(f'Max num count: {ma.getMaxNumCnt()}')
    

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumIdx = 0

    def setMaxIdxAndNum(self):
        self.maxNum = 0
        self.maxNumIdx = 0

        for i, n in enumerate(self.nums):
            if self.maxNum < n:
                self.maxNum = n
                self.maxNumIdx = i

    def getMaxNum(self):
        self.setMaxIdxAndNum()
        return self.maxNum

    def getMaxIdx(self):
        self.setMaxIdxAndNum()
        return self.maxNumIdx

import maxMod


class ModeAlgorithm:

    def __init__(self, ns, mn):
        self.nums = ns
        self.maxNum = mn
        self.indices = []

    def setIndexList(self):
        self.indices = [0 for x in range(self.maxNum+1)]

        for n in self.nums:
            self.indices[n] += 1

    def getIndexList(self):
        self.setIndexList()
        if sum(self.indices) == 0:
            return None
        else:
            return self.indices

    def printAges(self):

        n = 1
        while True:

            maxAlgo = maxMod.MaxAlgorithm(self.indices)
            maxNum = maxAlgo.getMaxNum()
            maxNumIdx = maxAlgo.getMaxIdx()

            if maxNum == 0:
                break

            print(f'[{n:0>3}] Frequency of age {maxNumIdx}: {maxNum} \t', end='')
            print('+' * maxNum)
            self.indices[maxNumIdx] = 0

            n += 1

import modeMod
import maxMod

ages = [25, 27, 27, 24, 31, 34, 33, 31, 29, 25,
        45, 37, 38, 46, 47, 22, 24, 29, 33, 35,
        27, 34, 37, 40, 42, 29, 27, 25, 26, 27,
        31, 31, 32, 38, 25, 27, 28, 40, 41, 34]

print(f'Employee count: {len(ages)} employees')

maxAlgo = maxMod.MaxAlgorithm(ages)
maxAge = maxAlgo.getMaxNum()
print(f'Max age: {maxAge}')

# modeMod

modeAlgo = modeMod.ModeAlgorithm(ages, maxAge)
print(f'Index list: {modeAlgo.getIndexList()}')

modeAlgo.printAges()

class LottoMode:

    def __init__(self, ln):
        self.lottoNums = ln
        self.modeList = [0 for n in range(1, 47)]

    def getLottoNumMode(self):

        for roundNums in self.lottoNums:
            for num in roundNums:
                self.modeList[num] += 1

        return self.modeList

    def printModeList(self):
        if sum(self.modeList) == 0:
            return None

        for i, m in enumerate(self.modeList):
            if i != 0:
                print(f'Number: {i:>2}, frequency: {m}, {"*" * m}')

import random
import modeMod

lottoNums = []
for i in range(30):
    addNums = []
    for j in range(6):
        rNum = random.randint(1, 45)
        addNums.append(rNum)
    lottoNums.append(addNums)
print(f'lottoNums: {lottoNums}')

lm = modeMod.LottoMode(lottoNums)
mList = lm.getLottoNumMode()
print(f'mList: {mList}')

lm.printModeList()

class BmiAlgorithm:

    def __init__(self, w, h):

        self.BMISection = {18.5: ['Underweight', 'Healthy'],
                           23: ['Healthy', 'Overweight'],
                           25: ['Overweight', 'Obese']}
        self.userWeight = w
        self.userHeight = h
        self.userBMI = 0
        self.userCondition = ''
        self.nearNum = 0
        self.minNum = 25  # Set as the largest possible value

    def calculatorBMI(self):
        self.userBMI = round(self.userWeight / (self.userHeight ** 2), 2)
        print(f'self.userBMI: {self.userBMI}')

    def printUserCondition(self):

        for n in self.BMISection.keys():
            absNum = abs(n - self.userBMI)
            if absNum < self.minNum:
                self.minNum = absNum
                self.nearNum = n
        print(f'self.nearNum: {self.nearNum}')

        if self.userBMI <= self.nearNum:
            self.userCondition = self.BMISection[self.nearNum][0]
        else:
            self.userCondition = self.BMISection[self.nearNum][1]

        print(f'self.userCondition: {self.userCondition}')

import nearMod

uWeight = float(input('Input weight (kg): '))
uHeight = float(input('Input height (m): '))

na = nearMod.BmiAlgorithm(uWeight, uHeight)
na.calculatorBMI()
na.printUserCondition()

class MaxAlgorithm:

    def __init__(self, ss):
        self.scores = ss
        self.maxScore = 0
        self.maxIdx = 0

    def removeMaxScore(self):
        self.maxScore = self.scores[0]

        for i, s in enumerate(self.scores):
            if self.maxScore < s:
                self.maxScore = s
                self.maxIdx = i
        print(f'self.maxScore: {self.maxScore}')
        print(f'self.maxIdx: {self.maxIdx}')

        self.scores.pop(self.maxIdx)
        print(f'scores: {self.scores}')

class MinAlgorithm:

    def __init__(self, ss):
        self.scores = ss
        self.minScore = 0
        self.minIdx = 0

    def removeMaxScore(self):
        self.minScore = self.scores[0]

        for i, s in enumerate(self.scores):
            if self.minScore > s:
                self.minScore = s
                self.minIdx = i
        print(f'self.minScore: {self.minScore}')
        print(f'self.minIdx: {self.minIdx}')

        self.scores.pop(self.minIdx)
        print(f'scores: {self.scores}')

class Top5Players:

    def __init__(self, cs, ns):
        self.currentScores = cs
        self.newScore = ns

    def setSortScores(self):
        nearIdx = 0
        minNum = 10.0

        for i, s in enumerate(self.currentScores):
            absNum = abs(self.newScore - s)
            if absNum < minNum:
                minNum = absNum
                nearIdx = i

        if self.newScore >= self.currentScores[nearIdx]:
            for i in range(len(self.currentScores)-1, nearIdx, -1):
                self.currentScores[i] = self.currentScores[i-1]
            self.currentScores[nearIdx] = self.newScore

        else:
            for i in range(len(self.currentScores)-1, nearIdx+1, -1):
                self.currentScores[i] = self.currentScores[i-1]
            self.currentScores[nearIdx+1] = self.newScore

    def getFinalTop5Scores(self):
        self.setSortScores()
        return self.currentScores

import maxAlgorithm
import minAlgorithm
import nearMod

top5Scores = [9.12, 8.95, 8.12, 6.90, 6.18]
scores = [6.7, 5.9, 8.1, 7.9, 6.7, 7.3, 7.2, 8.2, 6.2, 5.8]
print(f'scores: {scores}')

maxA = maxAlgorithm.MaxAlgorithm(scores)
maxA.removeMaxScore()

minA = minAlgorithm.MinAlgorithm(scores)
minA.removeMaxScore()

total = 0
for n in scores:
    total += n

average = round(total / len(scores), 2)

print(f'total: {round(total, 2)}')
print(f'average: {average}')

tp = nearMod.Top5Players(top5Scores, average)
top5Scores = tp.getFinalTop5Scores()
print(f'newTop5Scores: {top5Scores}')

Recursion

Recursion

• A function calls itself

def recursion(num):

    if num > 0:
        print('*' * num)
        return recursion(num-1)
    else:
        return 1


recursion(10)

• Euclidean algorithm

def gcd(n1, n2):

    if n1 % n2 == 0:
        return n2
    else:
        return gcd(n2, n1 % n2)

print(f'gcd(82, 32): {gcd(82, 32)}')
print(f'gcd(96, 40): {gcd(96, 40)}')

• Tower of Hanoi

# discCnt: number of discs; fromBar: first pole
# toBar: last pole; viaBar: intermediary pole

def moveDisc(discCnt, fromBar, toBar, viaBar):
    if discCnt == 1:
        print(f'Move disc {discCnt} from {fromBar} to {toBar}')
    else:
        # Move (discCnt-1) discs to viaBar
        moveDisc(discCnt-1, fromBar, viaBar, toBar)

        # Move discCnt discs to toBar
        print(f'Move disc {discCnt} from {fromBar} to {toBar}')

        # Move (discCnt-1) discs to toBar
        moveDisc(discCnt-1, viaBar, toBar, fromBar)

moveDisc(3, 1, 3, 2)

Exercises

class NumsSum:

    def __init__(self, n1, n2):
        self.bigNum = 0
        self.smallNum = 0
        self.setN1N2(n1, n2)

    def setN1N2(self, n1, n2):
        self.bigNum = n1
        self.smallNum = n2

        if n1 < n2:
            self.bigNum = n2
            self.smallNum = n1

    def addNum(self, n):
        if n <= 1:
            return n

        return n + self.addNum(n-1)

    def sumNums(self):
        return self.addNum(self.bigNum - 1)\
            - self.addNum(self.smallNum)

import recursionMod

num1 = int(input('Input number1: '))
num2 = int(input('Input number2: '))

ns = recursionMod.NumsSum(num1, num2)
result = ns.sumNums()
print(f'result: {result}')