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… 😀
Spin Foam 
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]
Huy, me mató toda la indentación =(
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).
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
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; }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.
Es verdad Demian, podría pensarse como un bubble-sort con una función de comparación especial. Tenés razón en lo que decís, encontré ese error al rato de postearlo, se lo mencioné a Mariano y me olvidé de corregirlo :S
Asi que, para no dejar las cosas inconclusas acá va:
http://codepad.org/xMPHFa8i
Ahi se puede ejecutar en forma online el ejemplo
Saludos!
Me encantó el codepad! Bookmarkeado!
Coincido con Demian… el Codepad es una muy buena idea. Eso me pasa por no visitar más seguido Hacker News… 😀
[…] de las soluciones de Demian y Guille, armé 5 soluciones propias con distintas características. Pueden verse todos los tests realizados […]