Dynamic programming algorithms - 1

dynamicProgrammingAlgorithms1.py

'''Course: https://www.coursera.org/learn/algorithmic-toolbox#about'''


def changeMoneyGreedy(moneyValue, demoninationsList):
    '''fast approach but doesnt give optimal result in all cases'''

    minNumOfDenominations = 0
    while moneyValue > 0:

        largestDenomination = 0
        for denomination in demoninationsList:
            if denomination <= moneyValue and denomination > largestDenomination:
                largestDenomination = denomination

        minNumOfDenominations += 1
        moneyValue = round(moneyValue - largestDenomination, 2)

    return minNumOfDenominations





def changeMoneyRecursive(moneyValue, demoninationsList):
    '''gives optimal solution but it is very slow for large problem size'''

    if moneyValue == 0:
        return 0

    minNumOfDenominations = 1000
    for denomination in demoninationsList:
        if denomination <= moneyValue:
            numOfDenominations = changeMoneyRecursive(round(moneyValue - denomination, 2), demoninationsList)

            if numOfDenominations < minNumOfDenominations:
                minNumOfDenominations = numOfDenominations + 1

    return minNumOfDenominations





def changeMoneyDynamicProgramming(moneyValue, demoninationsList):
    '''gives optimal solution and it is fast'''

    minNumOfCoinsList = [0] * (moneyValue+1)

    for money in range(1, moneyValue+1):
        minNumOfCoinsList[money] = 1000

        for denomination in demoninationsList:
            if denomination <= money:
                numOfDenominations = minNumOfCoinsList[money-denomination] + 1

                if numOfDenominations < minNumOfCoinsList[money]:
                    minNumOfCoinsList[money] = numOfDenominations

    return minNumOfCoinsList[moneyValue]





def editDistance(string1, string2):
    '''gives optimal solution and it is fast.
    returns minimum number of operations needed to change string1 to string2'''

    lengthOfString1 = len(string1)
    lengthOfString2 = len(string2)
    if lengthOfString1 > lengthOfString2:
        raise Exception("length of first string > length of second string")

    distance = []
    for row in range(lengthOfString1+1):
        distance.append([None] * (lengthOfString2+1))

    distance[0][0] = 0
    for row in range(1, lengthOfString1+1):
        distance[row][0] = row
    for col in range(1, lengthOfString2+1):
        distance[0][col] = col

    for col in range(1, lengthOfString2+1):
        for row in range(1, lengthOfString1+1):

            insertion = distance[row][col-1] + 1
            deletion = distance[row][col-1] + 1
            match = distance[row-1][col-1]
            mismatch = distance[row-1][col-1] + 1

            if string1[row-1] == string2[col-1]:
                distance[row][col] = min(insertion, deletion, match)
            else:
                distance[row][col] = min(insertion, deletion, mismatch)

    outputAlignment(lengthOfString1, lengthOfString2, distance, string1, string2)
    return distance[lengthOfString1][lengthOfString2]




def outputAlignment(row, col, distance, string1, string2):
    '''used in editDistance function. Prints the two strings and shows minimum operations needed'''

    if row == 0 and col == 0:
        return

    if row > 0 and distance[row][col] == distance[row-1][col] + 1:
        outputAlignment(row-1, col, distance, string1, string2)
        print("\n", string1[row-1], " | ", "-", end=" ")

    elif col > 0 and distance[row][col] == distance[row][col-1] + 1:
        outputAlignment(row, col-1, distance, string1, string2)
        print("\n", "-", " | ", string2[col-1], end=" ")

    else:
        outputAlignment(row-1, col-1, distance, string1, string2)
        print("\n", string1[row-1], " | ", string2[col-1], end=" ")




if __name__ == '__main__':

    print("\n(Greedy non-optimal) Get minimum no. of change for 95 Paise:", changeMoneyGreedy(95, [10, 25, 50, 75]))
    print("(Recursive too slow) Get minimum no. of change for 95 Paise:", changeMoneyRecursive(95, [10, 25, 50, 75]))
    print("(Dynamic Programming - fast) Get minimum no. of change for 95 Paise:", changeMoneyDynamicProgramming(95, [10, 25, 50, 75]))


    print("\nMinimum number of operations needed to change string1 to string2:", editDistance('editing', 'distance'))