Excusas et cetera

Originalmente tenía pensado publicar la primera parte de la respuesta al post sobre detección de cubos este fin de semana pasado, pero los videos de Susskind y Coleman sobre QFT se interpusieron 😀

Siempre creí que las clases expositivas eran bastante redundantes pero, cuando el material es dificultoso como en este caso, el inevitable “unpacking” que ocurre al explicar los temas “en vivo” se vuelve una ventaja importante. Los videos de Susskind son bastante fáciles de seguir para los que fueron siguiendo la serie en general, pero a veces pueden resultar un poco “handwavy”. Los de Coleman son bastante más rigurosos pero tienen mala calidad de filmación (incluso para 1975) y presuponen más conocimientos matemáticos y de mecánica cuántica de los que tengo, lo que me dificulta seguirlos.

Para no dejar todo en la nada, ofrezco un problema de programación C inspirado en uno visto (si no recuerdo mal) en algún comentario en el blog de Eric Raymond:

Enunciado:

Dado un vector de enteros, implementar una función que mueva “en el lugar” los ceros al final del vector dejando los otros enteros en el orden original. El prototipo de la función deberá ser:

void foo(int* a, size_t n).

Ejemplos de efectos sobre el vector pasado por parámetro:

{5, 0, 4, 0, 0, 3, 0, 0, 0, 2} --> {5, 4, 3, 2, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 1, 2, 3, 0, 4} --> {1, 2, 3, 4, 0, 0, 0, 0}

Algunas respuestas a esto, salvando fuerza mayor, este fin de semana. Ustedes pueden dejar otras respuestas en los comentarios que serán debidamente analizadas… 😀

Advertisements

10 thoughts on “Excusas et cetera

  1. Demian says:

    Le voy a pegar un vistazo a las clases de Susskind, definitivamente me puede aclarar un poco las cosas jeje. Es mucho material!

    Sobre el problema de programación, hallar una solución sencilla es bastante facil. Ahora, una eficiente, no se. No se me ocurre nada que no sea O(n).

    En un principio se me ocurrió que en vez de “mover los ceros al final” como dice el enunciado, es mucho más sencillo, para poder conservar el orden, mover los números distintos a cero al principio, y después escribir todos ceros al final.

    void foo(int* a, size_t n)
    {
    	size_t top = 0;
    	for (size_t i = 0; i < n; ++i)
    		if (a[i] != 0)
    			a[top++] = a[i];
    
    	for (size_t i = top; i < n; ++i)
    		a[i] = 0;
    }
    

    Pero con la misma idea, se puede simplemente intercambiar los elementos y se ahorra un ciclo =P

    void foo2(int* a, size_t n)
    {
    	size_t top = 0;
    	for (size_t i = 0; i < n; ++i)
    		if (a[i] != 0)
    			swap(a, i, top++);
    }
    

    Se podría hacer el swap sólo cuando i != top si las escrituras en memoria fueran una preocupación, pero eso destruiría la elegancia del operador postincremento sobre top jeje

    [Editado por Mariano Chouza]

    • Demian says:

      Huy, me mató toda la indentación =(

      • mchouza says:

        Ahí edité tu primer comentario para preservar indentación. Podés usar [ code lang=’c’ ] codigo fuente [ /code ] para que te use las “cajitas” con syntax highlighting (sin los espacios; no se como se hace escaping en WordPress).

  2. Demian says:

    Ha, ahí quedó buenísimo, gracias =). Además tiene unas lindas opciones la cajita de código. Lástima que no deje previsualizar los comentarios wordpress :S

  3. Guille says:

    Hola Mariano,

    Acá dejo otra posible solución al problema.
    Saludos!

    void foo(int *a, size_t n){
    	if (n <= 1) return;
    
    	if (!(*a)){
    		if (*(a+1)){
    			swap(a, a+1);
    		}
    	}
    
    	foo(a+1, n-1);
    }
    
    void swap (int* x, int* y){
    	int z= *x;
    	*x= *y;
    	*y= z;
    }
    
  4. Demian says:

    Tiene una onda bubble-sort recursivo eso, Guille =P

    El tema es que en esa sola pasada va a dejar un cero al final seguro, y va a mover los no-ceros hacia adelante en una posición. Por ejemplo, el primer vector que propone Mariano lo deja:

    {5, 0, 4, 0, 0, 3, 0, 0, 0, 2} –> {5, 4, 0, 0, 3, 0, 0, 0, 2, 0}

    Pero necesitaría hacer n pasadas de esas, siempre desde el primer elemento hasta el n – i en cada i-ésima pasada, tipo bubble-sort, para completar con la tarea.

  5. […] de las soluciones de Demian y Guille, armé 5 soluciones propias con distintas características. Pueden verse todos los tests realizados […]

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