プロジェクトオイラー 問８９

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問８９「ローマ数字」
ローマ数字の記法は一つの数について沢山ある場合が存在する (FAQを見よ). 
しかし, ある数については最良の記法が必ず存在する.

例えば, 16の正しい記法を全て並べてみる.

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

最後の例は, 最小の文字数で表せるという意味で, 最も効率が良い.
11Kのテキストファイルroman.txt は1000個のローマ記法で書かれた数を含んでいる.
これらは, 正しい記法に従っている. 即ち, 大きい数から順に書かれていて, 
引き算ペアのルールにも従っている(このルールについてはFAQを見よ)
但し, 最小の文字数で表されているとは限らない.

最小形で書いたときに, 何文字節約できるかを求めよ.

注: ファイル中の全てのローマ数字には, 5つ以上の同じ文字が連続して含まれることはない.


FAQ: ローマ数字のルール

I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

基本法則1
全ての文字は値の大きさの降順に並ぶ

基本法則2
引き算ペアについて.
例えば、4は5の1つ前なのでIVと表せる。
文字は値の大きさの降順に並べる必要があるので、
不適当に出てくる小さな値の文字は引くことを明確に示すとも言える。

X (10) + IX (9) として19=XIXと表せる. 
ただし, 8をIIXと二文字以上を引くことは許されない.

1. I, X, Cのみが引き算ペアの最初の文字として許される. 
2. IはVまたはXの前に来ることが許される 
3. XはLまたはCの前に来ることが許される 
4. CはDまたはMの前に来ることが許される






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def f(sIn):
	c = ["DCCCC CM","CCCC CD", "LXXXX XC", "XXXX XL", "VIIII IX", "IIII IV"]
	L = [s.split() for s in c]
	dif = 0
	pIn = open(sIn)
	for s in pIn.readlines():
		dif += len(s)
		for k in L: s = s.replace(k[0],k[1])
		dif -= len(s)
	pIn.close()
	pIn = None
	return dif
	
import os, sys
sIn = os.path.join(os.path.dirname(__file__), "problem089_roman.txt")
s = f(sIn)
print s

節約できる文字の組み合わせをリストに定義しておきます。

ファイルを１行ずつ読んでローマ数字を取得しながら、置換前の文字数は足してから節約した表記に置換し、置換後の文字数は引いて累計していきます。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。

743