↑ ↓ to move · enter to open

012 · Intermediate · Mapping, iteration

roman numerals

Seven symbols, each with a fixed value, and one twist: a smaller symbol written before a larger one is subtracted. Reading a numeral takes a single pass with a one-symbol look-ahead. Writing one takes a greedy walk down a 13-entry table, and each decimal digit turns out to be spelled on its own.

LAB 1

read it left to right

Map each symbol to its value: I 1 V 5 X 10 L 50 C 100 D 500 M 1000. Walk the string once. If a symbol is smaller than the one after it, subtract it. Otherwise add it. Type any numeral, including broken ones, and watch both the scan and the rules check.

Try

How to read this: Each tile is one symbol with its value underneath. The number above it shows whether it was added (+) or subtracted (−).

  • amber glow: symbol being read
  • dashed amber: the next symbol it is compared with
  • green: added
  • dashed green, amber −n: subtracted because a bigger symbol follows
  • red underline: breaks a writing rule
  • gold border: finished and valid

Try this: Press 1994, then Step: watch C get subtracted because M comes after it. Then try a broken one like IC.

—
Value
0
Running total
0
Comparisons
—
Standard numeral?

This step—

CodeO(n) time · O(1) space


        

Why one look-ahead is enough

In a standard numeral the values never go up from one symbol to the next, except inside a subtractive pair such as CM or IV. So the symbols that must be subtracted are exactly the ones smaller than their right neighbor.

The right-to-left scan applies the same test from the other end: it remembers the symbol it just read instead of peeking ahead. Both read each symbol once. Try IC or VX: the scan still returns a number, so checking the rules is a separate job.

LAB 2

write it greedily

To go the other way, list the seven symbols plus the six subtractive pairs in descending order. Take the largest value that still fits, append its symbols, subtract, and repeat. Switch to the seven plain symbols to see what goes wrong without the pairs.

n left0 numeral

How to read this: The row of tiles is the list of pieces, biggest first. The walk moves left to right, taking a piece whenever it still fits in what's left.

  • amber: piece being tested
  • gold: piece taken right now
  • green ×k: taken k times so far
  • faded: skipped past

Try this: Switch to 7 symbols only with n = 4 and see it write IIII instead of IV.

—
Numeral
0
Length
0
Comparisons
0
Entries taken

This step—

CodeO(1): at most — comparisons


        

Why greedy works here

Within one decimal place the table holds 9, 5, 4 and 1 of that place (900, 500, 400, 100 for hundreds). Greedy spells a digit d as 9 if d = 9, as 5 plus ones for 5 to 8, as 4 if d = 4, and as ones for 0 to 3. That is exactly the standard spelling, so greedy cannot pick a worse option.

Greedy never mixes places either. Once the thousands are taken, less than 1000 is left, so no thousands entry fits again. Once the hundreds are taken, less than 100 is left, and so on down. Greedy can fail when values do not nest this neatly. The knapsack lab in 004 · Dynamic programming shows greedy by value per kilo losing.

LAB 3

every number from 1 to 3999

Each decimal digit maps to its own chunk of symbols, so a numeral is four lookups glued together. Sweep through all 3999 numbers to plot numeral length against n, track the longest one found so far, and pick any n to see its digits light up in the pattern table.

length vs n

How to read this: Each dot is one number.

  • amber line and dot: the number you picked
  • gold ring: the longest numeral so far

Try this: Press Sweep, or move the pointer across the chart to pick a number.

How to read this: Find each digit of n in its row; the gold cells glued together spell the numeral. A dot writes nothing, and a dash can't happen (there is no 4000 or more).

—
Longest so far
0
Numbers scanned
—
Average length
—
Length of n

This number—

roman(n) = TH[d₃] + H[d₂] + T[d₁] + O[d₀]

Length histogram—

↑ how many numbers
numeral length (letters) →

Amber is the length of your n, gold the longest. Digit lengths are 0 1 2 3 2 1 2 3 4 2 for 0 to 9, so the most a place can add is 4 (for 8), and the thousands add at most 3. The ceiling is 3 + 4 + 4 + 4 = 15, reached only by 3888. Counting 0 as the empty numeral, the histogram is symmetric: as many numbers have length k as 15 − k.

Why it stops at 3999

The largest symbol is M = 1000 and no symbol may repeat more than three times, so the thousands digit tops out at MMM. Writing 4000 would need MMMM or a symbol for 5000, and the standard set has neither. That makes MMMCMXCIX = 3999 the largest standard numeral. There is no zero either: the empty string is the closest thing.