Coffee Vending Machine Problems [Part 1]

You have a vending machine, but it can not give the change back. You decide to implement this functionality. First of all, you need to know the minimum number of coins for this operation (i'm sure you don't want to return 100 pennys instead of 1$ coin).
So, find an optimal number of coins required, if you have unlimited set of coins with given denominations.

Assume all inputs are valid positive integers, and every set of coin denominations has len 4 for simplicity;

Examples:

optimal_number_of_coins(1, [1, 2, 5, 10]) 
(1 penny) so returns 1  
optimal_number_of_coins(5, [1, 2, 5, 10])
(5) so returns 1
optimal_number_of_coins(6, [1, 3, 5, 10])
(3+3 or 5+1) = 6 so returns 2
optimal_number_of_coins(10, [1, 2, 5, 10]) 
(10) so returns 1
optimal_number_of_coins(12, [1, 3, 5, 10])
(10+1+1) = 12 so returns 3
optimal_number_of_coins(53, [1, 2, 5, 25])
(25+25+2+1) = 53 so returns 4
optimal_number_of_coins(7, [1, 1, 1, 25])
(1+1+1+1+1+1+1) = 7 so returns 7
etc..

Have fun =)

Source: codewars | Difficulty: EASY
Tags: Mathematics

Starter code: def optimal_number_of_coins(n, coins):
	

Solutions:
from functools import lru_cache

def optimal_number_of_coins(n, coins):

	@lru_cache(maxsize=None)
	def f(amount: int, idx: int) -> float:
		(q, r) = divmod(amount, coins[idx])
		if r == 0:
			return q
		elif amount < 0 or idx <= 0:
			return float('inf')
		else:
			return min(1 + f(amount - coins[idx], idx), f(amount, idx - 1))
	coins = sorted(set(coins))
	return f(n, len(coins) - 1)


def optimal_number_of_coins(n, coins):
	s = [0] * (n + 1)
	for c in coins:
		if c <= n:
			s[c] = 1
	for i in range(n + 1):
		s[i] = min((s[i - v] + 1 for v in coins if i - v >= 0), default=0)
	return s[n]


def optimal_number_of_coins(n, coins):
	dicto = {}

	def optimal_number_of_coinss(n, coins, mino=0, indo=0):
		key = f'{n}mino:{mino}'
		if key in dicto:
			return dicto[key]
		if not n:
			return mino
		if indo >= len(coins):
			return 10000
		if n < 0:
			return 100100
		dicto[key] = min(optimal_number_of_coinss(n - coins[indo], coins, mino + 1, indo), optimal_number_of_coinss(n, coins, mino, indo + 1))
		return dicto[key]
	return optimal_number_of_coinss(n, coins)


def optimal_number_of_coins(n, A):
	D = {}
	for i in range(1, n + 1):
		D[i] = min((-~j + (i + ~j * x and D[i + ~j * x]) for x in A for j in range(i // x)))
	return D[n]


def optimal_number_of_coins(n, coins):
	return change_making(coins, n)

def _get_change_making_matrix(set_of_coins, r: int):
	m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]
	for i in range(1, r + 1):
		m[0][i] = float('inf')
	return m

def change_making(coins, n: int):
	m = _get_change_making_matrix(coins, n)
	for c in range(1, len(coins) + 1):
		for r in range(1, n + 1):
			if coins[c - 1] == r:
				m[c][r] = 1
			elif coins[c - 1] > r:
				m[c][r] = m[c - 1][r]
			else:
				m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])
	return m[-1][-1]


def optimal_number_of_coins(n, a):
	q = [float('inf')] * (n + 1)
	q[0] = 0
	for i in range(1, n + 1):
		q[i] = min((q[i - x] + 1 for x in a if x <= i))
	return q[n]