6/100 -> Tick fucking tock

How I felt in these 6 days of 100daysofcode…

#Coding question of the day,

Continue from previous question …

Q: Given a set of coins (1,2,3) and a value (5). Find out the list of combinations with the set of coins that sum up to the given value.

1
2
3
Given a set of coins [1,2,3] and value 5, return the list of combinations in an array of string.

Combinations: ['23', '122', '113', '1112', '11111']

Soluton 1: Naive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def combination(coins, value):
if len(coins) == 0 or value < 0:
return []

if coins[0] - value == 0:
return [str(coins[0])]

permutationOfCoins = combination(coins, value - coins[0])

for i in range(len(permutationOfCoins)):
permutationOfCoins[i] = str(coins[0]) + permutationOfCoins[i]

return combination(coins[1:], value) + permutationOfCoins


coins, value = [1, 2, 3], 5
print combination(coins, value)

Result:

1
['23', '122', '113', '1112', '11111']

Soluton 2: Better

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
def combination(coins, value, memo):
if len(coins) == 0 or value < 0:
return []

if coins[0] - value == 0:
return [str(coins[0])]

sortedCoinsWithValue = (''.join(map(str, sorted(coins))), value - coins[0])

if sortedCoinsWithValue not in memo:
memo[sortedCoinsWithValue] = combination(coins, value - coins[0], memo)

for i in range(len(memo[sortedCoinsWithValue])):
memo[sortedCoinsWithValue][i] = str(
coins[0]) + memo[sortedCoinsWithValue][i]

return combination(coins[1:], value, memo) + memo[sortedCoinsWithValue]


def combinationUtil(coins, value):
memo = {}
return combination(coins, value, memo)


coins, value = [1, 2, 3], 5
print combinationUtil(coins, value)

Result:

1
['23', '122', '113', '1112', '11111']

With that we can easily find the least number of coins that sum up to the value.

BONUS QUESTION!

Q: Given a set of coins, find the least number of coins that sum up to a given value. Return 0 if there is none.

1
2
3
4
Given coins [1,2,3] and value = 5,
Answer: 2

Combinations: ['23', '122', '113', '1112', '11111']
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
def combination(coins, value, memo):
if len(coins) == 0 or value < 0:
return []

if coins[0] - value == 0:
return [str(coins[0])]

sortedCoinsWithValue = (''.join(map(str, sorted(coins))), value - coins[0])

if sortedCoinsWithValue not in memo:
memo[sortedCoinsWithValue] = combination(coins, value - coins[0], memo)

for i in range(len(memo[sortedCoinsWithValue])):
memo[sortedCoinsWithValue][i] = str(
coins[0]) + memo[sortedCoinsWithValue][i]

return combination(coins[1:], value, memo) + memo[sortedCoinsWithValue]


def combinationUtil(coins, value):
sortedSetOfCoins = sorted(coins) # so our results will be sorted too ^^
memo = {}

results = combination(sortedSetOfCoins, value, memo)
leastNumberOfCoins = results[0]
return len(leastNumberOfCoins)


coins, value = [3, 2, 1], 5
print combinationUtil(coins, value)

Result:

1
2

#End,

Oh my gawd, I am enjoying doing coding question more than I expected? Much more than when I was in school. What the heck. Why Java, why so much paper, why dry content.