language agnostic - Código de golf: secuencia de Morris

language-agnostic code-golf (30)

C con crédito adicional, 242 (o 184)

#include <stdlib.h> #include <stdio.h> #include <string.h> #define s malloc(1<<20) main(int z,char**v){char*j=s,*k=s;strcpy(k,*++v);for(;;){strcpy(j,k);z=1;*k=0;while(*j){if(*j-*++j)sprintf(k+strlen(k),"%d%c",z,*(j-1)),z=1;else++z;}puts(k);}}

Puede guardar otros ~ 60 caracteres si omite los archivos incluidos, gcc seguirá compilando con advertencias.

$ ./a.out 11111111 | head 81 1811 111821 31181211 132118111221 1113122118312211 31131122211813112221 132113213221181113213211 111312211312111322211831131211131221 3113112221131112311332211813211311123113112211

El reto

El código más corto por número de caracteres que generará la secuencia de números de Morris . La secuencia de números de Morris , también conocida como secuencia de mirar y decir, es una secuencia de números que comienza de la siguiente manera:

1, 11, 21, 1211, 111221, 312211, ...

Puede generar la secuencia infinitamente (es decir, no tiene que generar un número específico).

Expectativas de E / S

El programa no necesita tomar ninguna entrada (sino puntos de bonificación por aceptarla y, por lo tanto, proporcionar la opción de comenzar desde cualquier punto de inicio o número arbitrario). Por lo menos su programa debe comenzar desde 1 .

Por lo menos se espera que la salida sea la secuencia:

1 11 21 1211 111221 312211 ...

Crédito adicional

Si vas a obtener crédito adicional, deberías hacer algo como esto:

$ morris 1 1 11 21 1211 111221 312211 ... $ morris 3 3 13 1113 3113 132113 ...

C, 128 caracteres

usa un buffer estático, garantizado para causar falla de segmentación

main(){char*c,v[4096],*o,*b,d[4096]="1";for(;o=v,puts(d);strcpy(d,v))for(c=d;*c;o+=sprintf(o,"%d%c",c-b,*b))for(b=c;*++c==*b;);}

Delphi

Delphi es un lenguaje terrible para el golf, pero aún así:

var i,n:Int32;s,t,k:string;u:char;label l;begin s:=''1'';l:writeln(s);t:='''';u:=s[1 ];n:=1;for i:=2to length(s)do if s[i]=u then inc(n)else begin str(n,k);t:=t+k+u; u:=s[i];n:=1;end;str(n,k);t:=t+k+u;s:=t;goto l;end.

Esto es 211 bytes (y se compila como está).

Haskell: 115 88 85

import List m x=do a:b<-group x;show(length b+1)++[a] main=mapM putStrLn$iterate m"1"

Esta es la secuencia infinita. Sé que se puede mejorar mucho, soy bastante nuevo en Haskell.

Un poco más corto, alineando mapM y iterar:

import List m(a:b)=show(length b+1)++[a] f x=putStrLn x>>f(group x>>=m) main=f"1"

Java - 167 caracteres (con crédito)

_{(122 sin clase / repetitivo principal)}

class M{public static void main(String[]a){for(String i=a[0],o="";;System.out.println(i=o),o="")for(String p:i.split("(?<=(.)(?!//1))"))o+=p.length()+""+p.charAt(0);}}

Con nuevas líneas:

class M{ public static void main(String[]a){ for(String i=a[0],o="";;System.out.println(i=o),o="") for(String p:i.split("(?<=(.)(?!//1))")) o+=p.length()+""+p.charAt(0); } }

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--)}

Permite interrumpir la secuencia (haciendo clic en "Cancelar"), por lo que no bloqueamos el agente de usuario y fijamos la CPU. También permite comenzar desde cualquier entero positivo (crédito adicional).

Ejemplo en vivo: http://jsbin.com/izeqo/2

Mathematica - 62 53 50 caracteres - Crédito adicional incluido

Edición: 40 caracteres ... pero de derecha a izquierda :(

Curiosamente si leemos la secuencia de derecha a izquierda (es decir, 1,11,12,1121, ..), 40 caracteres es suficiente

NestList[Flatten[Tally /@ Split@#] &, #2, #] &

Eso es porque Tally genera una lista {elem, contador}!

Edición: 50 caracteres

NestList[Flatten@Reverse[Tally /@ Split@#, 3] &, #2, #] &

Disección: (leer comentarios hacia arriba)

NestList[ // 5-Recursively get the first N iterations Flatten@ // 4-Convert to one big list Reverse // 3-Reverse to get {counter,element} [Tally /@ // 2-Count each run (generates {element,counter}) Split@#, // 1-Split list in runs of equal elements 3] &, #2,// Input param: Starting Number #] // Input param: Number of iterations

Edición: refactorizado

NestList[Flatten[{Length@#, #[[1]]} & /@ Split@#, 1] &, #2, #1] &

Fin de edición ///

NestList[Flatten@Riffle[Length /@ (c = Split@#), First /@ c] &, #2, #1] &

Espacios no necesarios / añadidos para mayor claridad.

Invocar con

%[NumberOfRuns,{Seed}]

Mi primera vez usando "Riffle", para combinar {1,2,3} y {a, b, c} en {1, a, 2, b, 3, c} :)

PHP: 111

Mi primer intento en un código de golf, muy contento con el resultado.

for($x=1;;){echo$y=$x,"/n";for($x="";$y;){for($c=0;$y[$c++]&&$y[$c]==$y[0];);$x.=$c.$y[0];$y=substr($y,$c--);}}

Da:

> php htdocs/golf.php 1 11 21 ... (endless loop)

PHP con crédito extra: 118

for($x=$argv[1];;){echo$y=$x,"/n";for($x="";$y;){for($c=0;$y[$c++]&&$y[$c]==$y[0];);$x.=$c.$y[0];$y=substr($y,$c--);}}

Da:

> php htdocs/golf.php 4 4 14 1114 3114 ... (to infinity and beyond)

Perl, 46 caracteres

$_=1;s/(.)/1*/$&=~y!!!c.$1/ge while print$_,$/

Crédito extra, 51 caracteres:

$_=pop||1;s/(.)/1*/$&=~y!!!c.$1/ge while print$_,$/

Perl, 67 caracteres

incluida la bandera -l .

sub f{$_=pop;print;my$n;$n.=$+[0].$1while(s/(.)/1*//);f($n)}f(1)

Perl, 72 caracteres con crédito extra

sub f{$_=pop;print;my$n;$n.=$+[0].$1while(s/(.)/1*//);f($n)}f(pop||1)

Python - 117

Mi python-fu no es fuerte, así que hice muchas búsquedas en Google para esto. :)

a=''1'' while 1: print a a=''''.join([`len(s)`+s[0]for s in''''.join([x+'' ''*(x!=y)for x,y in zip(a,(2*a)[1:])]).split()])

La idea es usar zip para generar una lista de (a [i], a [i + 1]) pares, use la comprensión interna para insertar un espacio cuando a [i]! = A [i + 1], únase a la lista resultante en una cadena, y dividida en espacios, usa otra comprensión en esta lista dividida para reemplazar cada elemento con la longitud de ejecución del elemento, y el primer carácter, y finalmente unirse para obtener el siguiente valor en secuencia.

Python, 97 102 115

Se supone que los espacios en blanco son pestañas:

x=''1'' while 1: print x;y=d='''' for c in x+''_'': if c!=d: if d:y+=`n`+d n,d=0,c n+=1 x=y

P.ej:

$ python morris.py | head 1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211

Ruby - 52

s=?1;loop{puts s;s.gsub!(/(.)/1*/){"#{$&.size}"+$1}}

La tarea es demasiado simple, y demasiado perlish ...

C - 120 caracteres

^{129 con crédito extra}

main(){char*p,*s,*r,x[99]="1",t[99];for(;r=t,puts(p=x);strcpy(x,t)) for(;*p;*r++=p-s+48,*r++=*s,*r=0)for(s=p;*++p==*s;);}

^{La nueva línea está ahí solo por la legibilidad.}

Esto se detiene cuando se produce un error (después de al menos 15 iteraciones). Si las bibliotecas de C utilizan E / S en búfer, es posible que no vea ninguna salida antes del fallo de seguridad. Si es así, prueba con este código:

#include<stdio.h> main(){char*p,*s,*r,x[99]="1",t[99];for(;r=t,puts(p=x),fflush(stdout),1; strcpy(x,t))for(;*p;*r++=p-s+48,*r++=*s,*r=0)for(s=p;*++p==*s;);}

Esto agrega un fflush después de cada salida.

Ungolfed, se vería algo como esto:

int main(){ char *p, *start, *result, number[99] = "1", temp[99]; while(1){ /* loop forever */ puts(number); result = temp; /* we''ll be incrementing this pointer as we write */ p = number; /* we''ll be incrementing this pointer as we read */ while(*p){ /* loop till end of string */ start = p; /* keep track of where we started */ while(*p == *start) /* find all occurrences of this character */ p++; *result++ = ''0'' + p - start; /* write the count of characters, */ *result++ = *start; /* the character just counted, */ *result = 0; /* and a terminating null */ } strcpy(number, temp); /* copy the result back to our working buffer */ } }

Puedes verlo en acción en ideone .

Con el crédito extra, el código se ve así:

main(){char*p,*s,*r,x[99],t[99];for(scanf("%s",x);r=t,puts(p=x);strcpy(x,t)) for(;*p;*r++=p-s+48,*r++=*s,*r=0)for(s=p;*++p==*s;);}

Common Lisp - 124 122 115 caracteres

(do((l''(1)(do(a r)((not l)r)(setf a(1+(mismatch(cdr l)l))r(,@r,a,(car l))l(nthcdr a l)))))((format t"~{~s~}~%"l)))

Con el formateo:

(do ((l ''(1) (do (a r) ((not l) r) (setf a (1+ (mismatch (cdr l) l)) r `(,@r ,a ,(car l)) l (nthcdr a l))))) ((format t "~{~s~}~%" l)))

F # - 135

let rec m l=Seq.iter(printf "%i")l;printfn"";m(List.foldBack(fun x s->match s with|c::v::t when x=v->(c+1)::v::t|_->1::x::s)l []) m[1]

Código formateado

let rec m l= Seq.iter(printf "%i")l;printfn""; m (List.foldBack(fun x s-> match s with |c::v::t when x=v->(c+1)::v::t |_->1::x::s) l []) m[1]

Aún con la esperanza de que pueda encontrar una mejor manera de imprimir la lista o usar string / bigint en su lugar.

GolfScript - 41 (crédito extra: 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

¿Qué?
El procedimiento para obtener el siguiente número en la secuencia: convierta el número actual en una cadena, agregue una nueva línea y pase un bucle sobre los caracteres. Para cada dígito, si el dígito P anterior es el mismo, incremente el contador c . De lo contrario, agregue c y P a lo que será el próximo número, luego actualice estas variables. La nueva línea que agregamos permite que el último grupo de dígitos se agregue al siguiente número.

Los detalles exactos se pueden obtener examinando la documentación de GolfScript. (Tenga en cuenta que | se utiliza como una variable.)

J, 44 caracteres con crédito extra

(([:,#;.1@{:,.{:#{.)@(,:0<1,[:|2-//]))^:(<9)

Desafortunadamente, esto solo genera 9 iteraciones, pero el número de iteraciones <9 se puede ajustar para que sea cualquier cosa. Establecerlo en a a: genera una secuencia infinita pero, obviamente, esto no se puede imprimir.

Uso:

(([:,#;.1@{:,.{:#{.)@(,:0<1,[:|2-//]))^:(<9) 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 2 2 1 0 0 0 0 0 0 0 0 3 1 2 2 1 1 0 0 0 0 0 0 0 0 1 3 1 1 2 2 2 1 0 0 0 0 0 0 1 1 1 3 2 1 3 2 1 1 0 0 0 0 3 1 1 3 1 2 1 1 1 3 1 2 2 1 (([:,#;.1@{:,.{:#{.)@(,:0<1,[:|2-//]))^:(<11) 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 3 1 2 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 3 1 1 2 2 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 2 1 1 3 2 1 3 2 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 3 1 2 2 1 1 3 1 2 1 1 1 3 2 2 2 1 1 4 0 0 0 0 0 0 0 0 3 1 1 3 1 1 2 2 2 1 1 3 1 1 1 2 3 1 1 3 3 2 2 1 1 4 0 0 0 0 1 3 2 1 1 3 2 1 3 2 2 1 1 3 3 1 1 2 1 3 2 1 2 3 2 2 2 1 1 4

Perl (46 caracteres)

$_="1$/";s/(.)/1*/length($&).$1/eg while print

Crédito extra (52 caracteres)

$_=(pop||1).$/;s/(.)/1*/length($&).$1/eg while print

Perl (crédito extra), 47 caracteres

$_=pop.$/;{print;s/(.)/1*/$&=~y|||c.$1/ge;redo}

Python - 92 caracteres

^{98 con credito extra}

Salidas infinitas. Recomiendo redirigir la salida a un archivo, y presionar rápidamente Ctrl + C.

x=`1`;t='''' while 1: print x while x:c=x[0];n=len(x);x=x.lstrip(c);t+=`n-len(x)`+c x,t=t,x

Para la versión de crédito extra, reemplazar

x=`1`

con

x=`input()`

Python - 98 caracteres

from itertools import * L=''1'' while 1:print L;L=''''.join(''%s''%len(list(y))+x for x,y in groupby(L))

106 caracteres para el bono

from itertools import * L=raw_input() while 1:print L;L=''''.join(''%s''%len(list(y))+x for x,y in groupby(L))

Aquí está mi intento de C # usando LINQ y el primer intento en Code Golf:

C # - 205 194 211 198 bytes con crédito adicional (incluyendo repetitivo C #)

using System.Linq;class C{static void Main(string[]a){var v=a[0];for(;;){var r="";while(v!=""){int i=v.TakeWhile(d=>d==v[0]).Count();r+=i;r+=v[0];v=v.Remove(0,i);}System.Console.WriteLine(r);v=r;}}}

Versión legible:

static void Main(string[] args) { string value = args[0]; for (;;) { string result = ""; while (value != "") { int i = value.TakeWhile(d => d == value[0]).Count(); result += i; result += value[0]; value = value.Remove(0, i); } Console.WriteLine(result); value = result; } }

Salida de muestra:

11 21 1211 111221 312211 13112221 1113213211 ...

Aquí va mi implementación (en Prolog):

Prólogo con DCGs (174 caracteres):

m(D):-write(D),nl,m(1,write(D),T,[nl|T],_). m(C,D,T)-->[D],{succ(C,N)},!,m(N,D,T). m(C,D,[G,D|T])-->[N],{G=write(C),G,D,(N=nl->(M-T-O=0-[N|R]-_,N);M-T-O=1-R-N)},!,m(M,O,R).

Prólogo de vainilla simple, código mucho más legible (225 caracteres):

m(D):- ((D=1->write(D),nl);true), m([], [1,D]). m([], [C,D|M]):- write(C), write(D),nl, reverse([D,C|M],[N|X]), !, m([N|X],[0,N]). m([D|T], [C,D|M]):- succ(C,N), !, m(T,[N,D|M]). m([Y|T],[C,D|M]):- write(C), write(D), !, m(T,[1,Y,D,C|M]).

Para dar salida a la secuencia de Morris: m (D). donde D es el dígito de ''inicio''.

Este es mi primer intento de código de golf, ¡así que no seas demasiado duro conmigo!

PHP 128 122 112 bytes con etiqueta de apertura

~~122~~ ~~116~~ 106 bytes sin etiqueta de apertura y espacios en blanco iniciales.

<?php for($a="1";!$c="";print"$a/n",$a=$c)for($j=0,$x=1;$a[$j];++$j)$a[$j]==$a[$j+1]?$x++:($c.=$x.$a[$j])&&$x=1;

(Aunque es una pena que tenga que inicializar $a como una cadena, me cuesta 2 bytes adicionales, de lo contrario no puedo usar la notación de índice en ella).

Salida

$ php morris.php 1 11 21 1211 111221 312211 ...

PHP (crédito extra), 133 127 117 bytes con etiqueta de apertura

~~127~~ ~~121~~ 111 bytes sin abrir la etiqueta <?php y los espacios en blanco iniciales.

<?php for($a=$argv[1];!$c="";print"$a/n",$a=$c)for($j=0,$x=1;$a[$j];++$j)$a[$j]==$a[$j+1]?$x++:($c.=$x.$a[$j])&&$x=1;

Salida

$ php morris.php 3 3 13 1113 3113 132113 1113122113 ... ^C $ php morris.php 614 614 161114 11163114 3116132114 1321161113122114 1113122116311311222114 ...

PHP (crédito adicional), sin etiquetas con etiquetas de apertura y cierre

<?php for ($a = $argv[1]; !$c = ""; print "$a/n", $a = $c) { for ($j = 0, $x = 1; $a[$j]; ++$j) { // NB: this was golfed using ternary and logical AND operators: // $a[$j] == $a[$j + 1] ? $x++ : ($c .= $x . $a[$j]) && $x = 1; if ($a[$j] == $a[$j + 1]) { $x++; } else { $c .= $x . $a[$j]; $x = 1; } } } ?>

Llame a una cadena "Morris-ish" si no contiene nada más que los dígitos 1-3, y no contiene ninguna ejecución de más de tres dígitos. Si la cadena inicial es Morris-ish, todas las cadenas generadas iterativamente a partir de ella también serán Morris-ish. Del mismo modo, si la cadena inicial no es Morris-ish, entonces ninguna cadena generada será Morris-ish a menos que los números superiores a diez se consideren combinaciones de dígitos (por ejemplo, si 11111111111 se considera colapsado en tres unidades, en lugar de un "once" y uno).

Dada la observación, cada iteración que comienza con una semilla de Morris-ish se puede realizar como la siguiente secuencia de operaciones de búsqueda / reemplazo:

111 -> CA 11 -> BA 1 -> AA 222 -> CB 22 -> BB 2 -> AB 333 -> CC 33 -> BC 3 -> AC A -> 1 B -> 2 C -> 3

Tenga en cuenta que una secuencia es Morris-ish antes de la sustitución anterior, el segundo carácter de cada par generado será diferente del segundo carácter de los pares anterior y siguiente; por lo tanto, no es posible tener más de tres caracteres idénticos en secuencia.

Me pregunto cuántas secuencias de Morris-ish disjoint hay?

C #, 204 bytes (256 con crédito extra)

Mi primer intento de código golf

static void Main(){var v="1";for(;;){Console.Write(v + "/n");var r=v.Aggregate("", (x, y) => x.LastOrDefault()==y?x.Remove(0, x.Length-2)+(int.Parse(x[x.Length-2].ToString())+1).ToString()+y:x+="1"+y);v=r;}}

Versión legible, la diferencia con los demás es que uso la función de agregado de Linq

static void Main(){ var value="1"; for(;;) { Console.Write(value + "/n"); var result = value.Aggregate("", (seed, character) => seed.LastOrDefault() == character ? seed.Remove(seed.Length-2) + (int.Parse(seed[seed.Length-2].ToString())+1).ToString() + character : seed += "1" + character ); value = result; } }

C ++, 310 caracteres.

#include <iostream> #include <list> using namespace std; int main(){list<int> l(1,1);cout<<1<<endl;while(1){list<int> t;for(list<int>::iterator i=l.begin();i!=l.end();){list<int>::iterator p=i;++i;while((i!=l.end())&&(*i==*p)){++i;}int c=distance(p,i);cout<<c<<*p;t.push_back(c);t.push_back(*p);}cout<<''/n'';l=t;}}

Correctamente sangrado:

#include <iostream> #include <list> using namespace std; int main() { list <int> l(1,1); cout << 1 << endl; while(1) { list <int> t; for (list <int>::iterator i = l.begin(); i != l.end();) { const list <int>::iterator p = i; ++i; while ((i != l.end()) && (*i == *p)) { ++i; } int c = distance(p, i); cout << c << *p; t.push_back(c); t.push_back(*p); } cout << ''/n''; l = t; } }

Java

Mi primer intento de un ''Código de golf'' Acabo de lanzar esto juntos durante parte de mi clase de IB CS:

238 condensado

Condensado:

String a="1",b="1",z;int i,c;while(true){System.out.println(b);for(c=0,i=0,b="",z=a.substring(0,1);i<a.length();i++){if(z.equals(a.substring(i,i+1)))c++;else{b+=Integer.toString(c)+z;z=a.substring(i,i+1);c=1;}}b+=Integer.toString(c)+z;a=b;}

Formato correcto:

String a = "1", b = "1", z; int i, c; while (true) { System.out.println(b); for (c = 0, i = 0, b = "", z = a.substring(0, 1); i < a.length(); i++) { if (z.equals(a.substring(i, i + 1))) c++; else { b += Integer.toString(c) + z; z = a.substring(i, i + 1); c = 1; } } b += Integer.toString(c) + z; a = b; }

PHP 72 bytes

<?for(;;)echo$a=preg_filter(''#(.)/1*#e'',''strlen("$0"). $1'',$a)?:5554,~õ;

Este script puede ser optimizado aún más. Pero ya que tenemos en PHPGolf ({http://www.phpgolf.org/?p=challenges&challenge_id=28}) exactamente la misma secuencia, lo guardo de esta manera.