Solution to problem
number 89 of Project Euler.
Question # 89
The rules for writing Roman numerals allow for many ways of writing each number (see About Roman Numerals...). However, there is always a "best" way of writing a particular number.
For example, the following represent all of the legitimate ways of writing the number sixteen:
The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; that is, they are arranged in descending units and obey the subtractive pair rule (see About Roman Numerals... for the definitive rules for this problem).
Find the number of characters saved by writing each of these in their minimal form.
The "descending size" rule was introduced to allow the use of subtractive combinations. For example, four can be written IV because it is one before five. As the rule requires that the numerals be arranged in order of size it should be clear to a reader that the presence of a smaller numeral out of place, so to speak, was unambiguously to be subtracted from the following numeral. For example, nineteen could be written XIX = X + IX (9). Note also how the rule requires X (ten) be placed before IX (nine), and IXX would not be an acceptable configuration.
Generally the Romans tried to use as few numerals as possible when displaying numbers. For this reason, XIX would be the preferred form of nineteen over other valid combinations, like XVIIII or XVIV. However, this was NOT a rule and there still remain in Rome many examples where economy of numerals has not been employed. For example, in the famous Colesseum the the numerals above the forty-ninth entrance is written XXXXVIIII and not IL nor XLIX (see rules below).
Despite this, over time we have continued to introduce new restrictive rules. By mediaeval times it had become standard practice to avoid more than three consecutive identical numerals. That is, IV would be written instead of IIII, IX would be used instead of VIIII, and so on. In addition, the subtractive combinations had the following rules superimposed:
It is also expected that higher denominations should be used whenever possible; for example, L should be used in place of XXXXX, or C should be used in place of LL. However, even this "rule" has been flaunted: in the church of Sant'Agnese fuori le Mura (St Agnes' outside the walls), found in Rome, the date, MCCCCCCVI (1606), is written on the gilded and coffered wooden ceiling; I am sure that many would argue that it should have been written MDCVI.
However, if we believe the adage, "when in Rome do as the Romans do," and we see how the Romans write numerals, then it clearly gives us much more freedom than many would care to admit.
For example, the following represent all of the legitimate ways of writing the number sixteen:
IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI
The last example being considered the most efficient, as it uses the least number of numerals.VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI
The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; that is, they are arranged in descending units and obey the subtractive pair rule (see About Roman Numerals... for the definitive rules for this problem).
Find the number of characters saved by writing each of these in their minimal form.
Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.
About Roman Numerals:-
Traditional Roman numerals are made up of the following denominations:
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000
You will read about many different rules concerning Roman numerals, but the truth is that the Romans only had one simple rule:V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000
Numerals must be arranged in descending order of size.
For example, three ways that sixteen could be written are XVI,
XIIIIII, VVVI; the first being the preferred form as it uses the least
number of numerals.The "descending size" rule was introduced to allow the use of subtractive combinations. For example, four can be written IV because it is one before five. As the rule requires that the numerals be arranged in order of size it should be clear to a reader that the presence of a smaller numeral out of place, so to speak, was unambiguously to be subtracted from the following numeral. For example, nineteen could be written XIX = X + IX (9). Note also how the rule requires X (ten) be placed before IX (nine), and IXX would not be an acceptable configuration.
Generally the Romans tried to use as few numerals as possible when displaying numbers. For this reason, XIX would be the preferred form of nineteen over other valid combinations, like XVIIII or XVIV. However, this was NOT a rule and there still remain in Rome many examples where economy of numerals has not been employed. For example, in the famous Colesseum the the numerals above the forty-ninth entrance is written XXXXVIIII and not IL nor XLIX (see rules below).
Despite this, over time we have continued to introduce new restrictive rules. By mediaeval times it had become standard practice to avoid more than three consecutive identical numerals. That is, IV would be written instead of IIII, IX would be used instead of VIIII, and so on. In addition, the subtractive combinations had the following rules superimposed:
- Only I, X, and C can be used as the leading numeral in part of a subtractive pair.
- I can only be placed before V and X.
- X can only be placed before L and C.
- C can only be placed before D and M.
It is also expected that higher denominations should be used whenever possible; for example, L should be used in place of XXXXX, or C should be used in place of LL. However, even this "rule" has been flaunted: in the church of Sant'Agnese fuori le Mura (St Agnes' outside the walls), found in Rome, the date, MCCCCCCVI (1606), is written on the gilded and coffered wooden ceiling; I am sure that many would argue that it should have been written MDCVI.
However, if we believe the adage, "when in Rome do as the Romans do," and we see how the Romans write numerals, then it clearly gives us much more freedom than many would care to admit.
Solution:-
/*************************************************************************/
/*
solution to project euler 89
*/
#include<string.h>
#include<stdio.h>
int findNumber(char*);
int findRoman(int);
int main()
{
FILE *fp;
char str[100];
int n,i,counter,sum;
if(fp=fopen("a.txt","r"))
{
while(!feof(fp))
{
//counter=0;
i=0;
fscanf(fp,"%s",str);
counter=strlen(str);
str[counter]='\0';
//printf("%s\n",str);
sum+=counter-findRoman(findNumber(str));
str[0]='\0';
}
printf("answer = %d\n",sum);
}
else
printf("there was an error in opening the file...aborting...");
return 0;
}
int findRoman(int n)
{
int counter=0;
//printf("%d => ",n);
while(n>=1000)
{
counter++;
//printf("M");
n-=1000;
}
if(n>=900)
{
counter+=2;
//printf("CM");
n-=900;
}
if(n>=500)
{
counter++;
//printf("D");
n-=500;
}
if(n>=400)
{
counter+=2;
//printf("CD");
n-=400;
}
if(n<400)
while(n>=100)
{
counter++;
//printf("C");
n-=100;
}
if(n>=90)
{
counter+=2;
//printf("XC");
n-=90;
}
if(n>=50)
{
counter++;
//printf("L");
n-=50;
}
if(n>=40)
{
counter+=2;
//printf("XL");
n-=40;
}
if(n<40)
while(n>=10)
{
counter++;
//printf("X");
n-=10;
}
if(n==9)
{
counter+=2;
//printf("IX");
n-=9;
}
if(n>=5)
{
counter++;
//printf("V");
n-=5;
//printf("%d",n);
}
if(n==4)
{
counter+=2;
//printf("IV");
n-=4;
}
while(n!=0)
{
counter++;
//printf("I");
n--;
//printf("%d\n",n);
}
//printf("\n");
return counter;
}
int findNumber(char *str)
{
int i=0,n=0,x;
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='C' && str[i+1]=='M')
{
i+=2;
n+=900;
}
while(str[i] && str[i]=='M')
{
n+=1000;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='C' && str[i+1]=='D')
{
i+=2;
n+=400;
}
while(str[i] && str[i]=='D')
{
n+=500;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='X' && str[i+1]=='C')
{
i+=2;
n+=90;
}
while(str[i] && str[i]=='C')
{
n+=100;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='X' && str[i+1]=='L')
{
i+=2;
n+=40;
}
while(str[i] && str[i]=='L')
{
n+=50;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='I' && str[i+1]=='X')
{
i+=2;
n+=9;
}
while(str[i] && str[i]=='X')
{
n+=10;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='I' && str[i+1]=='V')
{
i+=2;
n+=4;
}
while(str[i] && str[i]=='V')
{
n+=5;
i++;
}
}
while(str[i] && str[i]=='I')
{
n++;
i++;
}
return n;
}
solution to project euler 89
*/
#include<string.h>
#include<stdio.h>
int findNumber(char*);
int findRoman(int);
int main()
{
FILE *fp;
char str[100];
int n,i,counter,sum;
if(fp=fopen("a.txt","r"))
{
while(!feof(fp))
{
//counter=0;
i=0;
fscanf(fp,"%s",str);
counter=strlen(str);
str[counter]='\0';
//printf("%s\n",str);
sum+=counter-findRoman(findNumber(str));
str[0]='\0';
}
printf("answer = %d\n",sum);
}
else
printf("there was an error in opening the file...aborting...");
return 0;
}
int findRoman(int n)
{
int counter=0;
//printf("%d => ",n);
while(n>=1000)
{
counter++;
//printf("M");
n-=1000;
}
if(n>=900)
{
counter+=2;
//printf("CM");
n-=900;
}
if(n>=500)
{
counter++;
//printf("D");
n-=500;
}
if(n>=400)
{
counter+=2;
//printf("CD");
n-=400;
}
if(n<400)
while(n>=100)
{
counter++;
//printf("C");
n-=100;
}
if(n>=90)
{
counter+=2;
//printf("XC");
n-=90;
}
if(n>=50)
{
counter++;
//printf("L");
n-=50;
}
if(n>=40)
{
counter+=2;
//printf("XL");
n-=40;
}
if(n<40)
while(n>=10)
{
counter++;
//printf("X");
n-=10;
}
if(n==9)
{
counter+=2;
//printf("IX");
n-=9;
}
if(n>=5)
{
counter++;
//printf("V");
n-=5;
//printf("%d",n);
}
if(n==4)
{
counter+=2;
//printf("IV");
n-=4;
}
while(n!=0)
{
counter++;
//printf("I");
n--;
//printf("%d\n",n);
}
//printf("\n");
return counter;
}
int findNumber(char *str)
{
int i=0,n=0,x;
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='C' && str[i+1]=='M')
{
i+=2;
n+=900;
}
while(str[i] && str[i]=='M')
{
n+=1000;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='C' && str[i+1]=='D')
{
i+=2;
n+=400;
}
while(str[i] && str[i]=='D')
{
n+=500;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='X' && str[i+1]=='C')
{
i+=2;
n+=90;
}
while(str[i] && str[i]=='C')
{
n+=100;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='X' && str[i+1]=='L')
{
i+=2;
n+=40;
}
while(str[i] && str[i]=='L')
{
n+=50;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='I' && str[i+1]=='X')
{
i+=2;
n+=9;
}
while(str[i] && str[i]=='X')
{
n+=10;
i++;
}
}
for(x=0;x<2;x++)
{
if(str[i] && str[i+1] && str[i]=='I' && str[i+1]=='V')
{
i+=2;
n+=4;
}
while(str[i] && str[i]=='V')
{
n+=5;
i++;
}
}
while(str[i] && str[i]=='I')
{
n++;
i++;
}
return n;
}
/*************************************************************************/
2 = 1 +
a