The Thousand-Notch Gate
The east gate of bitwick is a dial of one thousand notches, numbered 0 through 999. Every cart down the road carries an inscription chalked on its tailboard, and the gatekeeper must turn the dial to the notch that inscription names — or turn the cart away, if the chalk is nonsense.
Write gateNotch(expr), where expr is a string. It returns an integer in 0..999, or null (None in Python) if expr is not a well-formed inscription.
The chalk. An inscription is made of tokens. A run of one or more decimal digits is a number token (any length, leading zeros allowed). Each of +, -, *, ^, (, ) is a token on its own. Spaces may appear anywhere between tokens and are ignored, but they never join: 1 2 is two number tokens, not one. Any other character makes the inscription malformed.
The dial. Every value is a notch in 0..999. A number token is its decimal value modulo 1000. Addition, subtraction and multiplication are taken modulo 1000. Prefix - applied to a value v gives (1000 - v) mod 1000. a ^ b is the product of b copies of a, modulo 1000, where b is the value of the right operand (which is therefore always in 0..999); the product of zero copies is 1, so a ^ 0 is 1 for every a, including a of 0.
The binding. From loosest to tightest: binary + and -; then binary *; then prefix -; then ^. The binary +, - and * are left-associative; ^ is right-associative. Parentheses group. A prefix - may stand before any operand and may repeat. There is no prefix +. So:
a - b - cis(a - b) - c, anda * b * cis(a * b) * ca ^ b ^ cisa ^ (b ^ c)-a ^ bis-(a ^ b)a ^ -bisa ^ (-b), anda * -bisa * (-b)
Nonsense. The inscription is malformed if it contains any character outside those tokens and the space, or if its tokens do not form exactly one complete expression. That covers: an empty or blank string, an operator with a missing operand (a leading +, a trailing operator, a * or ^ with nothing usable before or after it), two number tokens side by side, empty parentheses, and unmatched parentheses.
Return the notch as an integer, or null/None for nonsense.
examples
- case 1
expr of "100 - 20 - 30"50 — the minus signs bind left to right, so it is (100 - 20) - 30, not 100 - (20 - 30) - case 2
expr of "-3^2"991 — the power is taken first, giving 9, and the whole of it is negated: 1000 - 9 - case 3
expr of "2^-3"672 — the right operand is -3, which is the notch 997, and the product of 997 copies of 2 modulo 1000 is 672 - case 4
expr of "1 2"null (None) — a space never joins digits, so this is two number tokens side by side and the chalk is nonsense
- reward
- 540 XP
- signature
gateNotch
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- multiplication before addition
- subtraction runs backwards round the dial
- minus signs bind left to right
- powers bind right to left
- prefix minus negates the whole power
- exponent wrapped round the dial
- repeated prefix minus
- minus on the right of a binary minus
- prefix minus after a star
- literal larger than the dial
- parentheses group both sides
- nested parentheses around one number
- zero copies of zero
- zero power tower
- negating the top notch
- blank chalk
- spaces only
- no prefix plus
- trailing operator
- unmatched opening paren
- spare closing paren
- empty parentheses
- two numbers side by side
- stranger to the alphabet
- doubled star has no prefix form