SHOW:
|
|
- or go back to the newest paste.
| 1 | # -------------- tasks/escher_tasks/task_9__treasures.py ---------------- | |
| 2 | ||
| 3 | ||
| 4 | def treasures(info, limit): | |
| 5 | - | return [] |
| 5 | + | |
| 6 | limit = int(limit * 1000) | |
| 7 | keys = sorted(info, | |
| 8 | key=lambda k: info[k]["price"] / info[k]["weight"], | |
| 9 | reverse=True) | |
| 10 | ||
| 11 | res = {}
| |
| 12 | - | from tasks.escher_tasks.task_9__treasures import treasures |
| 12 | + | for k in keys: |
| 13 | can_take = limit // info[k]["weight"] | |
| 14 | will_take = min(can_take, info[k]["amount"]) | |
| 15 | - | def test_treasures(): |
| 15 | + | res[k] = will_take |
| 16 | limit -= will_take * info[k]["weight"] | |
| 17 | - | assert treasures( |
| 17 | + | |
| 18 | return [f"{k}: {res[k]}" for k in info if res[k] > 0]
| |
| 19 | ||
| 20 | ||
| 21 | from itertools import product | |
| 22 | ||
| 23 | - | assert treasures( |
| 23 | + | |
| 24 | def treasures_2(info, limit): | |
| 25 | ||
| 26 | limit = int(limit * 1000) | |
| 27 | ||
| 28 | counts = {}
| |
| 29 | for k in info: | |
| 30 | can_put = limit // info[k]["weight"] | |
| 31 | will_put = min(can_put, info[k]["amount"]) | |
| 32 | counts[k] = will_put | |
| 33 | ||
| 34 | res = [0 for _ in info] | |
| 35 | best_price = 0 | |
| 36 | ||
| 37 | for combination in product(*[range(counts[k] + 1) for k in info]): | |
| 38 | total_price = sum([amount * info[k]["price"] | |
| 39 | for k, amount in zip(info, combination)]) | |
| 40 | total_weight = sum([amount * info[k]["weight"] | |
| 41 | for k, amount in zip(info, combination)]) | |
| 42 | ||
| 43 | if total_weight <= limit and total_price > best_price: | |
| 44 | res = combination | |
| 45 | best_price = total_price | |
| 46 | ||
| 47 | return [f"{k}: {count}" for k, count in zip(info, res) if count]
| |
| 48 | ||
| 49 | ||
| 50 | def treasures_3(info, limit): | |
| 51 | ||
| 52 | limit = int(limit * 1000) | |
| 53 | best_results = [[0 for _ in info]] | |
| 54 | ||
| 55 | for i in range(1, limit + 1): | |
| 56 | results = [best_results[-1].copy()] | |
| 57 | ||
| 58 | for _idx, k in enumerate(info): | |
| 59 | if i < info[k]["weight"]: | |
| 60 | continue | |
| 61 | ||
| 62 | res = best_results[i - info[k]["weight"]].copy() | |
| 63 | res[_idx] += 1 | |
| 64 | if res[_idx] > info[k]["amount"]: | |
| 65 | continue | |
| 66 | results.append(res) | |
| 67 | ||
| 68 | get_price = lambda res: sum(i * info[k]["price"] | |
| 69 | for i, k in zip(res, info)) | |
| 70 | best_results.append(max(results, key=get_price)) | |
| 71 | ||
| 72 | return [f"{k}: {i}" for k, i in zip(info, best_results[-1]) if i]
| |
| 73 | ||
| 74 | ||
| 75 | # ---------------- tests/test_escher_tasks/test_task_9__treasures.py ------------------ | |
| 76 | ||
| 77 | ||
| 78 | import pytest | |
| 79 | from tasks.escher_tasks.task_9__treasures import ( | |
| 80 | treasures, treasures_2, treasures_3) | |
| 81 | ||
| 82 | ||
| 83 | @pytest.mark.parametrize("func", [treasures, treasures_2, treasures_3])
| |
| 84 | def test_treasures(func): | |
| 85 | ||
| 86 | assert func( | |
| 87 | {'golden coin': {'price': 100, 'weight': 50, 'amount': 200},
| |
| 88 | 'silver coin': {'price': 10, 'weight': 20, 'amount': 1000},
| |
| 89 | 'ruby': {'price': 1000, 'weight': 200, 'amount': 2}}, 5
| |
| 90 | ) == ['golden coin: 92', 'ruby: 2'] | |
| 91 | ||
| 92 | assert func( | |
| 93 | {'golden coin': {'price': 100, 'weight': 50, 'amount': 100},
| |
| 94 | 'silver coin': {'price': 10, 'weight': 20, 'amount': 100},
| |
| 95 | 'ruby': {'price': 1000, 'weight': 200, 'amount': 1}}, 7.5
| |
| 96 | ) == ['golden coin: 100', 'silver coin: 100', 'ruby: 1'] | |
| 97 |
