【Project Euler】Problem 89: ローマ数字

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 89.ローマ数字

原文 Problem 89: Roman numerals

問題の要約：ファイルから読み込んだローマ数字は長さが最適化されていない。これを最短の表現に変換して短くなった文字数の合計を求めよ

ローマ数字から数字に変換するrom2numと数字を最短の表現に変換するnum2romを作ってその長さの差の合計を求めます。例によってファイルの読み込みは下に添付しました。

romv = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
def rom2num(r):
  return sum([-romv[r[i]] if romv[r[i]]<romv[r[i+1]] else romv[r[i]]   
              for i in range(len(r)-1)])+romv[r[-1]]
romc = [('I', 'V', 'X'), ('X', 'L', 'C'), ('C', 'D', 'M'), ('M', 'MMM', '')] 

def num2rom(n):
  def _d2r(d, i, v, x):  # digit to roman number 
    return ['', i, i * 2, i * 3, i + v, v, v + i, v + i * 2, v + i * 3, i + x][d]
  
  return "".join([_d2r(int(d), *romc[3-i]) for i, d in enumerate(format(n,"04"))])

print(f"Answer: {sum([len(rn)-len(num2rom(rom2num(rn))) for rn in roman])}")

ファイルの読み込み

# show upload dialog
from google.colab import files
uploaded = files.upload()
f = open("p089_roman.txt")
roman = f.readlines()
f.close()
roman = list(map(lambda s: s.strip(),roman))
print(len(roman),roman[:10])

（開発環境：Google Colab）