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.
relue
Posts: 10
Joined: Mon Feb 04, 2008 2:14 pm

Problem 089

Post by relue »

I need some clarification for this problem. Is 49 = IL or IM = 999 ok? The rule says such expression is not prefered, but didn't say if it is allowed or not. Whether to abide by this rule makes a big differece for the answer.

User avatar
hk
Administrator
Posts: 10706
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 89

Post by hk »

The problem description gives definitive rules :
http://projecteuler.net/index.php?secti ... n_numerals
Last edited by euler on Wed Oct 15, 2008 6:20 am, edited 2 times in total.
Reason: Edited broken link (hk) ... link only works if logged in (euler)
Image

Slin
Posts: 1
Joined: Sat May 26, 2007 9:15 am

Problem 89

Post by Slin »

As 3 people pointed out in the problem thread, and no one answered, there is nothing in the FAQ or problem description that disallows repeated subtractive pairs. E.g. IXIX as 18 instead of XVIII.

pavel
Posts: 2
Joined: Tue Oct 14, 2008 7:08 pm

Re: Problem 89

Post by pavel »

Need help.

I can't understand question. What does mean "characters saved by writing each in minimal form"?
May be I can't understand because my English is bad. May be someone can post example?
Last edited by pavel on Tue Oct 14, 2008 7:48 pm, edited 1 time in total.

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 89

Post by daniel.is.fischer »

In the problem statement, there are given several ways to write 16.
Suppose in the textfile there appears the line
IIIIIIIIIIIIIIII (hope I didn't miscount)
the minimal form is XVI, which uses three characters, while the original used sixteen, so for this item, you could save thirteen characters.
For each item in the textfile, determine how many characters are used and how many are needed for the minimal representation of that value. Sum the differences of the character counts.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

pavel
Posts: 2
Joined: Tue Oct 14, 2008 7:08 pm

Re: Problem 89

Post by pavel »

Thanks

User avatar
DNS
Posts: 30
Joined: Thu Oct 16, 2008 8:32 am
Location: Ukraine, Nikolaev

Re: Problem 89

Post by DNS »

Thank you, daniel.is.fischer!
With your tips I finished P89 (and P210, thanks one more time)!
First, I'd thought that symbols saved are symbols saved in file - length of the file saved.
My English is rather poor :(
2 x 2 = 4 = true

Phibonacci
Posts: 10
Joined: Fri Nov 28, 2008 4:04 am
Location: Des Moines, IA
Contact:

Re: Problem 089

Post by Phibonacci »

the rules are not clear enough
my answer is 8841-8031 = 810

Are any of these legit
IM = 999
IXIX = 18
IXL = 1 10 50 = 9 50 = 41
Phibonacci - A juxtaposition of Phi (The Golden Ratio) and Fibonacci (Leonardo of Pisa)

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

Re: Problem 089

Post by rayfil »

In the second post, hk provided a link to some definitive rules. That link may have answered most, if not all, of your questions. :shock:
When you assume something, you risk being wrong half the time.

Phibonacci
Posts: 10
Joined: Fri Nov 28, 2008 4:04 am
Location: Des Moines, IA
Contact:

Re: Problem 089

Post by Phibonacci »

I have read through the FAQ numerous times but it doesn't make things any clearer. it says the only rule for SURE is that they are arranged in descending order of size. The rest of the rules they give us have either been added on in medieval times or that one way is preferred over another way, but it does not give concrete rules. Can I please PM or email someone my roman numerals from 1-1000 or maybe 1-10000 and have them point out which numeral is wrong. I'm not asking for the solutions just some direction.

thanks,

Phibonacci
Phibonacci - A juxtaposition of Phi (The Golden Ratio) and Fibonacci (Leonardo of Pisa)

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

Re: Problem 089

Post by rayfil »

You can PM me your 1-1000 list.
When you assume something, you risk being wrong half the time.

jhgrc
Posts: 3
Joined: Thu May 28, 2009 12:31 pm

Re: Problem 089

Post by jhgrc »

I got the correct answer but I think it is not optimal.

I've got saving of [snip] chars by being more optimal and still by the rules (i.-iv.). You must consider shortening 8,80 and 800 to 'IIX', 'XXC' and 'CCM' which save 1 letter. Those are shorter by one but naturally you can complain about 3-practise in FAQ. With 3-practise I mean that shorten more than 3 consecutive letters (VIIII -> IX).

8: VIII -> IIX
80: LXXX -> XXC
800: DCCC -> CCM

For example from the provided file. [orig -> arabic -> optimized (saving)]
Read: MMMMDLXXXII -> 4582 -> MMMMDXXCII (1)
Read: MMCLXXXXVIII -> 2198 -> MMCXCIIX (4)
Read: MMMMDCVIII -> 4608 -> MMMMDCIIX (1)
Read: MMDCCCXLVIIII -> 2849 -> MMCCMXLIX (4)
Last edited by daniel.is.fischer on Thu May 28, 2009 1:30 pm, edited 1 time in total.
Reason: snip upper bound for solution

jhgrc
Posts: 3
Joined: Thu May 28, 2009 12:31 pm

Re: Problem 089

Post by jhgrc »

Phibonacci wrote: Are any of these legit
IXIX = 18
I'd say that this is not legit, but XIIX would be. Please see my post on this same problem.

XIIX=4 chars
XVIII=5 chars

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 089

Post by daniel.is.fischer »

But IIX violates rule ii: "I can only be placed before V and X."
If IIX is to be interpreted as 8, it would have to be a subtractive pair I(IX), which by rule ii isn't allowed.
The same applies to all other proposed transcriptions (with rules iii or iv if X or C are involved).
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

jhgrc
Posts: 3
Joined: Thu May 28, 2009 12:31 pm

Re: Problem 089

Post by jhgrc »

daniel.is.fischer wrote: But IIX violates rule ii: "I can only be placed before V and X."
If IIX is to be interpreted as 8, it would have to be a subtractive pair I(IX), which by rule ii isn't allowed.
I see, I did not think it that literal. That 'I' can be placed in before 'I' as well. But I can agree with you.

Just for curiosity it was interesting to see what would be most compressed format which can still be parsed by my program. Naturally for humans interpreting these even more optimized romans are a bit harder as bigger number subtraction etc. is needed.
Read: MMMMDCCLXXXVII -> 4787 -> MMMMCCXIIIM (4000 plus 213 below 1000)
Read: MMDXCVIIII -> 2599 -> MMDIC (1 below 2600)
Read: MCMLXXXXIII -> 1993 -> MVIIM (7 below 2000)
Read: CMLXIX -> 969 -> XXXIM (31 below 1000)
Read: MMMMDCCCCXXXXVI -> 4946 -> MMMMLXMVI (60 below 5000 plus 6)

These are similar to example of 49 (IL vs. XLIX).

Mr.Fister
Posts: 3
Joined: Tue Dec 01, 2009 9:23 am

Re: Problem 89

Post by Mr.Fister »

DNS wrote:Thank you, daniel.is.fischer!
With your tips I finished P89 (and P210, thanks one more time)!
First, I'd thought that symbols saved are symbols saved in file - length of the file saved.
My English is rather poor :(
I interpreted this the same way as you, and I would consider my English being quite above average for a non-native speaker. A better phrasing would have saved me almost 2 hours... and this was my #100 :(

babueter
Posts: 4
Joined: Tue Dec 08, 2009 9:00 pm

Re: Problem 089

Post by babueter »

I still don't have the answer, and this thread wasn't helpful so far.

I'm working on the assumption that IXIX is appropriate, since it conforms to the rules on the FAQ.

I don't want to give anything away, so if i could PM someone who has solved the problem some of my examples of reduction, it would be helpful to know if they could be reduced more, or if my reduction was not valid.

Thanks.

babueter
Posts: 4
Joined: Tue Dec 08, 2009 9:00 pm

Re: Problem 089

Post by babueter »

Never mind.... stpuid ^M skewed my data. The answer I had 10 minutes after I started the problem was the right one.

Thanks though.

vasilyev
Posts: 4
Joined: Fri Dec 11, 2009 5:54 pm

Re: Problem 089

Post by vasilyev »

Would you mind to put in the problem description, explicitly the following:

"Find the number of characters saved by writing each of these in their minimal form WHILE OBEYING ADDITIONAL RULES FROM FAQ",

or

"Find the number of characters saved by writing each of these in their minimal form DISREGARDING ADDITIONAL RULES".

The way it is phrased right now, it can be interpreted that (http://projecteuler.net/about=roman_numerals) is just for our information, and the answer should be just minimal, so IM is fine.

estanford
Posts: 10
Joined: Sun Sep 13, 2009 11:06 am

Re: Problem 089

Post by estanford »

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.)

Post Reply