Intro-CS-Course/lab3.py at master · bharddwaj/Intro-CS-Course · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
'''
Created on Feb 14, 2019

@author: Bharddwaj Vemulapalli
username: bvemulap

I pledge my honor that I have abided by the Stevens Honor System.
'''

def change(amount, coins):
    '''Returns a non-negative integer indicating the minimum number of coins required to make up the givenamount.'''
    if amount == 0:
        return 0
    if amount < 0:
        return float("inf")
    if coins == []:
        return float("inf")
    return min(1 + change(amount - coins[0],coins), change(amount,coins[1:]) )
'''
doesn't work haha
def change2(amount,coins):

    if amount == 0:
        return 0
    if amount <= 0:
        return float("inf")
    if coins == []:
        return float("inf")
    max_coin_value = max(coins)
    max_index = coins.index(max_coin_value)

    list_of_modulars = list(map(lambda x: amount % x ,coins))
    min_remainder = min(list_of_modulars)
    filtered_list_coins = list(filter(lambda x: amount % x == min_remainder,coins))
    min_remainder_index = coins.index(max(filtered_list_coins)) #trying to find biggest number with smallest remainder

    # added this portion to remove 1 until later to see if it fixes algorithm
    index_for_one = coins.index(1)
    coins2 = coins[:index_for_one] + coins[index_for_one + 1:]

    list_of_modulars2 = list(map(lambda x: amount % x ,coins2))

    min_remainder2 = min(list_of_modulars2)

    filtered_list_coins2 = list(filter(lambda x: amount % x == min_remainder2,coins2))

    min_remainder_index2 = coins2.index(max(filtered_list_coins2))
    ###########################################################################
    #print(max(filtered_list_coins))
    #print(amount)


    #subtracting_max_first = 1 + change2(amount - coins[max_index], coins)
    mod_with_one = 1 + change2(amount - coins[min_remainder_index] , coins)
    print(f"this is modulus with 1: {coins[min_remainder_index]}")
    mod_without_one = 1 + change2(amount - coins2[min_remainder_index2],coins)
    print(f"this is modulus without 1: {coins2[min_remainder_index2]}")

    return min(mod_with_one,mod_without_one)
'''
#print(change(48, [1, 5, 10, 25, 50]) ) #supposed to be 6
#print(change(48, [1, 7, 24, 42]) )     #supposed to be 2
#print(change(35, [1, 3, 16, 30, 50]) ) #supposed to be 3