20
Challenge description
We've had a few challenges involving the Look-and-say sequence. Quick reminder:
- The sequence starts with
1
, - Subsequent terms of this sequence are generated by enumerating each group of repeating digits in the previous term,
So the first few terms are:
1 "one"
11 "one one" (we look at the previous term)
21 "two ones"
1211 "one two, one one"
111221 "one one, one two, two ones"
312211 "three ones, two twos, one one"
Now let's do the same thing, but use Roman Numerals instead. We start with I
and follow the same rules (we apply the digit-counting rule to characters instead, so we read IVX
as one one, one five, one ten
instead of one four, one ten
or some other way):
I "one"
II "one one"
III "two ones" = "II" + "I"
IIII "three ones" = "III" + "I"
IVI "four ones" = "IV" + "I"
IIIVII "one one, one five, one one"
IIIIIVIII "three ones, one five, two ones" = ("III" + "I") + ("I" + "V") + ("II" + "I")
Given a positive integer N
, either:
- Output first
N
numerals of this sequence (any reasonable separator is fine, as well as["I", "II", "III", ...]
- Output
N
th term of this sequence (it may be 0-indexed).
Remember to make your code as short as possible, since this is a code-golf challenge!
EDIT: I believe that there is always one standard/preferred way of expressing integers as roman numerals, (like 95
-> XCV
instead of VC
). Couple of Roman numeral converters I found online corroborate my opinion. If in doubt, use an online converter, as listing all the possible edge-cases and specific rules of writing Roman numerals is not the point of this challenge.
EDIT2: @PeterTaylor and @GregMartin pointed out that only numbers less or equal to 5
appear in the sequence, so you don't have to worry about the ambiguity of Roman numerals (numbers 1
- 8
are I
, II
, III
, IV
, V
, VI
, VII
, and VIII
)
There isn't a unique Roman numeral expression for each integer. Which numbers might it be necessary to express, and which expressions of those numbers are valid? – Peter Taylor – 2016-08-30T15:13:47.410
What do you mean by "there isn't a unique Roman numeral expression for each integer"? Like
4
/IV
/IIII
? Or95
/XCV
/VC
? There might not always be a unique way to express an integer, but I'm pretty sure there's always a preferred (standard) one - correct me if I'm wrong. – shooqie – 2016-08-30T15:17:52.8131how far do we have to go with our roman numberals? – Maltysen – 2016-08-30T15:19:30.157
Yes, both of those cases. In the second case, I think it's very much a matter of opinion which is preferable. – Peter Taylor – 2016-08-30T15:21:59.777
@Maltysen I think the number of equal digits that can appear in succession is limited to 7. – Martin Ender – 2016-08-30T15:22:21.457
@shooqie I agree with you on this one, but you might just want to solidify the rules for roman numerals in OP. – Maltysen – 2016-08-30T15:26:17.573
@Maltysen: Like, this is something that bothers me the most about this site. Make a challenge a tiny bit more complicated and you get questions like
what counts as X?
orwhat about the edge-case #98752314?
– shooqie – 2016-08-30T15:35:35.4609@shooqie if these details weren't clarified, how would you compare answers? If there are certain edge cases left up to interpretation the actual scores become meaningless because they might make a bigger difference than any golfing tricks you could come up with. – Martin Ender – 2016-08-30T16:41:14.420
@MartinEnder: Well, I did my best at clearing up the confusion about the Roman numerals, but I feel like I shouldn't have to say how to write them - we've had challenges with Roman numerals before and there didn't seem to be any confusion whatsoever. – shooqie – 2016-08-30T17:00:28.490
I don't understand the output format - are we converting to roman numerals, grouping by character type, counting the length of each group and turning the whole thing into roman numerals again? – Blue – 2016-08-30T17:30:15.797
@muddyfish: Yeah, pretty much. – shooqie – 2016-08-30T17:32:30.953
I think one can mathematically prove that numbers greater than 8 never appear in the sequence starting at
I
. If so, then programs need only considerI
s andV
s. – Greg Martin – 2016-08-30T18:46:46.700@GregMartin, it's possible to prove the stronger statement that no run-length greater than 5 appears in the sequence whose first generation is
I
. – Peter Taylor – 2016-08-30T21:56:00.0331k rep! Congrats :) – ThreeFx – 2016-08-30T23:51:18.757
@GregMartin: Well, that certainly makes things easier. – shooqie – 2016-08-31T07:57:21.007
Surprisingly roman numerals are in fact a decimal notation where a number is split into powers of 10. So
999
=900+90+9
=CM + XC + IX
=CMXCIX
and notIM
(This is the modern standard form. The romans themselves were not completely consistent). But as noted this is not needed here. – Ton Hospel – 2016-09-01T06:02:06.530