Roman numbers reader

roman_to_number.py

#!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()