Retos para desarrolladores

Entre crisis, abogados, hipotecas, y tareas del hogar (aunque éstas últimas no terminen nunca para mi frustración), últimamente he tenido poco tiempo libre para disfrutar de mi afición como programador, que aunque también sea mi profesión, no deja de ser un hobbie con el disfruto de mi tiempo libre.

"Busca un trabajo que te guste y no tendrás que trabajar un sólo día de tu vida". 
Cita sabia del filosofo chino Confucio.

Cansado ya de dedicar mi tiempo libre a resolver problemas de mi vida cotidiana que me divierten mas bien poco, me aportan mas bien nada, y me limitan mi capacidad de aprendizaje y mejora continua de mis aptitudes profesionales, hoy por fin encontré el día perfecto para pasar un buen rato con mi buen amigo 'Dellone' (así es como bauticé este verano a mi primer portátil Dell)

Era una tarde de Sábado gris, lluviosa y fría. Otro de esos días perfectos en los que no se me ocurría nada mejor que sentarte delante del portátil y disfrutar junto al calor de sus ventiladores resolviendo alguna de las muchas tareas que tenia pendientes en mi lista de TODOs personales.



La tarea elegida hoy fue resolver el reto para desarrolladores publicados en el portal The Greplin Programming Challenge. Conocí estos retos gracias a un compañero de trabajo, a quien desde aquí le agradezco la información porque he pasado una tarde muy entretenida. Gracias Dani! ;)

Sobre el nivel del reto, comentar que son tres problemas que exigen unos conocimientos en algorítmica de lo mas básicos. En todo caso, es el tercer reto el que exige un poquito de imaginación para dar con la solución. Pero poco mas. Todo aquel con experiencia 'picando código' debería poder resolverlos sin mayores problemas.

Las soluciones que publico han sido desarrolladas en C, que a mi es el lenguaje que más me gusta. Pero el lenguaje usado para resolverlos es indiferente, podéis usar el que mas os guste (o el que mas os disguste, hay mucho masoca suelto por ahí...)

El primer reto se introduce con esta explicación:

 The Greplin Programming Challenge
 
 Level 1
 
 ----------------------------------------

 Embedded in this block of text is the password for level 2.
 The password is the longest substring that is the same in reverse.
 
 As an example, if the input was "I like racecars that go fast"
 the password would be "racecar".

La solución que propongo al primer reto es esta:

#include stdio.h
#include string.h

const char g_cad[] = 
"Fourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinz"
"LibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtci"
"vilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeare"
"qmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrest"
"ingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandprope"
"rthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowth"
"isgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwe"
"rtoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverfo"
"rgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhicht"
"heywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattd"
"afskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhic"
"htheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothave"
"diedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeop"
"lebythepeopleforthepeopleshallnotperishfromtheearth";

int is_str_palindrome(const char * init, const char * end)
{
    while ((*init == *end) && (init <= end)) {
        init++;
        end--;
    }

    return (init >= end);
}

int main(void)
{
    int l = strlen(g_cad);
    int i, j, ibest, lbest;

    ibest = lbest = 0;

    for (j = l - 1; j > 0; j--) {
        for (i = 0; i < j; i++) {
            if (is_str_palindrome(g_cad+i, g_cad+j))
                if (j-i > lbest) {
                    ibest = i;
                    lbest = j-i+1;
                }
        }
    }

    printf("Solution to challenge 1 is '%.*s'\n", lbest, g_cad+ibest);
}

El segundo reto se introduce con esta explicación:

 The Greplin Programming Challenge
 
 Level 2
 
 ----------------------------------------

 Congratulations.  You have reached level 2.
 
 To get the password for level 3, write code to find the first prime
 fibonacci number larger than a given minimum.  For example, the first
 prime fibonacci number larger than 10 is 13.

 When you are ready, go here or call this automated
 number (415) 799-9454.
 
 You will receive additional instructions at that time.  For the second portion
 of this task, note that for the number 12 we consider the sum of the prime divisors
 to be 2 + 3 = 5.  We do not include 2 twice even though it divides 12 twice.

La solución que propongo al segundo reto es esta:

#include stdio.h

unsigned long next_fibonacci()
{
    static unsigned long a = 0;
    static unsigned long b = 1;
    unsigned long nf = a + b;

    a = b;
    b = nf;

    return nf;
}

unsigned long next_prime()
{
    static unsigned long prime = 0;
    unsigned long tested = prime + 1;

    while (1) {
        if (is_prime(tested)) {
            prime = tested;
            return prime;
        } else {
            tested++;
        }
    }
}

int is_prime(unsigned long tested)
{
    unsigned long divisor;

    for (divisor = (tested / 2); divisor > 1; divisor--)
        if ((tested % divisor) == 0)
            return 0;

    return 1;
}

int main(void)
{
    unsigned long given_minimum = 227000;
    unsigned long X;

    while ((X = next_fibonacci()) < given_minimum)
        ;

    while (!is_prime(X))
        X = next_fibonacci();

    X += 1;

    int np = next_prime(); // 1

    int challenge2 = 0;

    while (X != 1) {
        np = next_prime();

        if ((X % np) == 0) {
            while ((X % np) == 0)
                X = X / np;
            challenge2 += np;
        }
    }

    printf("Solution to challenge 2 is %d\n", challenge2);
}

Y por ultimo, el tercer reto se introduce con esta explicación:

 The Greplin Programming Challenge
 
 Level 3
 
 ----------------------------------------

 Congratulations.  You have reached the final level.
 
 For the final task, you must find all subsets of an array
 where the largest number is the sum of the remaining numbers.
 For example, for an input of:

 (1, 2, 3, 4, 6)

 the subsets would be

 1 + 2 = 3
 1 + 3 = 4
 2 + 4 = 6
 1 + 2 + 3 = 6
 
 Here is the list of numbers you should run your code on.
 The password is the number of subsets.  In the above case the
 answer would be 4.

Y la solución que propongo al tercer reto, es esta:

#include stdio.h
#include math.h

/* Input param */
int g_set[] = { 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99 };

int g_setlen = sizeof(g_set) / sizeof(int);

int is_membership(int v)
{
    int i;

    for (i = 0; i < g_setlen; i++)
        if (g_set[i] == v) {
            return 1;
        }

    return 0;
}

int is_onebit(int v)
{
    int i;
    for (i = 0; i < g_setlen; i++)
        if (v == (pow(2, i)))
            return 1;
    return 0;
}

int main(void)
{
    int mask;
    int m;
    int aux;
    int pos;
    unsigned int N = pow(2, g_setlen);
    int challenge3 = 0;

    for (mask = 1; mask < N; mask++)
    {
        if (is_onebit(mask))
            continue;

        aux = mask;
        pos = 0;
        m = 0;
        while (aux != 0) {
            if (aux & 0x01)
                m += g_set[pos];
            aux = aux >> 1;
            pos++;
        }

        if (is_membership(m))
            challenge3++;
    }

    printf("Solution to challenge 3 is %d\n", challenge3);
}

Todos los desarrolladores que estáis leyendo esto conocéis la sensación de satisfacción inmensa que produce dar con la solución al problema y "avanzar al siguiente nivel". Pienso que esa es la droga que nos metemos los que trabajamos en esto y nos mantiene tan enganchados a esta entretenida profesión (si, somos unos jonkies!! :) Y este es el premio que obtendréis al terminar el reto:

 The Greplin Programming Challenge

 The End

 ----------------------------------------

 Congratulations.  You completed the challenge.  Your completion code is 118-170-234969.

 We'd love to talk to you - send your completion code, the code you wrote
 during the challenge, and your resume to

 USER at SUBDOMAIN dot DOMAIN

 Even if you're not looking for a job, we'd love to hear what you thought
 about the challenge.

La dirección de correo la protejo para evitar spam innecesario a los organizadores. Eso si, si alguno de los lectores esta en paro, y tiene en mente trabajar en Estados Unidos, igual es ésta vuestra oportunidad. !Al menos intentadlo! :)

Para los que sigáis con el gusanillo de resolver mas problemas de este estilo, os dejo aqui otro enlace a un reto para desarrolladores bastante famosillo, The Euler Project, con mas de 300 problemas que resolver, un gran número de participantes registrados repartidos por los cinco continentes, y un ranking en el que estareis compitiendo contra todos ellos. Si alguien se aburre con este reto, que hable conmigo que está contratado! :P



Como veis en la imagen adjunta, solo he podido terminar los 7 primeros. La falta de tiempo libre me obliga a mantener abandonadas algunas tareas que me gustaría continuar a medida que recupere el control de mi tiempo libre. Animo a todos los lectores que compartan mi afición a que lo intenten, pregunten dudas, compartan las soluciones, y así poder comentarlas y buscar entre todos la solución óptima en cuanto a coste computacional, etc. Espero que lo disfrutéis. Y ya sobran mas explicaciones. ¡A programar se ha dicho!