1. ## 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  Reply With Quote

2. ## 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.   Reply With Quote

3. ## 151 without strings in Common LISP:
Code:
`(do*((a'(1)(nconc a`(,c,v)))(c 0 0)(v 1(car a)))(())(format t"~{~A~}~&#37;"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.  Reply With Quote

4. ## I wish I remembered APL. I would probably take less than ten symbols in that.  Reply With Quote

5. ## 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.  Reply With Quote

6. ## I can't even understand the question!! =O
Wow I need to seriously sit down and learn code more than I have  Reply With Quote

7. ## 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.  Reply With Quote

8. ## 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  Reply With Quote

9. ## Python (95 characters)

Extra credit (138 characters)

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.  Reply With Quote

10. ## Inspiration shortened it.
Code:
```morris = function(b=1) {
b = as.integer(strsplit(as.character(b),NULL)[])
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.  Reply With Quote

11. ## 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.   Reply With Quote

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

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

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

Should shorten up some code significantly.  Reply With Quote

15. ## brb, making my own programming language where a blank source code file means "Morris Sequence program".  Reply With Quote

16. ## don't forget the extra credit  Reply With Quote

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

Python: 94

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  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•