The Tollmaster's Amended Rulebook

# The Tollmaster's Amended Rulebook

The east gate of bitwick charges every cart that rolls through it. The rulebook has been amended so many times — a levy here, a rebate there, a waiver granted one winter and never struck out — that the clerk who used to read it has taken to her bed. The gate still needs a number for each cart.

The cart. cart is a mapping from attribute names to values, both strings (a plain object in TypeScript, a dict in Python). For example, a cart may carry a goods attribute, a wheels attribute, and so on. Nothing is assumed about which attributes exist.

The rules. rules is a list of rule objects, each with exactly these fields:

• when — a mapping from attribute name to a required value, both strings.
• kind — one of "base", "add", "free".
• amount — an integer, possibly negative. Ignored when kind is "free".
• rank — an integer, possibly negative.
• group — a string. Ignored unless kind is "add". The empty string is an ordinary group name.

Matching. A rule matches the cart when every entry of when is satisfied. For a key k with required value v:

• if v is "*", the cart must contain k (any value);
• if v begins with "!", the cart must contain k and the cart's value must not equal v without that leading "!";
• otherwise the cart must contain k and the cart's value must equal v.

An empty when matches every cart.

Precedence. Of two rules, the one with the greater rank outranks the other. If the ranks are equal, the one whose when has more entries outranks the other. If those counts are also equal, the one appearing later in rules outranks the other.

The toll.

1. Look at the matching rules whose kind is "base" or "free". If there are none, the base charge is 0. Otherwise take the single highest-precedence one among them: if it is "free", the toll is 0 and no surcharge is applied; if it is "base", the base charge is its amount. 2. Look at the matching rules whose kind is "add". Partition them by group; within each group only the highest-precedence one applies. The surcharge is the sum of those winners' amounts. 3. The toll is the base charge plus the surcharge, but never less than 0.

Write tollFor(rules, cart), which returns the toll as an integer.