The Cask-Keeper's Cellar
The inn's cask-keeper has gone to market and left the cellar untended. Casks come down the ramp all day; the cellar holds only so much weight, and every cask carries a rank — the higher the rank, the more the keeper wants it kept.
Build Cellar, constructed with capacity, a non-negative integer giving the total weight the cellar can hold. Cask names are strings, weights are positive integers, ranks are non-negative integers. It supports three operations.
`store(name, weight, rank)` — returns a list of the names evicted by this call, in the order they were removed (an empty list if none). It proceeds as follows:
1. If name already names a cask in the cellar, that cask is removed first and its weight freed. This removal is not an eviction, is not reported, and it happens even if the arriving cask is then turned away. 2. The arriving cask is admitted only if it can be made to fit by removing casks of rank less than or equal to its own: that is, only if the free space plus the total weight of all casks whose rank is ≤ rank is at least weight. If it cannot, nothing further changes and an empty list is returned. 3. Otherwise casks are removed one at a time until the free space is at least weight. Each removal takes the cask of lowest rank; among casks of equal rank, the one least recently touched. The arriving cask is then placed in the cellar.
`fetch(name)` — if a cask of that name is in the cellar, returns its weight (an integer); otherwise returns -1 and changes nothing.
`order()` — returns the names of the casks currently in the cellar as a list, arranged in the order they would be evicted: lowest rank first, and among equal ranks the least recently touched first.
A cask is touched exactly twice-over: when it is placed by a store that admits it, and when a fetch finds it. Nothing else touches a cask.
examples
- case 1
capacity 10; store ale (weight 4, rank 1), store hay (3, rank 0), store oil (3, rank 0), fetch hay, then store gem (4, rank 2)the gem store returns ["oil", "hay"] — both rank-0 casks go, oil first because the fetch made hay the more recently touched of the two. Afterwards order() is ["ale", "gem"]. - case 2
capacity 6 holding only crown (weight 5, rank 5); store sack (weight 3, rank 1)an empty list, and sack is not in the cellar: only 1 weight is free and there is nothing of rank 1 or lower to remove, so nothing is disturbed. - case 3
capacity 5 holding keg (weight 3, rank 3) and jar (weight 2, rank 1); store jar again with weight 4 and rank 0an empty list — the old jar is cleared first, then the new jar is refused (2 free, nothing of rank 0 or lower to remove). A later fetch of jar returns -1.
- reward
- 500 XP
- signature
Cellar
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- rank falls before age
- the crown will not be moved
- re-shelving clears the old cask
- a cellar with no room at all
- one cask fills the cellar