Problem 089

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: Problem 089

Post by elendiastarman »

estanford wrote:So are we considering IIX to be a valid replacement for VIII? The rules page doesn't make it clear whether multiple numerals of the same kind can be placed before another in a subtractive pair. (I know it says I can only come before V and X, but I can't tell whether it applies in the VIII -> IIX case.)
That is not a valid replacement (same for similar constructions). That help?
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

cottonvibes
Posts: 1
Joined: Thu Aug 05, 2010 2:53 am

Re: Problem 089

Post by cottonvibes »

Guys I want to report what some other people were saying, which makes the answer to problem 89 on the site wrong.

By following the rules euler wrote in the FAQ: http://projecteuler.net/about=roman_numerals
Numerals must be arranged in descending order of size.
1. Only I, X, and C can be used as the leading numeral in part of a subtractive pair.
2. I can only be placed before V and X.
3. X can only be placed before L and C.
4. C can only be placed before D and M.
The following numbers should be valid:
IXIX = 9 + 9 = 18
XCXC = 90 + 90 = 180
CMCM = 900 + 900 = 1800

There is no rule these numbers break from above.
Therefore, either the rules on the FAQ need to be changed to explicitly say "no repeats of same subtractive-pair numbers", or the answer needs to be changed on the site.

For anyone wondering, the answer to the question currently does not allow repeats.
Therefor, for the above numbers it wants:
XVIII = 10 + 5 + 1 + 1 + 1 = 18
CLXXX = 100 + 50 + 10 + 10 + 10 = 180
MDCCC = 1000 + 500 + 100 + 100 + 100 = 1800

kcm1700
Posts: 1
Joined: Mon Aug 30, 2010 12:48 am

Re: Problem 089

Post by kcm1700 »

I also had the same problem... :(

I'm not familiar with roman numerals, since i'm from East Asia.

strictly following FAQ in projecteuler,
I tried to minimize the numeral, so I used some DP approach instead of greedy solution.
the output of my program for 18, 180, 1800 was IXIX, XCXC, CMCM, respecitively.
these consecutive same subtractive pairs were necessary for 18, 180~189, 1800~1899.
I googled for the roman numerals. I finally found the rule saying that consecutive same subtractive pairs are not allowed. til now, there's nothing saying about this rule in the FAQ. however, the problem statement says see FAQ for definitive rules for this problem...

cottonvibes wrote:Guys I want to report what some other people were saying, which makes the answer to problem 89 on the site wrong.

By following the rules euler wrote in the FAQ: http://projecteuler.net/about=roman_numerals
Numerals must be arranged in descending order of size.
1. Only I, X, and C can be used as the leading numeral in part of a subtractive pair.
2. I can only be placed before V and X.
3. X can only be placed before L and C.
4. C can only be placed before D and M.
The following numbers should be valid:
IXIX = 9 + 9 = 18
XCXC = 90 + 90 = 180
CMCM = 900 + 900 = 1800

There is no rule these numbers break from above.
Therefore, either the rules on the FAQ need to be changed to explicitly say "no repeats of same subtractive-pair numbers", or the answer needs to be changed on the site.

For anyone wondering, the answer to the question currently does not allow repeats.
Therefor, for the above numbers it wants:
XVIII = 10 + 5 + 1 + 1 + 1 = 18
CLXXX = 100 + 50 + 10 + 10 + 10 = 180
MDCCC = 1000 + 500 + 100 + 100 + 100 = 1800

kosiu_drumev
Posts: 6
Joined: Wed Jun 02, 2010 10:43 pm

Re: Problem 089

Post by kosiu_drumev »

The problem could be more intresting if there was examples with several "D" or "L" in a row. Best regards!
Image
Last edited by kosiu_drumev on Sat Jul 09, 2011 10:01 pm, edited 1 time in total.

beastmaster
Posts: 3
Joined: Thu Apr 21, 2011 4:29 pm

Re: Problem 089

Post by beastmaster »

Hi!
I've been working on this one for a while and still haven't solved it. I suspect there is a problem with my character counting, but i am not sure. Could someone check my code and give me some tips? It's written in python.

beastmaster

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: Problem 089

Post by elendiastarman »

I can look it over.
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

blamaeda
Posts: 2
Joined: Sat May 28, 2011 7:25 pm

Re: Problem 089

Post by blamaeda »

I'm stuck with this problem.

For clarification, can anyone tell me the minimal form of 18 and 49?

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 089

Post by TripleM »

XVIII and XLIX.

User avatar
rayfil
Administrator
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 089

Post by rayfil »

Roman numerals are essentially a variation of the decimal system in use today. Simply put brackets around each digit and then transcribe them into their Roman equivalent according to the posted rules.
Numerals must be arranged in descending order of size.
1. Only I, X, and C can be used as the leading numeral in part of a subtractive pair.
2. I can only be placed before V and X.
3. X can only be placed before L and C.
4. C can only be placed before D and M.
Ex.: 18 = (1)(8) = (X)(VIII) == XVIII
When you assume something, you risk being wrong half the time.

blamaeda
Posts: 2
Joined: Sat May 28, 2011 7:25 pm

Re: Problem 089

Post by blamaeda »

Then I really don't know what I'm doing wrong. Can anyone please take a look at my code? It's pretty straightforward (I think).

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 089

Post by TripleM »

Sure.

eppie
Posts: 14
Joined: Sat Jul 02, 2011 5:19 pm

Re: Problem 089

Post by eppie »

I can't see what I'm doing wrong.
Could someone give a intermediate result so I can check my code?
What is the savings in the first 30 numbers?
I don't think this gives away too much.

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 089

Post by thundre »

eppie wrote:I can't see what I'm doing wrong.
Could someone give a intermediate result so I can check my code?
What is the savings in the first 30 numbers?
I don't think this gives away too much.
For the first 30, I get a savings of 14 characters.
Image

eppie
Posts: 14
Joined: Sat Jul 02, 2011 5:19 pm

Re: Problem 089

Post by eppie »

thundre,

Thanks for the info. I solved the problem.

iordan_tanev
Posts: 6
Joined: Mon Jan 17, 2011 3:25 pm

Re: Problem 089

Post by iordan_tanev »

Hi,
reading the FAQ about this question i have some question. As far as i understood the rules which must be always true are

Numerals must be arranged in descending order of size.
Avoid more than three consecutive identical numerals

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.

Also i want to ask if combination such as IX can be used only at the end of the number or it can be used any where. Something like XIXV = 24. Also if there are some more rule which i didn't see in the FAQ please share.
Best Regards,
Iordan

User avatar
rayfil
Administrator
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 089

Post by rayfil »

Simply consider that a "subtractive pair" can only be used to replace its equivalent value when the number is written with "Arabic numerals".

For example, IV can only be used to replace a 4 as the unit digit. The IX in your XIXV could obviously not replace any 9 as a unit digit in your expected value of 25.
When you assume something, you risk being wrong half the time.

thelma
Posts: 10
Joined: Wed Dec 05, 2012 2:18 am

Re: Problem 089

Post by thelma »

I am stuck and hoping for help. Someone posted the correct solution for the first 30 entries in the file. My solution matches up to 30, but apparently it fails somewhere.

I've found a Roman/Arabic coverter online and I've been feeding it random minimalizations from my solution and they've all been ok. Of course that means 10 or 15 numbers; I have neither time nor patience for a serious session with that.

I've printed all 1000 results, and my code is completely unoptimized Python. Any suggestions on what to do next appreciated. --thelma

thelma
Posts: 10
Joined: Wed Dec 05, 2012 2:18 am

Re: Problem 089

Post by thelma »

OK, I sent it on to my son and he found it: I'm posting here because I can't believe that this was supposed to be part of the 'difficulty' of solving the problem. The file roman.txt did not end with a final crlf and my code therefore never added in the result of the final conversion

User avatar
RishadanPort
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

Re: Problem 089

Post by RishadanPort »

thelma wrote:OK, I sent it on to my son and he found it: I'm posting here because I can't believe that this was supposed to be part of the 'difficulty' of solving the problem. The file roman.txt did not end with a final crlf and my code therefore never added in the result of the final conversion
It is important to test in the beginning that all your input was properly received. It was given that 1000 roman numberals were given.
I did the problem in Windows using Java, -- and had no problem with the input whatsoever.

If you are reading the input from a different OS (and not java), you have to be a bit careful. File formats in for example Linux, are not the same as file formats in windows necessarily. For sure important to check that you can read the input properly...
Image

Rishada is the gateway to free trade—but the key will cost you.

thelma
Posts: 10
Joined: Wed Dec 05, 2012 2:18 am

Re: Problem 089

Post by thelma »

Thanks, RishadonPort. I hope I've learned to take more care from this!

Post Reply