kenju's blog

About Programming and Mathematics

Programming Contest: 数字をローマ数字に変換する

exercism.io をやっていて、http://exercism.io/tracks/ruby/exercises/roman-numerals という問題に出くわした。数字が渡されたときに、ローマ数字(String)に変換するメソッドを実装しろ、というものだ。

Problem

Specの一部抜粋は以下のような感じ。

  def test_1
    # skip
    assert_equal 'I', 1.to_roman
  end

  def test_27
    # skip
    assert_equal 'XXVII', 27.to_roman
  end

  def test_402
    # skip
    assert_equal 'CDII', 402.to_roman
  end

  def test_1024
    # skip
    assert_equal 'MXXIV', 1024.to_roman
  end

Solution

Solution A

幾つか方法はある。まず思いつくのが、数字とローマ数字のMappingを用意して逐次変換するというもの。

NUM_TO_ROMAN = {
  1: 'I',
  2: 'II',
  ...
  40: 'XL',
  ...
}

そして、与えられた数字を桁数ごとに分割して、そのMappingから構築するというもの。

n = 481
digits = to_digit(480) #=> [400, 80, 1]
mapped = digits.map { |d| from_mapping(d) } #=> ['CD', 'LXXX', 'I']
result = mapped.join #=> 'CDLXXXI'

ただし、このアルゴリズムの欠点は、Mappingに使うNUM_TO_ROMANが冗長になること。大体30~40程度のkeyを必要とする。あまりイケてない。

そこで、別の方法を考える。

Solution B

ここで、1 ~ 10までのローマ数字は、桁数の基数を無視するとして、以下のパターンで構築されることに気づく。 例えば、400の場合、

  • 桁:4
  • 基数:100

なので、(α, β, γ) = (C, D, M)とした時、4 => 'αβ'すなわち'CD'で表現できる、と考えるのだ。

  #    1 digit: I, V, X
  #   10 digit: X, L, C
  #  100 digit: C, D, M
  # 1000 digit: M
  DIGIT_TO_TEMPLATE = {
    1 => 'α',
    2 => 'αα',
    3 => 'ααα',
    4 => 'αβ',
    5 => 'β',
    6 => 'βα',
    7 => 'βαα',
    8 => 'βααα',
    9 => 'αγ',
    10 => 'γ'
  }

基数と、(α, β, γ)に用いる実際のローマ数字とのMappingは、以下の通り。

  BASE_TO_ROMAN_MAP = {
    1 => {
      'α': 'I',
      'β': 'V',
      'γ': 'X',
    },
    10 => {
      'α': 'X',
      'β': 'L',
      'γ': 'C',
    },
    100 => {
      'α': 'C',
      'β': 'D',
      'γ': 'M',
    },
    1000 => {
      'α': 'M',
    },
  }

これらを利用すると、DIGIT_TO_TEMPLATEで表現するテンプレートに、BASE_TO_ROMAN_MAPで取得できるローマ数字のMappingを、基数に応じて注入する、というテンプレートパターンで解決できることになる。

具体的なコード例は以下の通り:

  [400, 40, 8].map { |d|
      base = 10 ** (d.digits.size - 1) #=> 100
      digit = base == 0 ? d : d / base #=> 4
      template = DIGIT_TO_TEMPLATE[digit] #=> 'αβ'
      roman_map = BASE_TO_ROMAN_MAP[base] #=> { 'α': 'C', 'β': 'D', 'γ': 'M', },
      roman_map.reduce(template) { |acc, (k, v)|
        acc.gsub(/#{k}/, v) #=> 'CD'
      }
    }.join('') # 'CDLXVIII'

Conclusion

以上をまとめたコード全てを再掲すると、以下になる。 なお、テスト要件の都合上 Integer classにメソッドを生やしているが、現実のアプリケーションではdefault APIにメソッドを生やすのは可能な限り避けるべき。

class Integer
  #    1 digit: I, V, X
  #   10 digit: X, L, C
  #  100 digit: C, D, M
  # 1000 digit: M
  DIGIT_TO_TEMPLATE = {
    1 => 'α',
    2 => 'αα',
    3 => 'ααα',
    4 => 'αβ',
    5 => 'β',
    6 => 'βα',
    7 => 'βαα',
    8 => 'βααα',
    9 => 'αγ',
    10 => 'γ'
  }

  BASE_TO_ROMAN_MAP = {
    1 => {
      'α': 'I',
      'β': 'V',
      'γ': 'X',
    },
    10 => {
      'α': 'X',
      'β': 'L',
      'γ': 'C',
    },
    100 => {
      'α': 'C',
      'β': 'D',
      'γ': 'M',
    },
    1000 => {
      'α': 'M',
    },
  }


  def to_roman
    # if n = 448
    # [400, 40, 8]
    to_digits.reject { |d|
      d == 0
    }.map { |d|
      # ['CD', 'LX', 'VIII']
      # ex.400 = 4 * 100
      # 100 = ('αβ') = ('CD')
      base = 10 ** (d.digits.size - 1) #=> 100
      digit = base == 0 ? d : d / base #=> 4
      template = DIGIT_TO_TEMPLATE[digit] #=> 'αβ'
      roman_map = BASE_TO_ROMAN_MAP[base] #=> { 'α': 'C', 'β': 'D', 'γ': 'M', },
      roman_map.reduce(template) { |acc, (k, v)|
        acc.gsub(/#{k}/, v) #=> 'CD'
      }
    }.join('') # 'CDLXVIII'
  end

  # 488 to [400, 88, 8]
  def to_digits
    digits.map.with_index {
      |v, i| v * 10 ** i
    }.reverse
  end
end