Fun programming puzzler

Problem:
Code a Morris Sequence.

Requirements:
- Use as few characters as possible. A character is defined by anything that is not a newline, tab, or space.
- Any programming language, esoteric or traditional, may be used.
- The program should be free of buffer overflows and an exception may never be thrown.
- Your program must be able to print out an infinite number of iterations.
- Each iteration must be printed and be on its own line.
- Any and all compilation arguments may be used.
- If the Extra Credit below is not used, the sequence must begin with "1" as the starting number.
- Assume the input is always valid.

Extra Credit:
Allow the user to input his own number to start the sequence.

Examples:

Input:

Code:

>>> morris

Output:

Code:

1
11
21
1211
111221
{And so on}

Input:

Code:

>>> morris 3

Output:

Code:

3
13
1113
3113
132113
{And so on}

Input:

Code:

>>> morris 131313

Output:

Code:

131313
111311131113
311331133113
13212321232113
{And so on}

Reference:
Stack Overflow

inb4Russtwins
I'd actually try this, but my programming knowledge extends only as far as Visual BASIC, which sucks balls. And with that I definitely won't win.

151 without strings in Common LISP:

Code:

(do*((a'(1)(nconc a`(,c,v)))(c 0 0)(v 1(car a)))(())(format t"~{~A~}~%"a)(setf b a a())(dolist(d b)(if(= d v)(incf c)(setq a(nconc a`(,c,v))c 1 v d))))

Could shave off more in Arc, but meh.

Issue is probably that I don't have regex easily available or any string functions at all.

I wish I remembered APL. I would probably take less than ten symbols in that.

Oh, realized spaces, tabs and newlines doesn't count. Then we have

Normal - 125:

Code:

(do*((a'(1)(nconc a`(,c,v)))(c 0 0)(v 1(car a)))(())(format t"~{~A~}
"a)(setf b a a())(dolist(d b)(if(= d v)(incf c)(setq a(nconc a`(,c,v))c 1 v d))))

Extra - 165:

Code:

(do*((a(mapcar #'char-digit(coerce(read-line)'list))(nconc a`(,c,v)))(c 0 0)(v 1(car a)))(())(format t"~{~A~}
"a)(setf b a a())(dolist(d b)(if(= d v)(incf c)(setq a(nconc a`(,c,v))c 1 v d))))

Again, without string-functions.

I can't even understand the question!! =O
Wow I need to seriously sit down and learn code more than I have

In this thread: Fiel says longer variable names make you lose.

You should have made the first criteria "minimum number of operations" instead of "minimum number of characters", otherwise h4x0rz language users (Devil's Sunrise) win.

In R.

Code:

morris <- function(b=1) {
c = b
repeat {
  cat(b,"\n",sep="")
  n = -1
  x = n
  for (i in 1:length(b)) {
    if (b[i]==x) c[n]=c[n]+1
    else {
      n=n+2
      x=b[i]
      c[n+1]=x
      c[n]=1
    }
  }
  b = c
}
}

This solves the more complicated version because the shorter one is the same number of characters, just change the first line into 2 lines:

Code:

morris <- function() {
b=1

135 characters either way, if I counted right.

I'm slightly cheating because to put in more than 1 digit, you use morris(c(1,3,1,3,1,3)), not morris(131313).


Also, technically speaking, it'll overflow when R runs out of memory (in 32-bit R, after 3 gigs, in 64-bit, after it uses all your RAM). But not much I can do about that.

 Version that will take integer input as specified: 183 chars

Code:

morris <- function(b=1) {
b = as.integer(strsplit(as.character(b),NULL)[[1]])
c = b
repeat {
  cat(b,"\n",sep="")
  n = -1
  x = n
  for (i in 1:length(b)) {
    if (b[i]==x) c[n]=c[n]+1
    else {
      n=n+2
      x=b[i]
      c[n+1]=x
      c[n]=1
    }
  }
  b = c
}
}

 Python (95 characters)

Code:

def f(s):
    n = ''
    while s:
        a = s[0]
        r = s.lstrip(a)
        n += str(len(s)-len(r)) + a
        s = r
    return n

s = '1'
while 1:
    print s
    s = f(s)

 Extra credit (138 characters)

Code:

def f(s):
    n = ''
    while s:
        a = s[0]
        r = s.lstrip(a)
        n += str(len(s)-len(r)) + a
        s = r
    return n

import sys
try:
    s = sys.argv[1]
except IndexError:
    s = '1'
    
while 1:
    print s
    s = f(s)

Not the cleanest or most time-efficient method, but character-efficient, which is what Fiel asked for.

Edit: Didn't realize "input is always valid", so you can get rid of the try/except block in the extra credit, which drops it down to 116 characters.

Edit: Comparing s to the empty string wasted 4 characters. Whoops.

Inspiration shortened it.

Code:

morris = function(b=1) {
b = as.integer(strsplit(as.character(b),NULL)[[1]])
c = b
repeat {
   cat(b,"\n",sep="")
   n = x = -1
   for (i in b) {
     if (i==x) c[n]=c[n]+1
     else {
       n=n+2
       c[n+1]=x=i
       c[n]=1
     }
   }
   b = c
}
}

165 with normal input. 117 if I don't coerce b into the right format.

In this thread: Fiel says longer variable names make you lose.

You should have made the first criteria "minimum number of operations" instead of "minimum number of characters", otherwise h4x0rz language users (Devil's Sunrise) win.

Pretty hard to quantify what an operation is.

a += b could be considered one operation
a += b could be considered two operations (add A to B, store in A)
a += b could be considered four operations (fetch A, fetch B, add A to B, store in A)

One regex call could be considered one operation or thousands of operations.

Soooo yeah, I'd like to see you try to define what an operation is exactly.

It should simply be "minimum number of tokens".
(and then we could even use meaningful variable names without penalty...)

If you did it that way I could write my entire program with a single multidimensional variable. But that's not easier to read.

Only got as far as coming up with an appropriate regex: ((\d)(?:\1)*)

Should shorten up some code significantly.

- Any programming language, esoteric or traditional, may be used.

brb, making my own programming language where a blank source code file means "Morris Sequence program".

don't forget the extra credit

So I just realized that I could unwrap my function to save a few chars.

 Python: 94

Code:

import sys
s = sys.argv[1]
    
while 1:
    print s
    n = ''
    while s:
        a = s[0]
        r = s.lstrip(a)
        n += str(len(s)-len(r)) + a
        s = r
    s = n

Without extra credit, 77.

Edit: Based on my own benchmarking, this algorithm appears to run in quadratic time with respect to len(s), which is definitely sub-optimal.

Here's a linear-time version that does not use str.lstrip() and is probably not as short as it could be:

 Python: 112

Code:

import sys
s = sys.argv[1]

while 1:
    print s
    n = ''
    i = 0
    while i < len(s):
        a = s[i]
        j = i
        while j < len(s) and s[j] == a:
            j += 1
        n += str(j-i) + a
        i = j
    s = n