Tag Archives: Roman Numerals

Euler 89 – Haskell Redux

Just for kicks I decided to revisit my Roman numeral routines from Euler 89.

Admittedly, my earlier Python algorithms were not the most efficient, but they got the job done. Thought it might be worth seeing if Haskell can do it better. As usual, I re-wrote some of the more tighter online routines for clarify and fed the Euler roman.txt file through it to get the same answer.

import Data.Maybe

dec2num :: Integer -> String
dec2num x
	| x == 0 = ""
	| otherwise = b ++ dec2num (x - a)
	where
		(a, b) = head $ filter ((<= x) . fst)
			$ zip [1000,900,500,400,100,90,50,40,10,9,5,4,1]
			["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]

num2dec :: String -> Integer
num2dec n = fst $ foldr (\p (t,s) -> if p >= s then (t+p,p) else (t-p,p)) (0,0)
	$ map (fromJust . flip lookup numMap) n
	where
		numMap = zip "IVXLCDM" [1,5,10,50,100,500,1000]

main = do
	raw <- readFile "roman.txt"
	print $ (sum [length s|s <- lines raw]- sum [length $ dec2num $ num2dec s|s <- lines raw])

Euler 89 – Roman Numerals

Finally got over my programmer’s block and completed another Euler problem. This one deals with optimizing roman numerals.

Created a couple routines to convert between decimals and roman numerals. Simply read in each number, convert it to decimal, and back to numeral again. This essentially optimized the numeral. Add up the savings and presto!

Yeah, yeah, I know there are probably really cool shortcuts you can do, but with these routines, I can convert anything now. And its more fun this way.

def num2dec (numeral):
    decimal = 0
    for n in range(0,len(numeral)):
        if numeral[n] == "M":
            decimal += 1000
        if numeral[n] == "D":
            decimal += 500
        if numeral[n] == "C":
            decimal += 100
            if n != len(numeral)-1:
                if numeral[n+1] == "D" or numeral[n+1] == "M":
                    decimal -= 200
        if numeral[n] == "L":
            decimal += 50
        if numeral[n] == "X":
            decimal += 10
            if n != len(numeral)-1:
                if numeral[n+1] == "L" or numeral[n+1] == "C":
                    decimal -= 20
        if numeral[n] == "V":
            decimal += 5
        if numeral[n] == "I":
            decimal += 1
            if n != len(numeral)-1:
                if numeral[n+1] == "V" or numeral[n+1] == "X":
                    decimal -= 2
    return decimal
def dec2num (decimal):
    numeral = ""
    for i in range (0, decimal // 1000):
        numeral += "M"
        decimal -= 1000
    if decimal >= 900:
        numeral += "CM"
        decimal -= 900
    for i in range (0, decimal // 500):
        numeral += "D"
        decimal -= 500
    if decimal >= 400:
        numeral += "CD"
        decimal -= 400
    for i in range (0, decimal // 100):
        numeral += "C"
        decimal -= 100
    if decimal >= 90:
        numeral += "XC"
        decimal -= 90
    for i in range (0, decimal // 50):
        numeral += "L"
        decimal -= 50
    if decimal >= 40:
        numeral += "XL"
        decimal -= 40
    for i in range (0, decimal // 10):
        numeral += "X"
        decimal -= 10
    if decimal == 9:
        numeral += "IX"
        decimal -= 9
    for i in range (0, decimal // 5):
        numeral += "V"
        decimal -= 5
    if decimal == 4:
        numeral += "IV"
        decimal -= 4
    for i in range (0, decimal // 1):
        numeral += "I"
        decimal -= 1
    return numeral
if __name__=="__main__":
    sum = 0
    for n in open("C://Python27//roman.txt", "r"):
        n = n.rstrip('\n')
        sum += len(n) - len(dec2num(num2dec(n)))
    print "Answer =", sum