Coding Dojo #2

El día de ayer tuve la fortuna de asistir al Coding Dojo de manos de los chicos de ViveCodigo, en verdad fue una experiencia enriquecedora y educativa.
Como no tuve una participación muy activa en esta edición me tome la tares de realizar un par de mejoras y terminar los ejercicios.
Ejercicio 1: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?
Le hice una modificación mínima y da el resultado como en 3 segundos, cosa que antes hacia en 3 minutos.

/*
    @rodrigo_salado
*/

def getSolution(n){
    index = 0
    while(n!=0){
        if(isPrime(++index)){
            n--
        }
    }
    index
}

def isPrime(n){
    if(n <= 1) { return false }
    if(n <= 3) { return true  }
    lim = (long) Math.sqrt(n)
    !(2..lim).find{
        n%it == 0
    }
}

assert getSolution(1) == 2
assert getSolution(2) == 3
assert getSolution(3) == 5
assert getSolution(6) == 13
assert getSolution(10001) == 104743

assert isPrime(-1) == false
assert isPrime(0) == false
assert isPrime(1) == false
assert isPrime(2) == true
assert isPrime(3) == true
assert isPrime(4) == false
assert isPrime(5) == true
assert isPrime(6) == false
assert isPrime(7) == true
assert isPrime(8) == false
assert isPrime(9) == false
assert isPrime(10) == false
assert isPrime(11) == true
assert isPrime(12) == false
assert isPrime(13) == true
assert isPrime(14) == false
assert isPrime(15) == false
assert isPrime(16) == false
assert isPrime(17) == true
assert isPrime(18) == false
assert isPrime(19) == true
assert isPrime(20) == false
assert isPrime(21) == false
assert isPrime(22) == false
assert isPrime(23) == true
assert isPrime(24) == false
assert isPrime(25) == false

Ejercico 2: Un conversor de números arábigos a romanos.
Este ejercicio solo lo pude resolver hasta que comprendí como es la notación numérica romana.

/*
    @rodrigo_salado
*/

mil = [0:'', 1000:'M', 2000:'MM', 3000:'MMM']
cen = [0:'', 100:'C', 200:'CC', 300:'CCC', 400:'CD', 500:'D', 600:'DC', 700:'DCC', 800:'DCCC', 900:'CM']
dec = [0:'', 10:'X', 20:'XX', 30:'XXX', 40:'XL', 50:'L', 60:'LX', 70:'LXX', 80:'LXXX', 90:'XC']
uni = [0:'', 1:'I', 2:'II', 3:'III', 4:'IV', 5:'V', 6:'VI', 7:'VII', 8:'VIII', 9:'IX']

num = [mil, cen, dec, uni]

def separaNumeros(n){
    pM = ((int)(n/1000)) * 1000
    n = n%1000
 
    pC = ((int)(n/100 )) * 100
    n = n%100

    pD = ((int)(n/10  )) * 10
    pU = n%10
   
    [pM, pC, pD, pU]
}

def arabigoRomano(n){
   result = ''
   separaNumeros(n).inject(0){v, i ->
       result += num[v][i]
       v+1
   }
   result
}

assert arabigoRomano(1) == 'I'
assert arabigoRomano(2) == 'II'
assert arabigoRomano(3) == 'III'
assert arabigoRomano(4) == 'IV'
assert arabigoRomano(5) == 'V'
assert arabigoRomano(6) == 'VI'
assert arabigoRomano(7) == 'VII'
assert arabigoRomano(8) == 'VIII'
assert arabigoRomano(9) == 'IX'
assert arabigoRomano(45) == 'XLV'
assert arabigoRomano(77) == 'LXXVII'
assert arabigoRomano(97) == 'XCVII'
assert arabigoRomano(193) == 'CXCIII'
assert arabigoRomano(768) == 'DCCLXVIII'
assert arabigoRomano(874) == 'DCCCLXXIV'
assert arabigoRomano(923) == 'CMXXIII'
assert arabigoRomano(1999) == 'MCMXCIX' // ------->>
assert arabigoRomano(2534) == 'MMDXXXIV'
assert arabigoRomano(3863) == 'MMMDCCCLXIII'
assert arabigoRomano(3999) == 'MMMCMXCIX'

assert separaNumeros(0) == [0, 0, 0, 0]
assert separaNumeros(1) == [0, 0, 0, 1]
assert separaNumeros(2) == [0, 0, 0, 2]
assert separaNumeros(22) == [0, 0, 20, 2]
assert separaNumeros(342) == [0, 300, 40, 2]
assert separaNumeros(5342) == [5000, 300, 40, 2]

Saludos y muchas gracias por todo ViveCodigo.

Referencias:
http://vivecodigo.org/coding-dojo/
http://projecteuler.net/problem=7
http://es.wikipedia.org/wiki/Numeraci%C3%B3n_romana

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Imagen de rugi

Se ve que estuvo bueno el

Se ve que estuvo bueno el ambiente.....
Veo dificil ir pronto, pero.... trataré de escaparme un día de estos jejeje

Saludos!!!

"Como no tuve una

"Como no tuve una participación muy activa en esta edición" Uhh? Por que no??

@Rugi, yo también, yo también yo tambien.

:) :) :) :) : ):: ))):):))):):):))::))

Imagen de rugi

Entiendo que, al igual que

Entiendo que, al igual que yo, Oscar tiene horarios un tanto cuanto demandantes.

Por esa razón su insistencia en los streams o en que se graben los eventos ;)

Yo sí te endiendo !!! jejeje

Saludos!!
---

Jajajaj .. este si lo

Jajajaj .. este si lo grabaron, pero estaría chido en streaming para twitter y cerrar el círculo de la comunicación.

Imagen de rodrigo salado anaya

Si se puso genial el coding-dojo...

Si se puso genial el coding-dojo, y con súper anfitrión; deodeveloper, lo que más me gusto, fue ver las soluciones de los demás, lo que menos el silencio mortal a la hora de iniciar los ejercicios. Necesitamos una “gabacha” :P.

@Orcar ammm porque no me salieron ayer los ejercicios :(, pero ya aprendí y como no podía estar sin haber saboreado ese delicioso sabor que te queda después de haber resuelto un problema, pus que me levanto, me cambio, me subo al metrobus y me pongo a leer sobre números romanos, y voila que lo resuelvo : )

Todo muy divertido.

Ahh vaya... mmhh que mal, eso

Ahh vaya... mmhh que mal, eso sucede a veces cuando muuuchas veces. Yo creí que te habían sentado en una esquinita por ahí.

Imagen de yngwie74

Romanos

Lo importante es salir del hoyo sr, y veo que no solo salió, sino que terminó llegando a una solución muy elegante... enhorabuena!!

Desde que está metido en lo del proj. euler como que usa más % y sqrt en su código que de costumbre, no? :-P

Una duda: usaste TDD en el ejercicio de números romanos o las pruebas fueron "after the fact"?

Saludos

Imagen de rodrigo salado anaya

Pues no use TDD pero tampoco...

@Alfred Pues no use TDD pero tampoco hice las pruebas hasta el final. Me ayudo mucho de las pruebas mientras voy desarrollando pero no tengo la disciplina de moverle muy poquito al código, tiendo a saltarme muchos pasos.
Y gracias por los comentarios : )

Tampoco está peleado ( bueno

Tampoco está peleado ( bueno en realidad sí ) sáltate los pasos pero crea el test primero.

Es decir, en vez de que sea TDD, sería Test Supported Development o algo así.

Imagen de ezamudio

TID o TED

Test Inspired Development

Test Encouraged Development

Imagen de yngwie74

Es una diciplina, pero también un skill

Cuando hablamos de TDD, siempre escuchamos el término "diciplina" asociado con el mismo. Sin embargo, no debemos olvidar que la última "D" se refiere a "desarrollo", por lo que al igual que este, entre más lo practiquemos, mejor nos volveremos con el mismo.

Sé que especialmente en el trabajo es difícil hacerlo, pero como un reto personal, trata de desarrollar todo el código que escribas (en tus propios proyectos) durante una semana, usando TDD estricto y después decide si vale o no vale la pena desarrollar esa habilidad.

Imagen de benek

Aquí mis soluciones, no me

Aquí mis soluciones, no me había dado chance de subirlas: https://github.com/benek/CodingDojo2

Tampoco utilicé TDD como tal, la premura y el tiempo limitado fueron factor, para la próxima prometo hacerlo.

CodingDojo

Pues Le di un pequeño refactor al de los números romanos como lo mencione el dia del Dojo lo reduje a que la obtencion del numero romano fuera en un solo metodo y no en los 4 que tenia. EL otro es el de los números primos

que bien

Vaya que bien te quedo el código. Mire el video podcast de viviecodigo y me encanto.

Imagen de rodrigo salado anaya

To linkill

Muchas gracias por el comentario. Sip estubo genial el Dojo :)

Me hizo un poco de ruido el

Me hizo un poco de ruido el comentario de que la razón por la cual estaba tan lento era por la conversión que hace Groovy de todos los objetos y aunque es en parte cierta no creí que fuera la razón principal.

Veo entonces que el cambio de la v1 a la v2 es:

//antes
lim .. < n

// despues
2..lim

Intenté implementar el mismo algoritmo en Java ( en una Dell del 2005 ) y la primera versión se ejecutó en 80 segundos y la segunda en 500 milisegundos!!

Luego entonces, confirmo que no es en realidad el lenguaje sino el algoritmo lo que causo la demora.

Lo más interesante es que hay aún una optimización más a ese algoritmo porque ( a mi entender y puedo estar equivocado ) lo que hace el siguiente código:

!(2..lim).find{
        ....
}

Es iterar todo el rango y ejecutar el closure por cada elemento y luego negar el resultado. El problema con esto es que si se encuentra el resultado de inmediato de todas formas se va a iterar todo el rango ( si el son 10k números y el elemento 10 resultó divisible, aún se van a ejecutar los restantes 9,990 )

Se podría cambiar eso por algo como:

    // Ojo, esta es mi suposición de como se escribe esto en Groovy
   ( 2 .. lim ) .each {
       if ( n % it == 0 ) { return false }
   }
   return true;

y cortar el ciclo tan pronto encontremos que el número no es primo.

Al hacerlo en mi implementación Java, pasé de 80 secs . en la primera versión a 9 secs. y de 500 ms en la segunda versión a 64 ms.!!!

¿Que aprendo con esto?

Entonces no es culpa de los lenguajes de programación solitos... así nomás porque sí ( y me siento un poquito raro defendiendo a Groovy, pero en fin :P ) , tiene mucho que ver ( o siempre tiene que ver ) el algoritmo que se implementa.

También se aprende que aunque es fácil suponer cosas y de hecho es muy necesario para poder atacar el problema, es mucho mejor si se confirma la teoría con un poco de código. Al no hacerlo se queda la idea de: "Groovy es espantosamente lentooo.... , de hacerlo en ____ sería mucho más rápido"

Finalmente que mi propia implementación inicial es ridiculamente mala pues corre en 2 segundos vs. los 64 millisegundos de la segunda versión de Rodrigo.

Y ya.

Ahi les dejo el código por si ocupan.

class PrimosvRSA {
    public static void main( String ... args ) {
        long start = System.currentTimeMillis();
        System.out.println( getSolution( 10001 ) );
        System.out.println(  System.currentTimeMillis() - start + " ms. " );
    }
    private static final int getSolution( int n ) {
        int index = 0;
        while ( n != 0  ) {
            if ( isPrime( ++index  ) ) {
                n--;
            }
        }
        return index;
    }
    private static final boolean isPrime( int n ) {
        if ( n <= 1 ) { return false; }
        if ( n <= 3 ) { return true; }
        int lim = ( int ) Math.sqrt( n );
        boolean resultado = true;
        //for ( int i = lim ; i < n ; i++ ) { //<-- Esta fue la primera version
        for ( int i = 2 ; i <= lim ; i++ ) { //<-- Segunda version ... ok!
            if ( n % i == 0 )  {
                // resultado = false; //<-- esto es lo que hace el !(n..m).find{}  Segun yo
                return false;
            }
        }
        return resultado;
    }
}
/*
Código original
def getSolution(n){
    index = 0
    while(n!=0){
        if(isPrime(++index)){
            n--
        }
    }
    index
}
def isPrime(n){
    if(n <= 1) { return false }
    if(n <= 3) { return true  }
    lim = (long) Math.sqrt(n)
    !(2..lim).find{
        n%it == 0
    }
}
*/

:D

Imagen de ezamudio

find, each

En Groovy, find recibe un closure que ejecuta con cada elemento de la colección, hasta que devuelva true y en ese momento se detiene. Si con el primer elemento devuelve true, ya nada más se ejecutó una vez. Si ningún elemento devolvió true, find devuelve null. Similar a find en Scala.

each ejecuta el closure con cada elemento de la colección, sin importar lo que pase. No toma en cuenta el resultado del closure, no hace nada con él. Es como foreach en Scala.

findAll es como find pero ejecuta el closure con todos los elementos de la colección y devuelve una nueva colección que contiene todos los elementos que hayan dado true (o una colección vacía si ninguno dio true). Es como filter en Scala.

collect ejecuta un closure con todos los elementos de la colección y devuelve una nueva colección con el resultado de cada ejecución del closure. Es como map en Scala.

No sé cómo están implementados los rangos en Groovy pero parece que son bastante ineficientes, sospecho que internamente generan una colección con los elementos contenidos, o sea si defines 1..1000 el rango internamente tendrá una lista de mil enteros. En Scala y en Ceylon únicamente tienen los límites inferior y superior, y su iterador solamente devuelve el elemento siguiente hasta llegar al límite superior; no se generan listas de elementos de manera innecesaria.