The Stonecutter Charges by the Chisel-Mark
The stonecutter of bitwick charges one coin per chisel-mark, and the innkeeper has handed in a draft for a new rune-strip. Patterns are written in the masons' shorthand:
- a lowercase letter
a-zstands for one rune k[P], wherekis a decimal count with no leading zeros andPis itself a pattern, stands for the runes ofPwritten outktimes- patterns written side by side are joined, in order
The draft is s, a string in that shorthand. It is always well-formed, every count in it is at least 1, and the rune sequence it spells out is at most 100 runes long. The empty string is a valid draft and spells out no runes.
Write shortestInscription(s), which returns the shortest string in the same shorthand that spells out exactly the same rune sequence as s. Cost is the number of characters in the string, counting letters, digits and brackets alike. If more than one shortest string exists, return the one that comes first under ordinary character-code comparison of equal-length strings (digits before [, [ before ], ] before letters). For an empty draft, return the empty string.
examples
- case 1
draft of "3[a]""aaa" - the runes are a, a, a; three marks beats the four of "3[a]" - case 2
draft of "2[2[a]]""4[a]" - the runes are four a's; "aaaa" and "4[a]" both cost four, and a digit comes before a letter - case 3
draft of "aabaab""2[aab]" - both it and the plain six runes cost six, and '2' sorts before 'a' - case 4
draft of "2[ab3[c]]""2[abccc]" - writing the three c's out plainly inside the group is cheaper than keeping their count
- reward
- 540 XP
- signature
shortestInscription
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- an empty slab
- three runes beat the brackets
- four runes tie and the digit wins
- nesting flattens into one count
- tie broken by character order
- expanding an inner group pays
- plain runes beat a short count
- already the cheapest inscription
- two runs cut separately
- a single rune