Results 1 to 17 of 17
  1. Default 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

  2. Default


    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.

  3. DUCKS
    IGN: Mondays
    Server: Bellocan
    Level: 170
    Job: White Knight
    Guild: Affinity
    Alliance: Honour
    norway

    Default


    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.

  4. Orbital Bee Cannon
    IGN: SaptaZapta
    Server: Kradia
    Level: 275
    Job: Hero
    Guild: Matriarchy
    Alliance: Peaceful

    Default


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

  5. DUCKS
    IGN: Mondays
    Server: Bellocan
    Level: 170
    Job: White Knight
    Guild: Affinity
    Alliance: Honour
    norway

    Default


    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.

  6. Default


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

  7. Default


    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.

  8. Default


    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

  9. Default


    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.

  10. Default


    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.
    Last edited by Stereo; 2010-11-12 at 02:18 PM.

  11. Default


    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.

  12. Orbital Bee Cannon
    IGN: SaptaZapta
    Server: Kradia
    Level: 275
    Job: Hero
    Guild: Matriarchy
    Alliance: Peaceful

    Default


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

  13. Default


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

  14. Default


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

    Should shorten up some code significantly.

  15. Default


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

  16. Default


    don't forget the extra credit

  17. Default


    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

  18.  

Bookmarks

Posting Permissions

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