Skip to content

Instantly share code, notes, and snippets.

@rkz
Last active Jun 16, 2019
Embed
What would you like to do?
Roman numbers reader
#!python3
"""
Usage: roman_to_number.py [-v] <roman_number>
Read a roman number (e.g. CDXCVII) and print its base10 value (e.g. 497).
Options:
-v Show computation steps and error details
"""
import docopt
import sys
def main():
options = docopt.docopt(__doc__)
global verbose
verbose = options["-v"]
roman_number = options["<roman_number>"]
try:
print(read_roman(roman_number))
except ValueError as e:
log(f"parse error: {e}")
print(f"Illegal roman number '{roman_number}'", file=sys.stderr)
exit(1)
def read_roman(roman_number):
"""Read an uppercase roman number and return its base10 value. Raise `ValueError` if `roman_number` contains illegal
characters."""
seq = roman_to_digits_sequence(roman_number)
return compute_digits_sequence(seq)
def roman_to_digits_sequence(roman_number):
"""
Turn a roman number into the sequence of its digits' individual base10 values, e.g.:
roman_to_digits_sequence('XXVI') = [10, 10, 5, 1]
Raise `ValueError` if `roman_number` contains illegal characters.
"""
digit_map = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
try:
return [digit_map[x] for x in roman_number]
except KeyError:
raise ValueError(f"Roman number '{roman_number}' contains illegal digits")
def compute_digits_sequence(seq):
"""
Compute the value of a roman digits sequence:
reduce_digits_sequence([10, 1, 5]) = 14
"""
log(f"compute_digits_sequence: {seq}")
if len(seq) == 0:
return 0
elif len(seq) == 1:
return seq[0]
# When the first digit is the highest of the sequence, it adds up to the remainder
# e.g. LXXIX = L + XXIX
elif seq[0] == max(seq):
return seq[0] + compute_digits_sequence(seq[1:])
# Otherwise it means the sequence begins with an increasing sub-sequence that computes differently
else:
initial_seq, remainder = split_initial_increasing_seq(seq)
log(f"sequence is not max'ed by its first element: initial_seq = {initial_seq}, remainder = {remainder}")
return compute_increasing_sequence(initial_seq) + compute_digits_sequence(remainder)
def split_initial_increasing_seq(seq):
"""
Cut a sequence in two parts (returning a pair of sequences):
1. longest initial sub-sequence of increasing digits
2. the rest of digits
"""
if seq[0] == max(seq):
raise ValueError(f"Sequence {seq} has no initial increasing sub-sequence")
if len(seq) < 2:
raise ValueError("Cannot extract an initial increasing sub-sequence of a <2-digit sequence")
initial_seq = []
rest = seq.copy()
# Transfer digits for the left of `rest` to the right of `initial_seq` as long as it makes `initial_seq` increasing
while len(initial_seq) == 0 or (len(rest) > 0 and rest[0] >= initial_seq[-1]):
initial_seq.append(rest.pop(0))
return initial_seq, rest
def compute_increasing_sequence(seq):
"""
Compute the value of an increasing sequence. By construction it will be formed like [n, ..., n, p] with n < p, and
evaluate p - (n + ... + n).
"""
# Check the sequence format
if len(seq) < 2:
raise ValueError(f"Increasing sequence {seq} is too short")
n = seq[0]
p = seq[-1]
if len(set(seq[0:-1])) > 1:
raise ValueError(f"Increasing sequence {seq} has too much values")
if not (n < p):
raise ValueError(f"Sequence {seq} is not increasing")
# Compute
return p - n * (len(seq) - 1)
verbose = False
def log(message):
"""Write a log only in verbose mode."""
global verbose
if verbose:
print(message)
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment