|
# usage: |
|
# python3 coin_change.py |
|
|
|
import sys |
|
from collections import defaultdict |
|
|
|
CONVERT_TO_INTEGER = 100000 |
|
|
|
measurements = { |
|
"1cup": 237, |
|
"1half_cup": 118.5, |
|
"1quarter_cup": 59.25, |
|
"1third_cup": 79, |
|
"1eighth_cup": 29.625, |
|
|
|
"2tablespoon": 14.8125, |
|
"2half_tablespoon": 7.40625, |
|
|
|
"3teaspoon": 4.9375, |
|
"3half_teaspoon": 2.46875, |
|
#"quarter_teaspoon": 1.234375, |
|
} |
|
|
|
cup_names = { |
|
"1cup": 'cup', |
|
"1half_cup": '1/2 cup', |
|
"1quarter_cup": '1/4 cup', |
|
"1third_cup": '1/3 cup', |
|
"1eighth_cup": '1/8 cup', |
|
|
|
"2tablespoon": 'tablespoon', |
|
"2half_tablespoon": '1/2 tablespoon', |
|
|
|
"3teaspoon": 'teaspoon', |
|
"3half_teaspoon": '1/2 teaspoon', |
|
} |
|
|
|
for key, value in measurements.items(): |
|
measurements[key] *= CONVERT_TO_INTEGER |
|
measurements[key] = round(measurements[key]) |
|
|
|
# ensure we have the proper conversions |
|
# to simplify the devices used |
|
assert(measurements["1cup"] == 2*measurements["1half_cup"]) |
|
assert(measurements["1cup"] == 4*measurements["1quarter_cup"]) |
|
assert(measurements["1cup"] == 3*measurements["1third_cup"]) |
|
assert(measurements["1cup"] == 8*measurements["1eighth_cup"]) |
|
|
|
assert(measurements["2tablespoon"] == 2*measurements["2half_tablespoon"]) |
|
|
|
assert(measurements["3teaspoon"] == 2*measurements["3half_teaspoon"]) |
|
|
|
assert(measurements["1cup"] == 16*measurements["2tablespoon"]) |
|
assert(measurements["1cup"] == 48*measurements["3teaspoon"]) |
|
|
|
|
|
def cup_change(to_make): |
|
to_make *= 100000 |
|
|
|
coins = [1000000000] * (to_make+1) |
|
solution = [None] * (to_make+1) |
|
|
|
coins[0] = 0 |
|
for x in range(1, to_make+1): |
|
for name, c in measurements.items(): |
|
if x - c >= 0 and coins[x - c] + 1 < coins[x]: |
|
coins[x] = coins[x - c] + 1 |
|
solution[x] = name |
|
|
|
val = max([i for i, v in enumerate(range(to_make + 1)) if solution[v] is not None]) |
|
initial_val = val |
|
|
|
cups = [] |
|
result = 0 |
|
while val > 0: |
|
measurement_used = solution[val] |
|
result += measurements[solution[val]] |
|
val -= measurements[solution[val]] |
|
cups.append(measurement_used) |
|
|
|
errorML = (result - to_make) / CONVERT_TO_INTEGER |
|
return cups, errorML |
|
|
|
if __name__ == '__main__': |
|
|
|
# print everything in markdown pls |
|
print('| mL | what to use | error (mL)') |
|
print('|:---|:------------|:------------') |
|
for mL in [50, 100, 200, 600, 800, 950]: |
|
coins, error = cup_change(mL) |
|
coins = sorted(coins) |
|
coins_counts = defaultdict(int) |
|
for coin in coins: |
|
coins_counts[coin] += 1 |
|
|
|
coins_as_str = '' |
|
for coin, amount in coins_counts.items(): |
|
# only aggregate whole measurements |
|
name = cup_names[coin] |
|
if amount > 1 and (name == 'cup' or name == 'teaspoon' or name == 'tablespoon'): |
|
coins_as_str += (f'{amount} {name}s') |
|
else: |
|
coins_as_str += (f'{name}') |
|
|
|
coins_as_str += '<br>' |
|
|
|
print(f'| {mL}mL | {coins_as_str} | {error}mL | ') |