# Project Euler Problem 89

Solving Problem 89 was easy. In fact, solving the problem does not require any conversion of the source data as the question is how much shorter the converted numbers are going to be. It can be derived from the problem outline that cases for the length reduction are **IIII**, VIIII, XXXX, LXXXX, CCCC, and DCCCC. As each reduction of these yields just two digits, correspondent reductions are going to be **2**,**3**,**2**,**3**,**2**,**3**. Accumulating all reductions, being applied from the beginning of the file each time for the closest available reduction to the end will be the sought solution. Very simple recursive function **reduce** does exactly this.

open System.IO let rec reduce saved (roman: string) = match ([| "IIII"; "VIIII"; "XXXX"; "LXXXX"; "CCCC"; "DCCCC" |] |> Array.map (fun x -> (x, roman.IndexOf(x))) |> Array.filter (fun (x, i) -> i >= 0)) with | [||] -> saved | _ as a -> a |> Array.minBy(fun (x,i) -> i) |> fun (x,i) -> reduce (saved + x.Length - 2) (roman.Substring(i + x.Length)) let problem089() = File.ReadAllText( @"..\..\..\Datafiles\Problem089.data") |> reduce 0

Advertisements

Leave a Comment