Un pequeño juego
Publicado en Juegos el 27 de November, 2007 por Lek.Recientemente, ^Diamond^ me proponía que hiciéramos algo similar a lo que hace él en Gaussianos: Proponer juegos para su resolución (algo del estilo de Bits en el ring, pero más matemático quizá).
Esta mañana me ha llegado la inspiración para ver si el tema os motiva en forma de post gaussiano: Serie numérica que espera explicación. La serie está al alcance de cualquiera, además que en los comentarios ya se ha comentado cómo resolverla. Pero lo que nos interesa en 4bits es ver hasta que punto es programable y hasta dónde llega.
Entonces…
Necesitamos programas que realicen esta serie (y que lo hagan correctamente). No se requiere ningún lenguaje en concreto, pero se agradecería un ejecutable (para Linux, Windows o ambos) junto al código fuente. Si alguno se interesa ya os indicamos la forma de enviarlo. El premio está por ver, ahora mismo está entre un mondadientes y una palmada en la espalda ;)
En Python, que utiliza enteros largos de forma automática, es trivial. Espero que no se me fastidie la indentación al pegar:
—————-cortar—————
#!/usr/bin/python # -*- encoding: utf-8 -*- m=1 print "Condición inicial: "+str(m) # En cada iteración se saca por pantalla el valor actual. while 1: mn1=str(m)+chr(0) mn="" c0=0 for c in mn1: if c==c0: n+=1 else: if c0!=0: mn+=str(n)+c0 n=1 c0=c m=int(mn) print m—————-cortar—————
Evidentemente la serie es divergente, pero no es difícil ver, como Conway probó, que hay grupos de números que se van repitiendo. Es trivial también calcular con el programa las sucesivas aproximaciones a la constante de Conway.
Ya me doy yo mismo la palmadita en la espalda :-)
# Pasotaman 27 de November, 2007
Efectivamente, se me ha jorobado la indentación.
Vuelvo a pegar, cambiando los espacios al inicio de línea por ‘X’. Si alguien quiere probarlo, :%s/X/ /g en vim, p.ej.. Lo siento.# Pasotaman 27 de November, 2007
curioso, dejo aquí mi versión en ruby, que a diferencia de python, dan igual los tabulares así que ele, aquí va:
def serie_curiosa(max, serie) serie[0] = '1' anteriorValor='1' for i in (1..max-1) actualValor = '' anterior = anteriorValor[0,1].to_i; cuantos = 0 anteriorValor.each_byte do |n| actual = n.chr.to_i if actual == anterior cuantos += 1 else actualValor<<cuantos.to_s<<anterior.to_s cuantos = 1; anterior = actual end end actualValor<<cuantos.to_s< 0 serie[i] = actualValor; anteriorValor = actualValor end end serie_curiosa(ARGV[0].to_i, @serie = []); @serie.each_index {|i| puts "#{i} \t #{@serie[i]}"}# Blaxter 27 de November, 2007
Vaya, ha tenido más éxito del esperado… al menos más rápido :)
# Lek 27 de November, 2007
He retocado los comentarios de Blaxter y Pasotaman para que hagan uso de nuestro plugin para resaltar código, lo que no sé es porque salen un poco raros, pero bueno los pinta bastante bien.
# Fran 27 de November, 2007
No ha salido todo el código (falta un if por ahí) a ver si ahora… (editalo si eso, o borra el otro)
def serie_curiosa(max, serie) serie[0] = '1' anteriorValor='1' for i in (1..max-1) actualValor = '' anterior = anteriorValor[0,1].to_i; cuantos = 0 anteriorValor.each_byte do |n| actual = n.chr.to_i if actual == anterior cuantos += 1 else actualValor<<cuantos.to_s<<anterior.to_s cuantos = 1; anterior = actual end end actualValor<<cuantos.to_s< 0 serie[i] = actualValor; anteriorValor = actualValor end end serie_curiosa(ARGV[0].to_i, @serie = []); @serie.each_index {|i| puts "#{i} \t #{@serie[i]}"}Es para usar modo: ruby fichero.rb 40
Donde 40 es el número de elementos de la serie. Por cierto he comparado con la versión en python, y mientras que en ruby sacar 50 elementos le cuesta (en mi pc tostadora) 20seg o así, en python iba ya por más de dos minutos y lo he parado…
# Blaxter 27 de November, 2007
jaja, mecaguen wordpress xD. fichero ruby. Ahora me pillará el akismet como spam y me joderá vivo, ley de murphy.
# Blaxter 27 de November, 2007
En efecto, la versión en Python va más lenta que el caballo del malo. Aquí va la versión en C, que en mi portátil llega a la iteración 66 casi instantáneamente. Por defecto imprime la constante de Conway. Para ver los números hay que descomentar un printf hacia el final.
En todo caso, asintóticamente el tiempo de ejecución es exponencial (proporcional a 1.3^n). Para hacer un programa más rápido hay que cachear los resultados e implementar la detección de las “islas” que no interactúan entre sí.
#include #include #include int main(int argc,char **argv){ // Es de esperar que nunca se llegue a números tan grandes que produzcan // overflow de estos contadores. size_t i,j,l,lo,n,size; char c,co,*mo,*m; double conway; mo=strdup("1"); size=2; m=malloc(size*sizeof(char)); printf("Condición inicial: %s\n",m); // El programa no para hasta que se mate. for(i=0;;i++){ lo=strlen(mo); co=0; n=0; l=0; for(j=0;j=size-1){ size+=(l-size+2)*2; m=realloc(m,size*sizeof(char)); } m[l-2]=(char)(n+0x30); m[l-1]=co; } n=1; co=c; } } conway=((double)l)/lo; size=(int)(size*conway); printf("Iteración número %d\n",i+1); printf("Logitud de la cadena: %d\n",l); // Descomentar para ver el número en sí. //printf("Resultado: %s\n",m); printf("Aproximación a la constante de Conway: %lf\n",conway); free(mo); mo=m; // Para mejorar la velocidad no se hace ningún tipo de assert. // En consecuencia, el programa puede cascar inesperadamente. m=malloc(size*sizeof(char)); } return 0; }# Pasotaman 28 de November, 2007
Pasotaman, los include no aparecen porque usan los caracteres menor y mayor, y wordpress los pilla como HTML.
Para la próxima lo mejor, creo que será que dejéis un enlace al código, como ha hecho Blaxter.
# Fran 28 de November, 2007
Aggh, soy un cero a la izquierda en esto de escribir en blogs. ¿Se podría poner vista previa como en Gaussianos, p.ej.?
De todos modos, los include son de stdio.h, stdlib.h y string.h, como cualquiera puede suponer por las funciones que se usan. Lo peor son los signos que se pierden por el código.
Lo tenéis, espero que bien, en http://www.juststored.com/code/hP9ZC3
Al fondo de la página está el “download this code” para bajarlo sin números de línea y tal.
# Pasotaman 28 de November, 2007
Jo, pasotaman… con tu comentario me has dejado totalmente acojonado… calculando el tiempo de ejecución y todo……….
A ver si tengo un rato para currarme una cutreversión (cualquier cosa comparada con lo vuestro me temo que será cutre) en Java
# Lek 28 de November, 2007
A ver qué tal sale la cosa:
public class LekSeries { public static void main (String [] args) { int pasada = 1; char [] c = new char [] {'1'}; while (true) { //Comentar una u otra dependiendo qué quieras ver //System.out.println ((pasada++) + ": " + new String(c)); System.out.println ((pasada++) + " - Long: " + c.length); int lon = c.length; char [] temp = new char [lon*2]; //doblamos int count=0; char cha=c[0]; int i, j=0; for (i = 0 ; i < lon ; i++) { if (cha == c[i]) count ++; else { temp [j++] = String.valueOf (count).charAt (0); temp[j++] = cha; //reseteo valores count = 1; cha = c[i]; } } temp [j++] = String.valueOf (count).charAt (0); temp[j++] = cha; c = new char [j]; System.arraycopy (temp, 0, c, 0, j); } } }He visto que me muestra hasta el 37º número y luego empieza a hacer cosas raras (al mostrar, teóricamente sigue calculando)… habría que depurarlo :)
# Lek 29 de November, 2007
Un perlecillo, que nadíe había puesto todavía:
$ cat readit.pl #!/usr/local/bin/perl use strict; use warnings; my$t=($ARGV[0]or 10);my$i=1; for(1..$t){ print"$_: $i$/"; $i=r($i); } sub r{local$_=shift;my$o;while(/^(\d)/){my$c;my$a=$1;$c++while(s/^$a//g);$o.=$c.$a;}$o;}# deibyz 30 de November, 2007
Vaya, sale un poco mal =/, el codigo después de un tidy a ver si sale mejor:
$ cat readit.pl.tdy #!/usr/local/bin/perl use strict; use warnings; my $t = ( $ARGV[0] or 10 ); my $i = 1; for ( 1 .. $t ) { print "$_: $i$/"; $i = r($i); } sub r { local $_ = shift; my $o; while (/^(\d)/) { my $c; my $a = $1; $c++ while (s/^$a//g); $o .= $c . $a; } $o; }# deibyz 30 de November, 2007
Esto me tarda 1min, 43seg en determinar todas
las potencias de 5 sin ceros hasta la potencia
100000 y para las potencias de 2 (p=2) me tarda
42 segundos.
#include #include int main() { char *n,p=5,q,a; int maxsize=1024,size=1; int i,count=1,zeros; n=malloc(maxsize); n[0]=p; n[1]=0; while(count<100000) { if(n[size]) { size++; if(size==maxsize){maxsize*=2;n=realloc(n,maxsize);} n[size]=0; } a=0; zeros=0; for(i=0;i=0;i--)putchar(n[i]+'0'); putchar('\n'); } //sleep(1000); } }# Cristóbal Camarero 30 de November, 2007
Se me ha comido la mitad del código, así que lo pongo aquí:
cerospotencia.c
# Cristóbal Camarero 30 de November, 2007
Me he equivocado, creía que estabaias con lo de
http://gaussianos.com/mil-quintillones/
# Cristóbal Camarero 30 de November, 2007
Ahora un programa que sí genera esa serie:
serieexp.c
# Cristóbal Camarero 30 de November, 2007
Por dios, si vais a meter código aquí intentar encerrarlo entre etiquetas “pre”, sino intentad subirlo a algún sitio tipo Google Docs, Box, o algo así y listo.
# Fran 30 de November, 2007
Juas… al menos, por lo que se ve, la cosa ha gustado :)
Yo he estado probando el mío de Java, pero no he conseguido pasar más allá de las 63 iteraciones (sin mostrar el número, sólo la longitud del mismo)… me casca un OutOfMemory como un campano
# Lek 30 de November, 2007