Una respuesta y otro problema

[Continuacion de Excusas et cetera]

Además de las soluciones de Demian y Guille, armé 5 soluciones propias con distintas características. Pueden verse todos los tests realizados a estas soluciones en el repositorio SVN “asociado” a este blog.

La solución de Guille fallaba a causa del problema identificado por Demian y puede verse a mi solución 4 como una adaptación del algoritmo recursivo de Guille para realizar el bubble sort completo. Aunque bubble sort suele ser duramente criticado, es de hecho óptimo (en las circunstancias apropiadas, ver Improved Bounds on Sorting by Length-Weighted Reversals, Lemma 59 😀 ).

Mis soluciones

A continuación muestro las distintas soluciones que planteé, cada una demostrando algo en particular.

Solución 1 – Arrays

Esta es una solución simple, esencialmente idéntica a la primera de Demian.

void f1(int* a, size_t n)
{
    size_t i = 0, j;
    for (j = 0; j < n; j++)
        if (a[j])
            a[i++] = a[j];
    for (; i < n; i++)
        a[i] = 0;
}
Solución 2 – Punteros

Esta es una adaptación simple de la Solución 1 para utilizar punteros.

void f2(int* p, size_t n)
{
    int *q, *r;
    for (q = p, r = p + n; q < r; q++)
        if (*q)
            *p++ = *q;
    for (; p < r; p++)
        *p = 0;
}
Solución 3 – Obfuscated

Esta es una versión optimizada para ser difícil de entender, empleando solo una definición y un “statement”.

void f3(int* p, size_t n)
{
    int *q = p, *r = p + n;
    while ((r - p) *
           (r - q ? *q ? (*p++ = *q++) : ++q - p : (*p++ = 0) + 1));
}
Solución 4 – Recursiva

Esta es la solución de Guille, adaptada para realizar una pasada completa de “burbujeo” en cada llamada recursiva. De las soluciones que encontré, es la única que no requiere variables adicionales (aunque obviamente utiliza múltiples instancias del stack frame).

void f4(int* p, size_t n)
{
    if (n == 0)
        return;
    f4(p + 1, n - 1);
    while (n >= 2)
    {
        if (!p[0] && p[1])
        {
            /* xor swap */
            /* Proof:
               p0' = p0 ^ p1
               p1f = p1 ^ p0'
                   = p1 ^ p0 ^ p1
                   = p0
               p0f = p0' ^ p1f
                   = p0 ^ p1 ^ p0
                   = p1
            */
            p[0] ^= p[1];
            p[1] ^= p[0];
            p[0] ^= p[1];
        }
        p++;
        n--;
    }
}
Solución 5 – Utilizando solo una variable extra

Esta solución es una “mezcla” de las soluciones 1 y 2 modificada para utilizar solo una variable temporal. Dudo que sea posible resolver el problema sin variables temporales extras (aparte de los parámetros), pero no parece simple probarlo…

void f8(int* a, size_t n)
{
    size_t j;
    for (j = 0; j < n; j++)
    {
        if (a[j])
            a[0] = a[j], a++, j--, n--;
    }
    for (j = 0; j < n; j++)
        a[j] = 0;
}

Un problema matemático

Hace unos días vi en el blog de Michael Nielsen un interesante problema:

Dado un conjunto de 51 números dentro del intervalo 1-100 (incluyendo los extremos), demostrar que existen al menos dos números en ese conjunto que no comparten ningún divisor (a excepción de 1, obviamente).

(No, no vi inmediatamente la respuesta 😀 )

Advertisements

2 thoughts on “Una respuesta y otro problema

  1. Demian says:

    Jeje, tardé como 15 minutos en entender la solución ofuscada (me mató el operador condicional dentro del segundo operando de otro operador condicional… sólo estaba acostumbrado a verlo en el tercer operando (para lograr esas expresiones tipo switch)), pero está muy buena!

    Y, si bien me alegra (?) ver el uso del XOR-swap para ahorrar una variable, me extraña verlo partido en tantas lineas, obligando el uso innecesario de llaves… En vez de escribir

    a ^= b;
    b ^= a;
    a ^= b;

    se puede hace un poco de golf y dejarlo en una sola linea:

    a ^= b ^= a ^= b;

    Ese código no solamente es hermoso, también es suficientemente chico como para meterlo en casi cualquier lugar en vez de un costoso swap(&a, &b) y ganarse el aprecio de los compañeros de proyecto.

    —-

    Sobre el problema de los números, sale. Yo particularmente tardé bastante en sacar la respuesta, que resultó ser mucho más simple/elegante que los dos o tres enfoques que había pensado. Me gustaría ver si alguien la saca al toque jeje.

    • mchouza says:

      Y, si bien me alegra (?) ver el uso del XOR-swap para ahorrar una variable, me extraña verlo partido en tantas lineas, obligando el uso innecesario de llaves… En vez de escribir

      [código omitido]

      se puede hace un poco de golf y dejarlo en una sola linea:

      [código omitido]

      Si. Pensé en usar el operador coma para evitar las llaves, pero no en concatenar los operadores. Queda lindo.

      Sobre el problema de los números, sale. Yo particularmente tardé bastante en sacar la respuesta, que resultó ser mucho más simple/elegante que los dos o tres enfoques que había pensado. Me gustaría ver si alguien la saca al toque jeje.

      Bueno, se que algunos lo sacarían al toque, pero dudo que alguien que lea (regularmente) el blog. (Si, es un desafío encubierto. 😛 )

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s