Project Euler — Problem 89 Solution

Problem

The rules for writ­ing Roman numer­als allow for many ways of writ­ing each num­ber (see FAQ:Roman Numer­als). How­ev­er, there is always a “best” way of writ­ing a par­tic­u­lar num­ber.

For exam­ple, the fol­low­ing rep­re­sent all of the legit­i­mate ways of writ­ing the num­ber six­teen:

IIIIIIIIIIIIIIII

VIIIIIIIIIII

VVIIIIII

XIIIIII

VVVI

XVI

The last exam­ple being con­sid­ered the most effi­cient, as it uses the least num­ber of numer­als.

The 11K text file, roman.txt (right click and ‘Save Link/Target As…’), con­tains one thou­sand num­bers writ­ten in valid, but not nec­es­sar­i­ly min­i­mal, Roman numer­als; that is, they are arranged in descend­ing units and obey the sub­trac­tive pair rule (see FAQ for the defin­i­tive rules for this prob­lem).

Find the num­ber of char­ac­ters saved by writ­ing each of these in their min­i­mal form.

Note: You can assume that all the Roman numer­als in the file con­tain no more than four con­sec­u­tive iden­ti­cal units.

Solution

open System.IO

// define the set of available roman numerals
let romanNumerals = [(['I'],1I);(['I';'V'],4I);(['V'],5I);(['I';'X'],9I);
                     (['X'],10I);(['X';'L'],40I);(['L'],50I);(['X';'C'],90I);
                     (['C'],100I);(['C';'D'],400I);(['D'],500I);(['C';'M'],900I);
                     (['M'],1000I)]

// define function to get the numeric value of a roman numeral
let getNumericValue (numeral:char) =
    snd (romanNumerals |> Seq.filter (fun (l, v) -> l.Length = 1 && l.[0] = numeral) |> Seq.head)

// define function to convert a roman numerals to its corresponding numeric value
let toNumeric (numerals:string) =
    let rec toNumericRec ((head::tail):char list) (num:bigint) =
        match head, tail with
        | _, [] -> num + getNumericValue head
        | _, hd::tl when getNumericValue head >= getNumericValue hd ->
            toNumericRec tail (num + getNumericValue head)
        | _, hd::[] -> // subtractive pair as last number i.e. XIX - 19
            num + getNumericValue hd - getNumericValue head
        | _, hd::tl -> // subtractive pair not as last number XCV - 95
            toNumericRec tl (num + getNumericValue hd - getNumericValue head)

    toNumericRec (numerals.ToCharArray() |> Array.toList) 0I

// converts an integer value to corresponding minimal roman numerals form
let toMinimalRomanNumerals (value:bigint) =
    let rec toMinimalRomanNumeralsRec (value:bigint) (list:char list) =
        if value = 0I then list
        else
            let (list', value') =
                romanNumerals
                |> List.sortBy (fun (l, v) -> -v)
                |> Seq.filter (fun (l, v) -> v <= value)
                |> Seq.head
            toMinimalRomanNumeralsRec (value-value') (list@list')

    toMinimalRomanNumeralsRec value []

let original = File.ReadAllLines(@"C:\TEMP\roman.txt")
let minimal = original |> Array.map toNumeric |> Array.map toMinimalRomanNumerals

let answer =
    let originalLen = original |> Array.sumBy (fun str -> str.Length)
    let minimalLen = minimal |> Array.sumBy (fun str -> str.Length)
    originalLen - minimalLen