Deliciosa, deliciosa manzana T_T

you-feature-deadline-full.png

Advertisements

Bump Map desde Inkscape

Qué es un Bump Map?

Es una textura que indica qué tan elevadas o qué tan profundas están ciertas áreas de un objeto en 3D. Dentro de más blanco, más elevado, y dentro de más negro, más profundo.

Es otra forma de calcular cómo rebota la luz en un objeto, y es diferente del mapa normal, que utiliza los valores RGB como si fuera un vector unitario XYZ que indica la dirección hacia la que la luz debería rebotar.

Bump Map vs Normal Map

El normal map es muucho mejor que el bump map, porque permite un espectro más grande de profundidades, pero el bump map es más fácil de pintar a mano :) y esa es la gran ventaja de hacer bump maps. Si tienes un bump map, puedes “bakear” un mapa normal.

Bump Map en Inkscape!! :D

Por desgracia, no basta con pintar áreas blancas y áreas negras, porque cuando el cambio de alturas es muy paralelo, la profundidad no es muy notoria (al menos, cuando usas mapas normales o bump maps). Abajo, está una caja hecha con bump maps desde inkscape, pero sin gradientes…

sin-gradientes

Bump map hecho en inkscape :D

sin-gradientes-3d

Texturizado

Gradientes

Para que las profundidades resalten más, necesitamos poner “gradientes” de colores, estas gradientes se ven como diagonales al renderizarlas.

Los gradientes de inkscape son un desastre D: una de las razones es porque son muy difíciles de usar y personalizar, por eso, en vez de añadir gradientes, le pondremos algo de “blur”

blur-demo.png

Dentro de menos paralela la diferencia de altura, más blur debería tener

Pero esto nos lleva a otro problema: esa transparencia! las ranuras de la madera se pueden ver a través de los bordes de la X de metal, y eso se va a interpretar en blender como un glitch medio raro…

blur-3d.png

Para arreglar este problema, a cada objeto, debemos ponerle de fondo otro objeto de un color de acuerdo a la elevación en la que queremos que termine la diagonal, y asegurarnos que el “blur” no se sale del fondo que le pusimos.

blur-corrected.png

Ahora ya no hay “transparencias”, así que el renderizado no va a tener esos extraños glitches :D

fixed-bump-3d.png

Bolivia prohibe el Bitcoin

Luego de enterarme de que el BCB (Banco Central Boliviano) prohibió el uso de criptomonedas (de hecho, prohibió el comercio mediante cualquier moneda que no fuera el boliviano o el dólar), me pareció buena idea hacer un cómic sobre el bitcoin y sobre lo absurdo que es betar al bitcoin de Bolivia por las razones que el BCB expuso.

Estoy trabajando en este cómic desde comienzos de este mes, y es porque no sé mucho del tema, pero he estado investigando, y he encontrado agujeros en la mayoría de los argumentos que plantea el BCB! ÒnÓ

Lo que me hace pensar que fue una decisión demasiado apresurada, y que tomaron esta decisión, únicamente para parecer el 1er país lationamericano en dar su opinión respecto a algo que parecía moderno y novedoso, para que nadie creyera que Bolivia no es un país que está a la vanguardia de la tecnología y así ser la envidia de toda latinoamérica.

El cómic tendrá 5 páginas:
1: se trata sobre lo “difícil” que es usar criptomonedas (sí, estoy siendo sarcástica).

2: sobre lo “inseguras” que son.

3: sobre que no son reguladas por ningún estado, y sobre lo “fácil” que es replicarlas

4: sobre el monopolio que cada gobierno debería tener sobre la economía de su país.

5: ¿sorpresa? XD

sí, estoy siendo sarcástica :P

Espero que les guste ^__^ como no soy una experta en el tema, les sugiero que no confíen en mi cómic, lean las referencias (esos asteríscos con un número a la derecha), y creen su propio criterio ~__^

Publicaré la 1ra página del cómic en el transcurso de este día ^o^

Longest Zig Zag Subsequence: Análisis de la solución

Ayer el M.Sc. Jorge Terán, en la materia INF-143 nos planteó este problema… la solución se realizaba mediante dos vectores de tamaño n (donde n es la cantidad de datos). Sin embargo, también se puede solucionar mediante un solo vector de tamaño n, con una complejidad algorítmica de O(n)…

Ahora que tengo tu atención, voy a explicar cómo llegar a esta solución, y luego explicaré cómo es que esta solución funciona XD

Pero primero, sobre lo que encontrarás, y lo que no encontrarás aquí: Si estás esperando encontrar deliciosa copy-pasta del código para terminar tu tarea, te haz equivocado de post! por el contrario, si lo que buscas es entender la solución del problema, este post es para tí!

Statement: (Resúmen)

Para una descripción completa del problema, puedes ver el enunciado que M.Sc. Terán nos pasó en clases

Dada una secuencia de números en determinado orden, esta secuencia se denomina “secuencia zig-zag” si el número que resulta de restar el primer número del segundo, es de un signo distinto que el número que resulta de restar el segundo número del tercero… y este a su vez, es de signo distinto que el resultado de la resta del tercero con el cuarto… y así sucesivamente.

Se asume que el 0 es positivo y negativo ( demostración matemática), por lo que tiene el mismo signo que un número positivo y que un número negativo, y por lo tanto, cualquier secuencia que tenga dos números iguales seguidos, no es una secuencia zigzag.

Por ejemplo:


Datos:   1    5    3   30    8    16  15
Restas:   -4    2   -27   22  -8    1
Signos:   (-)  (+)  (-)  (+)  (-)  (+)

Esta es una secuencia zigzag, porque los signos de sus restas están intercalados.

Dada una secuencia de números, determinar la longitud de la subsequencia zig-zag más grande que se pueda formar con éstos números

una subsecuencia se puede formar eliminando cualquier número de cualquier posición de la secuencia original.

Buscando una solución

cómo sabemos si una secuencia de números es una secuencia zig-zag?

Para determinar esto, necesitamos la resta de los números de la secuencia…


Datos:   1    5    3   30    8    16  15
Restas:   -4    2   -27   22  -8    1

Más concretamente, necesitamos saber la polaridad


Signos:   (-)  (+)  (-)  (+)  (-)  (+)

Eso es! negativo, positivo, negativo, positivo, … eso es lo que buscamos en los números: que:
si hay una resta negativa: después tiene que haber, o bien nada, o bien una resta positiva.

Si hay una resta positiva: después tiene que haber, o bien nada, o bien una resta negativa.

De vuelta al problema… hay que encontrar la subsecuencia zig-zag más larga dentro de una secuencua dada de números. Puedo hacer esto si lo veo como un juego:

¿Cómo convierto una secuencia de números cualquiera, en una secuencia de números zig-zag eliminando la menor cantidad de números posible? Si de convertir se trata, entonces necesitaremos algo más que la polaridad de las restas: también necesitaremos la cantidad de las restas, para saber cuándo un (+) se puede convertir en un (-) luego de eliminar algún número de la secuencia.

Intentemos resolver un problema usando nuestro razonamiento… veamos este caso:


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

Comenzando de izquierda a derecha, podemos ver: -, +, -, ¡-! y encontramos la primera incongruencia en el índice 4! ¿Qué hacemos? tenemos dos opciones:
1 STEP-FORWARD: borrar el índice 4
2 STEP-BACKWARD: borrar el índice 3

¿Cuál de estas dos nos conviene más? no lo sabemos: hay que probar ambas, y ver con cuál se realizarían menos eliminaciones… probemos step-forward: eliminaremos el índice 4:

intentando step-forward


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

*luego de eliminar el índice 4*


indice: 0   1   2   3   4   5   6    7   8 
Datos:  1   17  5   10  15  10  5    16  8 
Restas:  -16  12  -5  -5   5   5   -11   8
Signos:  (-)  (+) (-) (-) (+) (+) (-)  (+)

AAAJÁ!!!!! vieron lo que pasó? lo vieron?! cada vez que eliminas al iésimo número del vector de datos, el iésimo-1 número del vector de restas se suma con el número que tiene a su derecha :D

Ahora, parece obvio que no necesitaremos el vector de datos (de hecho, tampoco necesitaremos un vector de índices ni de signos, pero los dejaremos visibles, ya que ayudan a entender el problema). todo lo que necesitamos es un vector en el que almacenamos las restas de los números!

volvamos a intentar solucionarlo… luego de eliminar el índice 4, se resolvió el problema? parece que no: el problema no se va a solucionar, hasta que el signo del 3er elemento del vector de restas cambie a positivo… así que volvamos a eliminar al índice 4, y hagámoslo hasta que el 3er elemento en el vector de restas se vuelva positivo no olviden que solo hemos eliminado 1 item


indice: 0   1   2   3   4    5    6    7 
Datos:  1   17  5   10  10   5    16   8 
Restas:  -16  12  -5  0    5   -11   8
Signos:  (-)  (+) (-) (?) (+)  (-)   (+)

nope… hay que volver a eliminar el 4… ya llevamos 2 eliminados


indice: 0   1   2   3   4    5    6  
Datos:  1   17  5   10  5    16   8 
Restas:  -16  12  -5  5   -11   8
Signos:  (-)  (+) (-) (+) (-)  (+)

esto sí soluciona el problema! y hemos eliminado a 3 números

¿Qué habría pasado si hubieramos intentado step-backward?

intentando step-backward…

En este camino, intentamos eliminar al número índice 3…


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

luego de eliminar el índice 3…


indice: 0   1   2   4   4   5   6   7    8  
Datos:  1   17  5   13  15  10  5    16  8 
Restas:  -16  12  -8  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (+) (+) (-)  (+)

esto no solucionó el problema… ¿Cuándo se solucionará el problema? cuando el número que está a la derecha del índice 3 del vector de las restas cambie de signo! así que vamos a repetir éste proceso, hasta que el 4to índice del vector de restas se vuelva positivo…

 

¿Qué problemas podrían surgir aquí? podría suceder que… de pronto, en una de las eliminaciones, el número del vector de restas que estamos analizando (el que está en negrillas en el código de arriba), cambie de signo, porque entonces, ya no sería congruente con el número anterior, y tendríamos que volver a analizar tooodo el vector. Pero esto no va a pasar porque, para que esto pase, es necesario que el número que está a la derecha de él tenga un signo diferente al número que estamos analizando, y cuando esto suceda, el problema se habrá solucionado, por lo que no sería necesario eliminarlo!

hasta ahora hemos eliminado 1 número

eliminamos el 4to…


indice: 0   1   2   4   4   5   6   7  
Datos:  1   17  5   15  10  5    16  8 
Restas:  -16  12  -10  5   5   -11   8
Signos:  (-)  (+) (-)  (+) (+) (-)  (+)

Esto soluciona el problema! hemos eliminado 2 números

Así que comparemos: qué solución es mejor en este caso?
STEP-BACKWARD: elimina 2 números.
STEP-FORWARD: elimina 3 números.

Creo que es mejor quedarnos con STEP-BACKWARD, ya que solo elimina 2 números.

Más adelante, nos queda un problema por resolver: dos signos + repetidos! creo que la lógica se ha entendido, así que, no lo resolveré paso por paso.

La Secuencia Zig-Zag más larga que se puede formar, es esta:


indice: 0   1   2    4   4   5    6  
Datos:  1   17  5    15  10  16   8 
Restas:  -16  12  -10  5   -6   8
Signos:  (-)  (+) (-)  (+) (-) (+)

y se forma luego de realizar 3 eliminaciones… su longitud es 7=10-3;

La Solución

“Pero dijiste que era una solución que funcionaba en O(n)!! yo solo veo una gran y obvia recurrencia…”

Con este razonamiento, se puede lograr una solución que funciona en O(n)… en serio! no es tan complicado como parece…

Ya que nos convencimos de que no necesitaremos el vector de los datos, transformaremos esto:


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

en esto


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8

Como solo vamos a recorrer el vector una vez, imagina que este eres tú: ·u· y que estás en el primer elemento del vector:


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:      ·u·

Así que vas a recorrer el vector hasta que encuentres la primera incoherencia, así:


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:      ·u·


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:           ·u·


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·

¡haz encontrado tu primera incoherencia! tienes dos opciones: step-forward o step-backward… así que te declaras dos variables: fw=0 (para step-forward) y bw=0 (para step-backward), también te creas otra variable llamada j… y las inicializas así:


bw+=restas[j-1]; fw+=restas[j]
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·
J:                     j

mientras vas incrementando j… ¿Hasta cuándo hay que repetirlo? hasta que j se salga del vector, o mientras bw tenga el mismo símbolo que restas[j+1] o mientras fw tenga el mismo símbolo que restas[·u·]

¿Por qué? porque bw indica cómo quedaría el número con índice 2 si decides tomar la solución step-backward, así que, en cuanto el número de la derecha (luego de sumarle ‘j’ números) cambie de signo, entonces el problema se habrá solucionado, y se asumirá que se han hecho ‘j – ·u·’ eliminaciones.

Mientras que fw indica cómo quedaría el número con índice 3 si decides tomar la solución step-forward… es casi la misma lógica…

si j se sale del rango, es porque hay que eliminar a todos los que están a partir de tu posición.


bw+=-5; fw+=-3;
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·
J:                     j


bw+=-8; fw+=-5;
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·
J:                        j

¡aquí se cumple una condición de salida!
bw es de diferente signo que restas[j+1], por lo tanto, la mejor solución, es backward, en la que se realizan 2 eliminaciones.

Añades las 2 eliminaciones al contador de eliminaciones, saltas hasta j, y continúas tu camino hasta volver a encontrar una incoherencia… si vuelves a encontrar una incoherencia, repites el proceso…


contador de eliminaciones: 2;
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:                       ·u·

¡Eso es todo! ahora… a codificar! :D

Si se fijan con atención, con este algoritmo, únicamente es necesario recorrer una vez el vector de restas (que tiene una longitud de n-1), lo cual nos da una complejidad algoritmica de O(n-1) = O(n). Además, si al momento de la lectura de los datos, en vez de almacenarlos en un vector, se restan y estas restas se almacenan directamente en un vector, este algoritmo ocuparía un espacio de O(n).

emacs + YASnippet

Estuve buscando por todas partes un .el que, cada vez que escribiera el principio de un tag, este plugin autocompletara el final del tag, y pusiera mi cursor al medio.

Al final lo encontré en la forma de una herramienta mucho más completa, que no solo funciona con tags, sino con  C, C++, C#, Perl, Python, Ruby, SQL, LaTeX, HTML, CSS y más~, dejaré aquí las instrucciones para instalarlo… si todo lo que dije aquí no funciona, o si quieres aprender más sobre YASnippet y cómo añadirle la opción popup, no olvides ver los enlazes en la última sección “fuente”…

¿Cómo? :D

En realidad, es bastante fácil ~_^

Descarga del paquete

Puedes descargar un .zip de esta dirección: https://github.com/capitaomorte/yasnippet/archive/master.zip y luego descomprimirlo en tu ~/.emacs.d/plugins/ (si la carpeta plugins no existe, créala)

También puedes clonar el repositorio en tu ~/.emacs.d/plugins con un


 $ cd ~/.emacs.d/plugins/
 $ git clone https://github.com/capitaomorte/yasnippet.git
 $ cp -r ~/.emacs.d/plugins/yasnippet/snippets ~/.emacs.d/plugins/

Instalación

Luego, solo añades éstas líneas a tu .emacs:

;;YASnippet
(add-to-list 'load-path "~/.emacs.d/plugins/yasnippet") (require 'yasnippet)
(yas-global-mode 1)

;;popup on YASnippet
(require 'popup)
(require 'yasnippet)

;; add some shotcuts in popup menu mode
(define-key popup-menu-keymap (kbd "M-n") 'popup-next)
(define-key popup-menu-keymap (kbd "TAB") 'popup-next)
(define-key popup-menu-keymap (kbd "<tab>") 'popup-next)
(define-key popup-menu-keymap (kbd "<backtab>") 'popup-previous)
(define-key popup-menu-keymap (kbd "M-p") 'popup-previous)

(defun yas/popup-isearch-prompt (prompt choices &optional display-fn)
(when (featurep 'popup)
(popup-menu*
(mapcar
(lambda (choice)
(popup-make-item
(or (and display-fn (funcall display-fn choice))
choice)
:value choice))
choices)
:prompt prompt
;; start isearch mode immediately
:isearch t
)))

(setq yas/prompt-functions '(yas/popup-isearch-prompt yas/no-prompt))

y listo · w ·

Uso…

para usarlo… tienes que escribir una “palabra clave” y luego presionar TAB. Por ejemplo, crea un archivo .html y escribe “div”, luego, presiona tab y selecciona el esqueleto que quieras usar :D

O… entra a un archivo .cpp, escribe “main” y presiona TAB…

Para ver cuáles son palabras clave disponibles, puedes revisar el menú YASnippet (dentro de emacs, la barra superior), y en la primera parte del menú (antes de la primera división de “——————-“) puedes ver *-mode >, y cuando pongas tu cursor sobre eso, aparecerán todos los “snippets” disponibles para el modo de edición en el que estás, y a la derecha de cada uno, la palabra clave que debes insertar, seguido de un “=>”.

Si algo falla, o si quieres aprender más sobre este plugin, te recomiendo estos links:

https://github.com/capitaomorte/yasnippet <— Github de YASnippet
http://iany.me/2012/03/use-popup-isearch-for-yasnippet-prompt/ <— explicación de popups para YASnippet

(Migración de Tumblr a WordPress, fecha original: 2013-09-01)

Emacs: Autocomplete

MasterCard propaganda

Tener Emacs configurado a tu medida: NO TIENE PRECIO

Finalmente logré configurar mi emacs para que funcione con autocomplete! Es fácil, y escribiré un mini tutorial de cómo hacerlo. (Si esto no funciona, talvez deberías leer esto: http://cx4a.org/software/auto-complete/manual.html#Installation ).

Lo primero es descargar el autocomplete. Para hacerlo, sigue este link: http://cx4a.org/software/auto-complete/index.html#Latest_Stable y descarga el *.tar.bz2 Una vez descargado, descomprímelo, para descomprimirlo mediante la consola, accede al directorio en el que descargaste el paquete, y escribe estas líneas:

~/Downloads/ $ tar jxf auto-complete-x.x.x.tar.bz2

Una vez descomprimido, puedes ejecutar el script de instalación (lo cual simplifica muuuucho~ las cosas) el script se encuentra en auto-complete-x.x.x/etc/install.el

Para ejecutar el script, entra a la carpeta auto-complete-x.x.x y haz lo siguiente:

$ make install DIR=$HOME/.emacs.d/

(DIR=$HOME/.emacs.d/ sirve para indicar en dónde está tu emacs).

Por último, para que tu emacs cargue el auto-complete cada vez que arranque, deberás modificar tu .emacs

Para hacer esto, recomiendo fuertemente que hagas un backup, así (tienes que estar como root):

# cd ~
# cp .emacs .emacs.bk

Hasta aquí, hemos creado un backup del archivo, si todo sale mal no entres en pánico!Siempre puedes volver al backup que haz hecho ejecutando:

# cp .emacs.bk .emacs (en caso de pánico)

Ahora sí, vamos a modificar el archivo de arranque del emacs, configurándolo para que cargue el auto-complete… Abre el archivo para su edición con tu editor favorito (por ejemplo, emacs)

$ emacs .emacs & (yo dawg, I herd you like emacs…)

Añádele las siguientes líneas al archivo:

;; Autocomplete
(add-to-list ‘load-path “/home/vg/.emacs.d/”)
(require ‘auto-complete-config)
(add-to-list ‘ac-dictionary-directories “/home/vg/.emacs.d//ac-dict”)
(ac-config-default)

El ‘;;’ es un comentario para documentar. Puedes no documentar, pero no es recomendable, a menos que quieras tener una sopa de código ilegible en el futuro ~_^

y eso es todo~~ si quieres aprender más sobre emacs:

RTFM! (sobre cc mode: http://cc-mode.sourceforge.net/html-manual/ )

Estaré publicando algunas cosas que aprenda sobre configurar el .emacs, pero hasta entonces, estaré RTFM XD Suerte con eso! Y recuerda… para todo lo demás, existe MasterCard ~_^

(Migración de Tumblr a WordPress, fecha original: 2013-10-15)

Competitive Programming

“Given well-known Computer Science (CS) problems, solve them as quickliy as possible!”

Durante todo el 1er semestre (y de hecho, incluso ahora) estuve obsesionada con encontrar mi propia solución a muchos problemas de algoritmia, nunca busqué en internet la solución a ningún problema de programación (a excepción del problema de pasar de notación INFIX  a POSTFIX). Pero en estos últimos días me di cuenta de algo: no tiene sentido continuar así · n ·

Pero, antes de que muchos de mis amigos que aún persisten en la insesante lucha de encontrar sus propias soluciones saquen sus antorchas y quieran quemarme en una hoguera por hereje (Gustavo Callejas :D), permítanme explicar el fundamento de tan herética proposición:

Como desarrolladores, tenemos que ser rápidos, tenemos que encontrar la solución más apropiada para los problemas, pero, si cada vez que nos topamos con algún problema, pretendemos querer solucionarlo desde 0, no solo tardaremos mucho, sino que también, nuestra solución podría no ser la más adecuada.

Podremos ver nuevos horizontes, si y solo si, nos paramos sobre los hombros de los gigantes.

Hay que aceptar que, gran parte de los problemas de algoritmia, ya fueron solucionados por otros programadores brillantes, quienes a su vez, también utilizaron, entendieron y adaptaron, las soluciones de otros programadores brillantes.

¡Ya habrá tiempo para solucionar problemas de algoritmia sin solución! por ahora, es mejor entender todas las soluciones que ya han sido planteadas para poder proponer las nuestras en un futuro (espero, no muy lejano), y que estas soluciones que nosotros contribuyamos (en el futuro), ayuden a otros programadores novatos a solucionar problemas “solucionables” en los contests.

¿Pero… si esto fuera cierto, entonces la ACM-ICPC (y todos los contests de competitive programming) se reducen a copiar, pegar y ver quién typea más rápido? ¡no del todo!

Como desarrolladores, en los contests, tenemos que llevar a los límites nuestro conocimiento de algoritmos, identificando problemas, encajándolos en algoritmos conocidos… está de más decir que, para hacer esto, es necesario conocer muy bien las limitaciones y ventajas de cada uno de los algoritmos, así como su funcionamiento ~_^

Así que, con este post, quiero despedirme de mi orgullo (infundado)… de ahora en adelante, bucaré soluciones parciales!

(Migración de Tumblr a WordPress, fecha original: 2013-10-04)

Programación Dinámica (DP: Dynamic Programming)

La programación dinámica es un tanto confusa, y lo sé! en las últimas semanas, estuve interrogando a muchas personas: “Qué es la programación dinámica?” muchas de ellas respondían conceptos muy confusos, por lo que llegué a concluír (erróneamente) que la programación dinámica era una especie de magia mediante la cual los algoritmos se hacen mucho más eficaces y rápidos, y que todo mago capaz de invocar el conjuro de la programación dinámica de forma exitosa, sería capaz de resolver todos los problemas de algoritmia del mundo…. no… DEL UNIVERSO!

Pero luego de un tiempo, y luego de que Jhtan me explicara varias veces el concepto (btw, gracias ^_^) por fin entendí qué es la programación dinámica:

NO ES MAGIA de hecho, nada es magia… todo tiene su explicación ;)

La programación dinámica tampoco es una forma de solucionar todos los problemas del universo y traer la felicidad y la paz mundial, de hecho, la programación dinámica también tiene sus limitaciones (como cualquier otro paradigma de algoritmia) y no funciona para cualquier problema… como ven, nada es mágico, y, en todo el conocimiento que he coleccionado a lo largo de mi vida, podría asegurarles casi con certeza: nada es mágico, no hay una receta mágica que funcione para todo y garantice perfección, si hacer algoritmos fuera algo automatizable, entonces habrían algoritmos para hacer algoritmos, y por lo tanto, programas que programen programas.
(Pero eso ya es un tema diferente…)

Si la programación dinámica no es magia, y si tampoco es una receta mágica, entonces… ¿Qué es exactamente la programación dinámica? y ¿por qué debería un informático entenderla? Vamos por pasos…

¿Qué es?

La programación dinámica es un paradigma (entre muchos) para resolver problemas. Este paradigma consiste en: utilizar resultados parciales (que el programa ha calculado y guardado en algún lugar) para dar con el resultado requerido. Un ejemplo! (bastante escueto e inútil, pero que ayudará a entender el paradigma): imagina que aún estás en colegio, y tu profesora quiere jugar un juego: ella te dirá una palabra que empieza con “a” y tú tienes que buscarla en el diccionario y leerle su significado… si tus compañeros encuentran la palabra antes que tú, ella te castigará sin recreo (digamos que está loca, y la lleva contra tí, o algo así), por suerte, tú eres más avispado que tus compañeros, y, como sabes que la profesora preguntará una palabra que comience con la letra “a”, separas la sección del diccionario que contiene todas las palabras con la letra “a” y eso te da cierta ventaja.

En el ejemplo, la porción del diccionario que haz separado, constituye un conjunto de resultados parciales, y para encontrar el resultado, buscas entre los resultados parciales el resultado correcto. La programación dinámica se trata, básicamente, de eso: calcular resultados parciales, guardarlos, y luego usarlos (ya sea buscando entre ellos o realizando operaciones con ellos) para obtener el resultado deseado.

Viéndolo así, Gauss utilizó este paradigma para resolver el problema de 1 + 2 + 3 + … + n y simplificarlo en su, tan conocida fórmula n(n+1)/2 cuando aún era niño.

Cuenta la anécdota que, el maestro de aritmética de Gauss le planteó al salón el problema de sumar los primeros 100 números de forma consecutiva (1 + 2 + 3 + … + 100), pero Gauss se dio cuenta que  1+99 = 100 y que  2 + 98 = 100 y que r + ( 100 – r ) = 100 y por lo tanto r + (n – r) = n… y allí está de nuevo resultados parciales, Gauss encontró todos los resultados parciales, los guardó, y se dio cuenta que formaban un rectángulo, luego, se dio cuenta que el resultado deseado era uno de los triángulos contenido en el conjunto de resultados parciales, así que procesó todos estos resultados parciales para obtener el resultado deseado, y de allí viene su fórmula n(n+1)/2.

Ahora vamos a la siguiente pregunta…

¿por qué es importante?

Aunque la programación dinámica no es una receta mágica, es una de las muchas armas que todo informático debería saber empuñar. Hay una gran variedad de problemas que se pueden resolver con programación dinámica, uno de ellos es el de Longest Common Subsequence.

Y bueno, recién estoy entendiendo la programación dinámica y no tengo mucha experiencia en esto del competitive programming y por eso aún no entiendo del todo sus implicaciones…

Pero lo que sí puedo afirmarles con certeza es que, entender (al menos en parte) cómo funciona la programación dinámica, y ser capaz de identificar problemas que requieren de programación dinámica para su solución, me ha dado cierto aire de confianza, la sensación de que, todos los problemas a los que no les encuentro solución, TIENEN una solución, pero primero, necesito aprender una nueva forma de encararlos: de entenderlos.

Y por último, un consejo para entender la programación dinámica: el problema Maximum Sum, el sitio uHunt lo clasifica como un problema de nivel de dificultad 1 (bastante fácil) que se resuelve mediante programación dinámica. Es altamente recomendable resolverlo sin buscar ayuda, por eso, es mejor entenderlo resolviendo este algoritmo… será difícil al principio, pero a mí me funcionó. Solo intenten resolverlo mientras piensan una y otra vez “por qué necesito resultados parciales?” “cómo voy a usar resultados parciales para resolver este problema?”… esto me funcionó a mí… espero que también te funcione a tí ^ w ^

(Migración de Tumblr a WordPress, fecha original: 2013-08-01)

Gay Diagonals

Straight Diagonal - Gay Diagonal

Gay Diagonal

Una anécdota de primer semestre que recordé busacndo la solución a este problema http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=44

What is the opposite of “straight”? XD (Y en serio, entregué así mi tarea… allí fue cuando me di cuenta de que los docentes no leen el código XD)

(Migración de Tumblr a WordPress, fecha original: 2013-08-29)