ExchangeNotes.py

#!/usr/local/bin/python2.7
table = {}

def findMin(num10, num5, num2, amount):
    # print (amount, num10, num5, num2)
    value10 = 99999999
    value5 = 999999999
    value2 = 999999999
    if (num10, num5, num2, amount) in table:
        return table[(num10, num5, num2, amount)]
    elif (amount <= num10 * 10) and (amount <= num5 * 5) and (amount <= num2 * 2) and ((-1, -1, -1, amount) in table):
        return table[(-1, -1, -1, amount)]
    elif amount == 0:
        table[(num10, num5, num2, amount)] = (0, 0, 0, 0)
        return table[(num10, num5, num2, amount)]
    elif num10 + num5 + num2 == 0:
        table[(num10, num5, num2, amount)] = (99999999, 50, 100, 500)
        return table[(num10, num5, num2, amount)]
    elif amount < 2:
        table[(num10, num5, num2, amount)] = (99999999, 0, 0, 0)
        return table[(num10, num5, num2, amount)]
    else:
        if (amount >= 2) and (num2 >= 1):
            value2 = 1 + (findMin(num10, num5, num2 - 1, amount - 2))[0]
        if (amount >= 5) and (num5 >= 1):
            value5 = 1 + (findMin(num10, num5 - 1, num2, amount - 5))[0]
        if (amount >= 10) and (num10 >= 1):
            value10 = 1 + (findMin(num10 - 1, num5, num2, amount - 10))[0]
        if (value10 <= value5) and (value10 <= value2) and (amount >= 10) and (num10 >= 1):
            table[(num10, num5, num2, amount)] = (value10, 1 + table[(num10 - 1, num5, num2, amount - 10)][1], table[(num10 - 1, num5, num2, amount - 10)][2], table[(num10 - 1, num5, num2, amount - 10)][3])
        elif (value5 <= value2) and (amount >= 5) and (num5 >= 1):
            table[(num10, num5, num2, amount)] = (value5, table[(num10, num5 - 1, num2, amount - 5)][1], 1 + table[(num10, num5 - 1, num2, amount - 5)][2], table[(num10, num5 - 1, num2, amount - 5)][3])
        elif (amount >= 2) and (num2 >= 1):
            table[(num10, num5, num2, amount)] = (value2, table[(num10, num5, num2 - 1, amount - 2)][1], table[(num10, num5, num2 - 1, amount - 2)][2], 1 + table[(num10, num5, num2 - 1, amount - 2)][3])
        if (amount < num10 * 10) and (amount < num5 * 5) and (amount < num2 * 2):
            table[(-1 -1, -1, amount)] = table[(num10, num5, num2, amount)]
        return table[(num10, num5, num2, amount)]

def ExchangeNotes(amount):
    if amount > (50 * 10 + 100 * 5 + 500 * 2):
        print "'50xS$10, 100xS$5, 500xS$2, remainder: S$" + str(amount - (50 * 10 + 100 * 5 + 500 * 2)) + "'"
    else:
        answer = findMin(50, 100, 500, amount)
        # print answer
        is10NoteNeeded = False
        is5NoteNeeded = False
        is2NoteNeeded = False
        if answer[1] > 0:
            is10NoteNeeded = True
        if answer[2] > 0:
            is5NoteNeeded = True
        if answer[3] > 0:
            is2NoteNeeded = True
        answerString = "'"
        if is10NoteNeeded:
            answerString = answerString + str(answer[1]) + "xS$10"
        if is10NoteNeeded and is5NoteNeeded:
            answerString = answerString + ", "
        if is5NoteNeeded:
            answerString = answerString + str(answer[2]) + "xS$5"
        if (is10NoteNeeded and is2NoteNeeded) or (is5NoteNeeded and is2NoteNeeded):
            answerString = answerString + ", "
        if is2NoteNeeded:
             answerString = answerString + str(answer[3]) + "xS$2"
        answerString = answerString + "'"
        if (not is10NoteNeeded) and (not is5NoteNeeded) and (not is2NoteNeeded):
            answerString = answerString + "   #the bank will not give any notes"
        print answerString
#
ExchangeNotes(1000)
ExchangeNotes(888)
ExchangeNotes(88)
ExchangeNotes(4)
ExchangeNotes(7)
ExchangeNotes(5000)
ExchangeNotes(0)
ExchangeNotes(-2)