Propuesta para desafíos javascript 2014

[marlanga]

Tras el parón vacacional, aquí os presento un nuevo reto, más fácil que los últimos para que cualquiera pueda participar.

RETO NUEVO
MCD y mcm

Se necesita un par de funciones que sirvan para calcular el Maximo Comun Divisor y minimo común múltiplo de un array de números dados. El array contendrá al menos dos elementos, y todos son los elementos son números enteros positivos.

Así que venga, a currar.


Música de ambientación: http://www.youtube.com/watch?v=H7NC5gYU1Ek

Resumen de retos completados:

+Reto, buscar tercer elemento mas pequeño de un array
Envío de Lynxcraft - Correcto
Envío de Panino5001 - Casi correcto
Envío de pantalaimon - Correcto
Envío de aijona - Correcto
Envío de IsabelM - Correcto
Envío de HackmanC - Correcto
Envío de danny_ - correcto


+Reto codificación morse
Envío de IsabelM - Lo importante es participar
Envío de lynxcraft - correcto
Mi envío - Super-hyper-mega correctísimo. Sin trato de favor.
Envío de Pantalaimon - Correcto


+Reto de ajedrez jaque al rey
Envío de jonni09lo - Correcto
Envío de Pantalaimon - Correcto
Mi envío - Fascinantemente perfecto.

+Reto de pixelar imágenes
Envío de Panino5001 - Correcto
Mi envío - La referencia a seguir.
Envío de Pantalaimon - Correcto

+Reto de juego TRON
Envío de Pantalaimon - Óptimo
Envío de NSD - Eficaz

+Reto de Aproximación a PI
Envío de jonni09lo - Mediante fibbonacci y arcotangente
Mi envío - Mediante montecarlo y aleatoriedad y relación de áreas círculo-cuadrado.
Envío de Pantalaimon - Serie de Taylor e integrales

[jonni09lo]

Bueno allí va mi solución para el ultimo reto http://jsfiddle.net/3EmtD/1/

Para el MCD usé la división de Euclides y para el MCM usé la siguiente formula:



Saludos

[Pantaláimon]

Dejo mi solución, que también utiliza el algoritmo de Euclides(aunque iterativo). Es lo más eficiente, pues ponerte a factorizar los números y luego hallar el MCD y el mcm como tipicamente enseñan en escuela sólo tiene sentido didáctico.

http://jsfiddle.net/jefebrondem/8NEUJ/1/

Mi ejemplo cumple las especificaciones pero he debilitado un poco las condiciones para los argumentos de MCD y mcd, pues no he visto la necesidad de que fueran tan estrictas.

[NSD]

Permitanme revivir un desafio anterior, @Pantaláimon estaba comparando los resultados de mi algoritmo con los del tuyo para hacerlo funcionar siempre y me he topado con que el tuyo tambien falla en determinadas circunstancias por ejemplo en esta: http://jsfiddle.net/2mt8q/2/

[marlanga]

Lo que tú consideras un fallo, no es tal. El algoritmo de pantalaimon es óptimo, siempre encuentra el mejor camino. Eso no quiere decir que el mejor camino sea perfecto para todos los casos.

En cuanto al reto de mcd y MCD, aquí está mi código:
http://jsfiddle.net/marlanga/Gsw9B/1/

Se basa en la misma idea que el resto de envíos, aunque para darle un poco de chicha lo he hecho parecido al de pantalaimon; en vez de un array de números, lo que acepta es un número infinito de argumentos numéricos sobre los que calcular las operaciones. Por supuesto, con un apply, es posible también meterle un array.

[Pantaláimon]

Iniciado por NSD

Permitanme revivir un desafio anterior, @Pantaláimon estaba comparando los resultados de mi algoritmo con los del tuyo para hacerlo funcionar siempre y me he topado con que el tuyo tambien falla en determinadas circunstancias por ejemplo en esta: http://jsfiddle.net/2mt8q/2/

marlanga ya lo ha comentado. El camino es óptimo aunque no recorra todas las casillas. ¿Por qué? Porque no siempre se pueden recorrer todas las casillas. El caso más simple es un tablero 3x3 que lo empiezas desde una casilla lateral que no sea esquina. Pruébalo a lápiz y papel, no podrás recorrerlas todas.

Supongamos para simplificar que en un tablero de ajedrez la casilla superior izquierda siempre es blanca. Entonces, dado un tablero de ajedrez de lados impares si una torre empieza en una casilla negra no podrá recorrer todas las casillas del tablero si se pone la condición de recorrerlas sólo una vez.

La explicación es sencilla:
1) En un tablero de lados impares siempre hay una casilla más de blancas que de negras.
2) Si una torre empieza en un color X y acaba en el color Y habrá recorrido el mismo número de casillas de cada color.
3) Si una torre empieza en un color X y acaba en el color X habrá recorrido una casilla más de color X que de color Y

De manera que la única opción para recorrer todas las casillas en un tablero de ajedrez de lados impares es empezar por una casilla blanca. Traduciendo para TRON, sólo se podrán recorrer todas las celdas en un tablero de lados impares si la suma de coordenadas iniciales es par.

Es un tema al que le di bastantes vueltas cuando salió el problema. He de confesar que consulté en otro foro pues vi que ocurría eso pero no era capaz de demostrarlo y con ello asegurar que hacía un camino óptimo hasta que me dieron esta magnífica demostración.

Un saludo!

[marlanga]

No parece que el número de participantes vaya a crecer mucho, pero me da igual, los pocos que habitamos por aquí resistiremos hasta el final.

RETO NUEVO
La Danza de Ordenación Húngara

VIDEO INDISPENSABLE: http://www.youtube.com/watch?v=ywWBy6J5gz8

Como podeis ver, se trata de un baile húngaro representando un algoritmo de ordenación muy conocido. El reto consiste simplemente en implementarlo en javascript.

Y aunque no pueda hacer nada por evitarlo, lo ideal sería programar el algoritmo simplemente viendo el video, sin buscar en google cómo implementarlo. Y para darle un ligero toque de competición al asunto, en la lista de soluciones pondré el tiempo que tarda cada algoritmo en ejecutarse para ordenar algún array gigantesco.

Ale, a currar.

[Pantaláimon]

Aquí la solución freak:

Código Javascript:

function baileHungaro( bailarines, primero, ultimo ) {
    if( ultimo - primero > 0 ) {
        console.log( 'EMPIEZA EL BAILE ' + primero + '-' + ultimo );
        var sombrero = new Sombrero( bailarines, primero, ultimo );
    
        sombrero.asignarSombrero(  'negro' , primero);
        sombrero.asignarSombrero( 'granate', ultimo );
 
        while( sombrero.negro.sigueBailando() ) {
            sombrero.negro.baila();
            sombrero.granate.baila();
            if( sombrero.negro.parejaAdecuada( sombrero.granate ) ) {
                sombrero.negro.seCruzaCon( sombrero.granate );
            } else {
                sombrero.granate.volverAlSitio();           
            }
            sombrero.granate.pasaSombrero();
        }
 
        baileHungaro( bailarines, primero, sombrero.negro.posicion-1 );
        baileHungaro( bailarines, sombrero.negro.posicion+1,  ultimo );
    }
}
 

Esta es la función principal que la he hecho para que al leerla recuerde a los movimientos que hacen los bailarines en el video. Aquí la versión entera:

http://jsfiddle.net/jefebrondem/pTmpV/

Y luego recordaba de memoria una versión en Haskell de quickSort que era muy bella por lo corta que se podía expresar :

Código Haskell:

quickSort l:ls = quickSort (filter (<l) ls) ++ [l] ++ (filter (>=l) ls)
quickSort [] = []
 

Que en Javascript se transforma en un código desagradable de leer:
http://jsfiddle.net/jefebrondem/93qkp/

Usaré la segunda para el concurso de eficiencia aunque en ninguno de los dos casos la he buscado.

Un saludo!

[marlanga]

Buff, ese algoritmo quicksort en un sólo return es espectacular; aunque quizás se podría mejorar la velocidad ligeramente usando recorridos manuales (for i=0...) en vez de usar filter, concat, slice, etc.

Y qué poca participación xd. Ya no sé si poner otro o seguir esperando.

[Pantaláimon]

Iniciado por marlanga

Buff, ese algoritmo quicksort en un sólo return es espectacular; aunque quizás se podría mejorar la velocidad ligeramente usando recorridos manuales (for i=0...) en vez de usar filter, concat, slice, etc.

Ya, pretendía que la solución más normal la hiciera algún otro participante...

Iniciado por marlanga

Y qué poca participación xd. Ya no sé si poner otro o seguir esperando.

Pues sí, parece que este reto no ha triunfado demasiado. También es verdad que con tráfico de usuarios por este foro en menos de un día puedes encontrarte que el hilo ya no está en la primera página. Es una lástima que los moderadores sigan manteniendo el foro de desafíos 2012 que tiene la mitad de posts que éste y no hayan hecho ningún movimiento para poner este como hilo fijo. Esto ayudaría a que más gente lo viera a primera vista y participara.

A los interesados en este hilo les propongo dos cosas para no perderle la pista. Arriba, adyacente a la barra verde que inicia el hilo hay una opción de "Herramientas" que si la clicas da la opción de "seguir el tema". Abajo del todo te da la opción de votar favorablemente el hilo. Esto lo puede hacer más visible a la par que llamar un poco la atención de los moderadores.

Un saludo!

[Aijoona]

Iniciado por Pantaláimon

Que en Javascript se transforma en un código desagradable de leer:
http://jsfiddle.net/jefebrondem/93qkp/

Usando las fat arrows de ES6:

Código Javascript:

var quickSort = (function(s, f) {
    return function qs(_) {
        return _.length > 1 ?
            [].concat(
                qs(_[s](1)[f]((e) => e < _[0])),
                _[0],
                qs(_[s](1)[f]((e) => e >= _[0]))
            ) : _;
    }
})('slice', 'filter');
 
quickSort([3, 2, 3, 4]); // [2, 3, 3, 4]
 

Revisando vi que las list comprehensions estan activas en Firefox:

Código Javascript:

function qs(xs) {
    var x = xs.splice(0, 1);
    return xs.length > 0 ? [].concat(
        qs([i for (i of xs) if (i < x)]),
        x,
        qs([i for (i of xs) if (i >= x)])
    ) : x;
}
 

Edit: version corregida.

[Pantaláimon]

Iniciado por Aijoona

Usando las fat arrows de ES6:

Iniciado por Aijoona

Revisando vi que las list comprehensions estan activas en Firefox:

¡Me fascina que lleguen a incorporarse estos conceptos en nuevos estándares! Gracias por informar sobre estos.

[dashtrash]

Vaya...no había visto este thread...Aquí va mi versión del ajedrez (me gusta más, es más algorítmico que matemático)
http://jsfiddle.net/tvJLs/2//
No está muy testado y se le pueden sacar algunos caballos más.. Pero un benchmark rápido (sobre 10000 iteraciones, eliminando console.log y dibujados de tablero) da resultados aceptables.

En cualquier caso, sé que no es el más rápido posible.Deberia ser posible hacerlo simplemente iterando sobre las dos reinas.Pero calcular el offset sobre las posiciones en los casos de diagonales lleva un ratito.

[marlanga]

No funciona bien.
Por ejemplo, con reinas en 0,0 y 1,1; y el rey en 2,2, el rey está en jaque pero puede escapar a 2 casillas. Tampoco tiene en cuenta si el rey está en jaque pero se puede comer a una reina para escapar del mate (o como otra posibilidad más de movimiento). Y la opción de que el rey esté "libre" no la contemplas.
Pero me alegra de que haya otro participante.
Hoy me duele el hígado de currar. Mañana probablemente ponga un reto nuevo. Mientras tanto, disfruten de unos minutos musicales: http://www.youtube.com/watch?v=5xVp1mauGnU

[dontexplain]

No sé si puedo proponer, pero propongo un nuevo reto.

Es una contraseña basada en los movimientos del ratón en el interior de una cuadrícula. Por ejemplo, seteas una contraseña realizando cierto movimiento, y luego puedes autentificarte realizando el mismo movimiento.

El margen máximo de error de píxel podría ser 10 píxeles y el margen máximo de cuanto de tiempo los 20 milisegundos con respecto al movimiento anterior. Se trataría pues de trazar los movimientos y encontrar los puntos comunes entre el registro inicial y el registro de autentificación y determinar si la relación es determinante.

Es una tarea complicada, lo sé. Pero mola más si no es un reto pijocutre.

[marlanga]

El número de participantes que envían soluciones es escaso; por ejemplo, tú mismo propones sin haber participado en ninguno. Así que prefiero poner retos mas sencillos para que cualquiera se anime a unirse. Pero esto no tiene por qué impedir que aquellos que quieran intentar el reto que propones, lo hagan.

Y como lo prometido es deuda, aquí va otro reto.

RETO NUEVO
Generador de números aleatorios

Quiero una función que genere un número aleatorio entre 0 y 0.9999999999, ambos inclusive. Para generarlo, podeis usar cualquier locura, a excepción por supuesto de el método Math.random().

Para probar su eficacia, generaré 1.000.000 de números entre 0 y 1000, para ver si el reparto es mas o menos estadìstico.

Ale, a currar.

[dontexplain]

Algo así podría valer.

Código Javascript:

function random()
{
    d = new Date();
    n1 = String( d.getTime() / d.getUTCMilliseconds() ).replace(".","");
    n2 = (n1.toString(16).length > 13) ? Number(n1.toString(16).slice(0,13)) : Number(n1.toString(16)) 
    n3 = Number("0." + String(n2 + new Date().getTime() >> d.getSeconds()).replace("-",""))
    return n3   
}
 

Aunque está claro que un código que he escrito en 5 minutos no va a superar la función random.

[jonni09lo]

Iniciado por dontexplain

Algo así podría valer.

Código Javascript:

function random()
{
    d = new Date();
    n1 = String( d.getTime() / d.getUTCMilliseconds() ).replace(".","");
    n2 = (n1.toString(16).length > 13) ? Number(n1.toString(16).slice(0,13)) : Number(n1.toString(16)) 
    n3 = Number("0." + String(n2 + new Date().getTime() >> d.getSeconds()).replace("-",""))
    return n3   
}
 

Aunque está claro que un código que he escrito en 5 minutos no va a superar la función random.

Hola, creo que podrías mejorarla de alguna manera (si es que le quieres dedicar más de 5 minutos), ya que si la meto en un ciclo esta me repite valores (puede llegar a hacer hasta 5 repeticiones)

PD: Ahora me pongo a hacer los retos para ver de mal humor al gato gruñón

Saludos

[dashtrash]

Iniciado por marlanga

No funciona bien.
Por ejemplo, con reinas en 0,0 y 1,1; y el rey en 2,2, el rey está en jaque pero puede escapar a 2 casillas. Tampoco tiene en cuenta si el rey está en jaque pero se puede comer a una reina para escapar del mate (o como otra posibilidad más de movimiento). Y la opción de que el rey esté "libre" no la contemplas.
http://www.youtube.com/watch?v=5xVp1mauGnU

Ejemplos mostrados en http://jsfiddle.net/NLu2G/ , donde se ve que el algoritmo funciona.Le he añadido el dibujar el tablero, pero el código es el mismo que el fiddle anterior.

[marlanga]

No, el código no es el mismo. Cometiste un pequeño error, y lo has solucionado en ese nuevo envío.

Y sigues sin mostrar si un rey está "libre" en caso de que no esté sufriendo jaque.

[dashtrash]

Iniciado por marlanga

No, el código no es el mismo. Cometiste un pequeño error, y lo has solucionado en ese nuevo envío.

O no.
Cometes un error mirando dos trozos de código son idénticos.
Por lo tanto, al código original sólo le faltaba el caso del rey libre (en eso tienes razón), aunque no afecta al algoritmo.Es una modificacion simple a la interpretación del resultado.
http://jsfiddle.net/NLu2G/2/

Al ser una modificación externa al bucle (como cualquier otra que se tuviera que hacer), no cambia el orden del algoritmo.Sigue siendo 3 veces más rápido que la solución más rápida anterior.

[marlanga]

Iniciado por dashtrash

Vaya...no había visto este thread...
http://jsfiddle.net/tvJLs/2//
No está muy testado y se le pueden sacar algunos caballos más..

Tu código original:
http://jsfiddle.net/tvJLs/2/


La evidencia:
http://jsfiddle.net/tvJLs/3/

Qué modesto eres. Ahora dime que es una conspiración judeomasónica.
En cuanto a lo de "libre", ya sé que es sencillo; solo señalaba que tú aún no lo hiciste y por eso falla en la batería de pruebas. Y como es una postcondición que debe cumplir la función, como fallo lo señalaba. Nada mas.

[dashtrash]

Iniciado por marlanga

Tu código original:
http://jsfiddle.net/tvJLs/2/


La evidencia:
http://jsfiddle.net/tvJLs/3/

La evidencia de qué? De que en un sitio están repetidos los parámetros de la llamada?
Exactamente, en qué línea de código está la "evidencia"?

Iniciado por marlanga

Qué modesto eres.

Iniciado por marlanga

Y aquí pongo el mío, que en tiempo de ejecución hace trizas al resto xd.

Es por estar en sintonía con el thread..Pero sin entrar en calificativos, no llego a tanto.Me quedo en los números.

[dontexplain]

Iniciado por dashtrash

La evidencia de qué? De que en un sitio están repetidos los parámetros de la llamada?
Exactamente, en qué línea de código está la "evidencia"?




Es por estar en sintonía con el thread..Pero sin entrar en calificativos, no llego a tanto.Me quedo en los números.

Es que marlanga es muy modesto....

Pero lleva razón en lo de ser competitivo. Yo llevo un tiempo alejado de estas cosas, demasiado pythoneo y poco javascripteo, él está a la vanguardia.

[marlanga]

No sólo estoy puesto en javascript, también sé algo sobre razonamientos lógicos, y todo tu mensaje, dontextplain, es una gran falacia ad hominem con el único objetivo de ¿atacarme? Una razón tan válida como cualquier otra para secuestrar el tema del post.

Ya sé de mis modales, o mas bien de su ausencia, pero todo el que me "conoce" por haber leído mensajes míos o incluso los tutoriales de mi blog sabe que la mitad de lo que escribo hay que tomárselo a broma y la otra mitad es mentira, que uso mucho el sarcasmo y que no voy a cambiar. http://www.youtube.com/watch?v=-M5qiuf5pd4

El problema es cuando lo que digo alguien se lo toman en serio y además cree el ladrón que todos son de su condición.

Y cada vez que dastrash dice que miento, que su primer envío funciona (como si que tuviera un fallo tonto rápidamente corregido en el segundo, tuviera alguna importancia), me viene a la cabeza la mítica frase

¿A quién va usted a creer, a mí o a vuestros propios ojos? - Grouch Marx

[dontexplain]

Iniciado por marlanga

No sólo estoy puesto en javascript, también sé algo sobre razonamientos lógicos, y todo tu mensaje, dontextplain, es una gran falacia ad hominem con el único objetivo de ¿atacarme? Una razón tan válida como cualquier otra para secuestrar el tema del post.

Ya sé de mis modales, o mas bien de su ausencia, pero todo el que me "conoce" por haber leído mensajes míos o incluso los tutoriales de mi blog sabe que la mitad de lo que escribo hay que tomárselo a broma y la otra mitad es mentira, que uso mucho el sarcasmo y que no voy a cambiar. http://www.youtube.com/watch?v=-M5qiuf5pd4

El problema es cuando lo que digo alguien se lo toman en serio y además cree el ladrón que todos son de su condición.

Y cada vez que dastrash dice que miento, que su primer envío funciona (como si que tuviera un fallo tonto rápidamente corregido en el segundo, tuviera alguna importancia), me viene a la cabeza la mítica frase

Lo único irónico ha sido la primera frase.

Lo demás lo digo seriamente.

Además, si tan interesado estás en que no secuestren tu hilo no entres al trapo y te hubieras ahorrado tu respuesta y mi respuesta a tu respuesta.

El problema es cuando lo que digo alguien se lo toman en serio y además cree el ladrón que todos son de su condición.

Veo que tú también tienes creatividad para falaciar.

[Pantaláimon]

Iniciado por dashtrash

Iniciado por marlanga

Tu código original:
http://jsfiddle.net/tvJLs/2/


La evidencia:
http://jsfiddle.net/tvJLs/3/

La evidencia de qué? De que en un sitio están repetidos los parámetros de la llamada?
Exactamente, en qué línea de código está la "evidencia"?

La evidencia está en que http://jsfiddle.net/tvJLs/2/ y http://jsfiddle.net/tvJLs/3/ son idénticos excepto por los parametros pasados. En el primer código el rey está en [2,1] y las reinas en [0,0] y [3,2]. En el segundo el rey está en [2,2] y las reinas en [0,0] y [1,1]. El segundo código, sin embargo no da el resultado correcto.

Cronología:
1) http://www.forosdelweb.com/f13/propu...ml#post4556394 :
dashtrash propone su primera solución con el rey en [2,1] y reinas en [0,0] y [3,2]: http://jsfiddle.net/tvJLs/2/

2) http://www.forosdelweb.com/f13/propu...ml#post4556939 :
marlanga le dice a dashtrash que existe un fallo cuando el rey estaba en [2,2] y las reinas estaban en [0,0], [1,1]

3) http://www.forosdelweb.com/f13/propu...ml#post4558310 :
dashtrash muestra un nuevo código http://jsfiddle.net/NLu2G/ y dice que es el mismo que el anterior salvo los gráficos.

4) http://www.forosdelweb.com/f13/propu...ml#post4558359 :
marlanga dice que no es cierto, que dashtrash ha rectificado el código.

5) http://www.forosdelweb.com/f13/propu...ml#post4558429 :
dashtrash dice que marlanga comete un error mirando dos trozos de código que son idénticos.

6) http://www.forosdelweb.com/f13/propu...ml#post4558433 :
marlanga le demuestra que, contrariamente a lo que dice dashtrash, los dos códigos no son idénticos porque el primero fallaba. Para ello copia el código del primer envío de dashtrash y le pone los parámetros que ya había indicado en 2) (véase enlace http://jsfiddle.net/tvJLs/3/). Con ello se ve que el código devuelve "jaque mate" cuando el resultado correcto debería ser "2".

Por otra parte, y sin cuestionar la eficiencia de un código respecto a otro (no me he preocupado de mirarlo). Poner un caso particular y repetirlo 10000 veces sólo demuestra que ese código es mas eficiente para ese caso en particular. Para hacer un buen cálculo de la eficiencia debería implementarse un algoritmo que explorara todas las opciones posibles para un rey y dos reinas y, entonces, comparar tiempos.

Un saludo cordial, por si las moscas.

[marlanga]

Dontexplain: Claro, ahora la culpa de tu comportamiento va a ser mía. Jajajaja.
Por cierto, ni entiendo lo que significa "falaciar", ni sé cómo puede haber una falacia en una suposición. Y lo que es peor, tampoco me interesan las respuestas.

PD. Es ingenio creer que no voy a entrar al trapo con el historial de infracciones que tengo, jaja.
Y ahora por favor, vuelvan a centrarse en el código.

PD2. En su primer envío, hay una variable POS que debería haber reseteado hacia la mitad del código y que al no hacerlo provocaba un pequeño error. En su segundo envío lo corrigió. Y que diga que no, y que hallamos llegado hasta esto hace que me parta de risa.

Y sí, me encanta hacer amigos. Este hilo tiene misterio, acción, suspense, drama, comedia... Lo tiene todo, va camino de convertirse en el mejor post del 2014.

[Pantaláimon]

Este último reto me daba bastante pereza hacerlo. Así que he hecho algo sencillo que al menos aparentemente funcione. Digo "aparentemente" porque aunque this.seed toma valores entre 0 y 10000000000, no tengo la certeza teórica de que recorra todos los números. http://jsfiddle.net/jefebrondem/WP4UH/
Parece que la media y la repartición de los números en el intervalo se cumple.

PD.: Ya de paso he aprovechado para probar el funcionamiento de la función random() de dontexplain : http://jsfiddle.net/jefebrondem/WP4UH/1/

[marlanga]

Pantalaimon, buena función de random, parece que reparte bastante bien los resultados. Pero tiene una pega. Random's con la misma semilla darán los mismos resultados al ejecutarla el mismo número de veces. Con alguna idea feliz se puede hacer que además de mediante una semilla, en el "interior" de la función se tenga en cuenta algún tipo de dato adicional para que aunque la semilla sea la misma en diferentes instancias de Random, el resultado varíe.

La de dontexplain, si se ejecuta una vez, parece buena. Si se ejecuta muchas veces seguidas, devolverá el mismo resultado porque el número de milisegundos será el mismo en un procesador rápido.