The Cellar Under the Broken Barrel
The cellar under the Broken Barrel inn is measured in weight, not in casks, and the cellarer has been promising for a month to write the tally down.
Build Cellar, a class constructed with one argument:
capacity— a non-negative integer, the total weight the cellar can hold at once.
The cellar holds casks. Each cask has a name (a string, unique in the cellar), a weight (a positive integer) and a rank (an integer; a larger rank is more precious). The cellar also remembers the order in which casks were last touched: a cask is touched when it is successfully stored and when it is successfully fetched.
The free weight is capacity minus the total weight of the casks currently stored.
store(name, weight, rank) attempts to put a cask in, and behaves as follows:
1. If a cask with this name is already stored, the call is a replacement: for the rest of this call that old entry is treated as no longer in the cellar, so its weight does not count and its old rank plays no part. 2. The attempt is refused if, even after also removing every stored cask whose rank is strictly less than rank, the free weight would still be less than weight. 3. If it is refused, nothing at all changes — in particular, a cask that was to be replaced keeps its old weight, its old rank and its place in the touch order — and the return value is false. 4. Otherwise, casks are removed one at a time until the free weight is at least weight. Each removal takes, among the stored casks whose rank is strictly less than rank, the one with the lowest rank; if several tie at that lowest rank, the one touched longest ago. 5. The new cask is then stored and is the most recently touched cask. Return the list of names removed by rule 4, in the order they were removed — an empty list if none were.
fetch(name) returns the weight of the named cask and makes it the most recently touched. If no cask of that name is stored, it returns 0 and nothing changes.
roster() returns the list of stored cask names, most recently touched first.
examples
- case 1
capacity 10; store("ale", 4, 1), store("mead", 4, 1), store("wine", 4, 2)the third call returns ["ale"] — ale and mead both have rank 1, and ale was touched longest ago; roster() is then ["wine", "mead"] - case 2
capacity 6; store("a", 3, 2), store("b", 3, 2), store("c", 2, 2)the third call returns false — only casks of strictly lower rank may be removed and there are none — so a and b stay and roster() is ["b", "a"] - case 3
capacity 10; store("a", 4, 2), store("b", 4, 2), store("a", 7, 2)the third call returns false — b's 4 cannot be moved, so only 6 of the 10 could ever be free for a weight of 7 — and a is still stored at weight 4
- reward
- 520 XP
- signature
Cellar
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- the least precious cask leaves first
- equal rank is never evicted
- fetching renews a cask
- several removals in rank order
- a refused replacement changes nothing
- a replacement frees its own weight
- a cellar with no room at all