Code Golf: Morris Sequence
Solution 1:
GolfScript - 41 (extra credit: 40)
1{.p`n+0:c:P;{:|P=c{c`P|:P!}if):c;}%~1}do
{~.p`n+0:c:P;{:|P=c{c`P|:P!}if):c;}%1}do
What?
The procedure for getting the next number in the sequence: Convert the current number to a string, append a newline and loop over the characters. For each digit, if the previous digit P
is the same, increment the counter c
. Otherwise, add c
and P
to what will be next number, then update these variables. The newline we append allows the last group of digits to be added to the next number.
The exact details can be obtained examining the GolfScript documentation. (Note that |
is used as a variable.)
Solution 2:
Haskell: 115 88 85
import List
m x=do a:b<-group x;show(length b+1)++[a]
main=mapM putStrLn$iterate m"1"
This is the infinite sequence. I know it can be improved a lot - I'm fairly new to Haskell.
Bit shorter, inlining mapM and iterate:
import List
m(a:b)=show(length b+1)++[a]
f x=putStrLn x>>f(group x>>=m)
main=f"1"
Solution 3:
Perl (46 characters)
$_="1$/";s/(.)\1*/length($&).$1/eg while print
Extra Credit (52 characters)
$_=(pop||1).$/;s/(.)\1*/length($&).$1/eg while print
Solution 4:
Javascript 100 97
for(x=prompt();confirm(y=x);)for(x="";y;){for(c=0;y[c++]&&y[c]==y[0];);x+=c+y[0];y=y.substr(c--)}
Allows interrupting the sequence (by clicking "Cancel") so we don't lock the user-agent and peg the CPU. It also allows starting from any positive integer (extra credit).
Live Example: http://jsbin.com/izeqo/2
Solution 5:
Perl, 46 characters
$_=1;s/(.)\1*/$&=~y!!!c.$1/ge while print$_,$/
Extra credit, 51 characters:
$_=pop||1;s/(.)\1*/$&=~y!!!c.$1/ge while print$_,$/