Resolución de algoritmos [Reto semanal] #1

B

Hola buenas! A raíz del hilo de retos de programación web se me ha ocurrido hacer una versión para resolución de algoritmos que paso a explicaros:

Funcionamiento

Cada semana propondremos tres problemas de algoritmia de la página project euler (o de cualquier otro sitio), ordenados en diferentes niveles de dificultad: fácil, medio y difícil. Se pueden resolver en cualquier lenguaje de programación, menos en javascript (es broma :laughing:). Tendremos 7 días para hacerlos, cada uno el que quiera/pueda y según los vayamos teniendo los iremos subiendo a este post.

Algunas normas:

  • No se puede utilizar ni ver códigos de terceros para resolver el problema, la idea es que cada uno llegue a su propia solución y una vez que la haya subido vea las de los demás para comparar. Esto evidentemente no se puede controlar pero nadie va a ganar nada por resolverlo.

  • Las soluciones se pondrán dentro de spoilers para evitar accidentes.

  • Además del código, se deberá poner el resultado de ejecutarlo para comprobar que realmente funciona como debe y da el resultado esperado.

Retos semana #1

Al ser la primera semana voy a proponer yo directamente los tres algoritmos pero para el resto de semanas creo que lo suyo será abrir una encuesta.

Nivel fácil => 1000-digit Fibonacci number (número 25)

Nivel medio => Singular integer right triangles (número 75)

Nivel difícil => Palindromic sums (número 125)

El tema de la dificultad es muy relativo, la página los ordena según el número de personas que los han resuelto. Hay un total de 610 algoritmos, este último el más dificil, y el que yo he puesto como difícil está en el 125. Si vemos que se quedan cortos y los resuelve mucha gente ya los iremos calibrando para próximas ediciones.

SOLUCIONES

Nivel fácil => 4782

spoiler

Nivel medio => 161667

Nivel difícil => 2906969179

spoiler

Por mi parte me comprometo a mantener actualizado el post si veo que hay un mínimo interés. Iré enlazando las soluciones de cada uno en #1 para tenerlo todo organizado. Si la cosa se anima mucho también había pensado en que podríamos tener un repositorio dónde ir subiéndolas.

Cualquier sugerencia o consejo será más que bienvenido.

20
HeXaN

Mejor empezamos por un bubble sort no vaya a ser que pase como en el otro reto jajaja.

3 1 respuesta
B

#2 jajaja pues sí, es que lo de hacer un ogame era un poco locura. De los algoritmos que he puesto creo que el primero es asequible para todo el mundo pero se podría pasar a nivel medio y el que ahora está en nivel medio sustituirlo por algo más bajo. El que queda quiero dejarlo en difícil para el que tenga ganas de estrujarse el cerebro. A ver que opinan los demás y si hace falta vamos haciéndole ajustes.

1
eZpit

Me parece buena inciativa y está bien que tu mismo propon... elijas ejercicios razonables, ya que ha quedado claro que la democracia en este foro no es una opción.

1 respuesta
varuk

Fibonacci number en Scala con tail recursion (el compilador luego lo traduce a un FOR y no lo hace recursivo)

spoiler
1 respuesta
r2d2rigo

#5 pero acaso te has leido el enunciado, alma de cantaro?

1 respuesta
varuk

#6 Hostia fuí a lo loco ahí y ni leí lo último:

"What is the index of the first term in the Fibonacci sequence to contain 1000 digits?"

Gracias por el aviso. Intentaré adaptarlo luego para eso.

1 respuesta
GenBe

Yo me apunto. Me parece una muy buena iniciativa, sobre todo para los que estamos empezando es muy interesante.

Yo por lo pronto creo que saqué el primer problema con Java. Luego le echaré un ojo a los otros problemas, pero creo que ya se me escapan jajaj

spoiler
2 respuestas
B

#4 Ya he dicho en el post que el resto de semanas se hará una votación. Esta primera es un poco a modo de prueba para ver a cuanta gente le interesa.
#7 Avísame cuando lo edites y así no se me olvida ponerte en #1
#8 Yo también llevo poco en esto y la idea era que todo el mundo pueda participar independientemente de su nivel o el lenguaje que conozcan. Por cierto pon dentro del spoiler el resultado que te imprime por pantalla para comprobar que sea correcto y ponerlo arriba, si no tengo que estar ejecutando todos los códigos xd.

1 respuesta
GenBe

#9 Okk, editado. Para la próxima ya lo tendré en cuenta jajaj.

drakkenspain

Algoritmo que calcula el primer número de la sucesión de Fibonacci superior al indicado.
Al principio leí mal, entendí que había que calcular el indice del primer número mayor que 1000.
Para calcular el primer número de 1000 dígitos, bastaría con pasarle a la función 10999, pero JS tiene las limitaciones que tiene, asi que lo he dejado con número superior a 1000 xD

No es la mejor solución, pero es lo primero que se me ha ocurrido

spoiler
1 respuesta
sraam

Estaba esperando a que saliese el resultado y mirando como lo habías solucionado los que ya lo habéis posteado y me ha entrado una duda, viendo lo de #8 #11 , es sacar el index del primer número que tiene 1000 dígitos, verdad?

1 respuesta
drakkenspain

#12 Eso entiendo con el enunciado. Sacar el primer número igual o superior a 10999

2 respuestas
sraam

#13 Me refería al primer número de la secuencia con 1000 digitos, como pone en el enunciado:

F12 = 144 | Es el primer numero con 3 digitos.

Pues lo mismo pero 1000 dígitos en vez de 3.

1 respuesta
GenBe

#14 #13 Okk, lo había entendido mal yo jajaj Pensaba que se refería al primer número mayor que 1000, fallo mío. Pero, un número de 1000 dígitos no sería demasiado grande para meterlo en una variable?

Edit: Okk, no había pensado en las soluciones que habéis puesto. Bien visto.

B

muy muy interesante

sraam

Aquí va mi solución en C#, se que no es la mas limpia pero algo es algo:

spoiler
1 1 respuesta
Soulscx

algo q se me ha ocurrido, no estoy seguro de la solucion pero me sale este numero

spoiler

codigo

spoiler
1 1 respuesta
B

#17 DIN DIN DIN!! Este es el resultado que se busca, el índice del primer número con 1.000 dígitos. El número en si no hacía falta pero aun así se puede poner.

Viendo que hay bastantes confusiones, que os parece si en #1 pongo el resultado esperado de cada problema? Así podeis saber si vuestro resultado es correcto o no.

1
r2d2rigo

Aqui va mi solucion en C#, he usado un enumerador custom para generar tuplas indice/valor y una sentencia LINQ para seleccionar la primera que cumple la condicion:

spoiler

Resultado

spoiler
1 respuesta
drakkenspain

Bueno, pues si nos ponemos exquisitos con la solución aquí esta de nuevo, con el mismo algoritmo que en #11 , pero con un lenguaje de verdad xD

spoiler
1 respuesta
arnaupool

Interesante propuesta, si tengo algo de tiempo libre me pongo a hacerlo.

sraam

Con el de nivel medio tengo un problema, en 11 minutos me ha analizado hasta la longitud 6000 de 1500000. xD

Tengo que darle una vuelta a esto porque así no acaba ni dejando esto toda la semana rodando.

B

#18 Hola! Ese es el número pero fíjate que en el enunciado se pide el índice de ese número, practicamente ya lo tienes, actualiza el resultado y te pongo en #1 :grinning:
#20 Tienes que poner también el resultado que te da ese código para comprobarlo, fallo mío porque no lo había puesto en #1 , ahora actualizo
#21 python verdad? Me suena 'def' pero por si acaso.. :laughing:

3 respuestas
Ranthas

Voy a darle un try a la suma de palíndromos. Mañana sobre esta hora publico resultados (incluyendo un más que factible fracaso).

Kanario93

Yo dejo por aqui mi código, mñn si tengo tiempo intentare hacer los otros.

spoiler
Soulscx

#24 hecho

drakkenspain

#24 Python, eso es.

r2d2rigo

#24 hecho y actualizado.

B

Posible solución al ultimo

spoiler

Aquí la version mostruo

spoiler

Vamos yo he entendio sacar todos los numeros palindromos echos con sumas de potencias de numeros consecutivos menores que 10 elevado a 8...vamos un menores a un millon

2 respuestas