Archivos mensuales: Ago PM

10 entradas

php7-logo

PrEDA: el juego de las Torres de Hanói

Hoy traigo otro enigma matemático resuelto a modo de code-kata, un rompecabezas llamado las Torres de Hanói. El juego consiste en tres torres compuestas por discos que se apilan de forma decreciente, de forma que los discos de abajo siempre son mayores que los de arriba. Con cada movimiento sólo podemos mover un disco. Y tenemos que conseguir mover todos los discos que inicialmente están todos en la torre A a la torre B. Haciendo ensayos, pruebas, partiendo de casos fáciles a más difíciles se puede establecer una estrategia por la cual se van moviendo todos los discos. Este problema bien conocido en computación se resuelve mediante la estrategia de divide y vencerás. Dividiendo el problema inicial, todos los discos en una torre, en subproblemas cada vez más sencillos y fáciles de abordar. Se trata de un algoritmo recursivo. Cuyo caso base es mover un sólo disco. Si no estamos moviendo un sólo disco se subdivide en 2 problemas y se mueve un disco.

php7-logo

PrEDA: el problema del Salto del Caballo de ajedrez

Hoy traigo otro code-kata para practicar con estructuras de datos y algoritmos. El problema del caballo es un clásico problema matemático. Consiste en recorrer todas las casillas de un tablero de ajedrez sin repetirlas y a salto del caballo. Esta vez, la forma más sencilla de abordarlo es simular el salto del caballo haciendo un árbol de posibles recorridos del caballo hasta conseguir llenar el tablero por completo. Es decir, partimos de una casilla, este será el nodo inicial del árbol. Entonces los hijos de cada nodo son los caminos posibles desde el nodo inicial hasta las casillas posibles siguientes. Si estamos en un tablero de 8×8, y hemos llegado a un nivel de ramificación de 64 quiere decir que hemos recorrido todas las casillas que hay. Entonces habríamos resuelto una de las soluciones. La mejor forma de resolver este problema es por la estrategia de vuelta atrás. Es decir, se va ramificando mientras que el caballo va saltando. Si llega a una casilla en la que ya no tiene casillas a las que saltar se vuelve atrás, para entonces seguir ramificando por el resto de posibles caminos. Esto con una función recursiva queda bien sencillo.

YoRobot4 - Text to HTML ratio

Yo, robot IV – White/Gray/Black Hat SEO – El Text to HTML ratio

El contenido es el rey para el posicionamiento, rezan muchos SEOs y muchas herramientas para SEOs. He leído por Internet que muchos hablan de que lo más importante para posicionar las páginas web es que el contenido sea bueno, que sea geniuno, interesante para el usuario. Desde nuestro punto de vista, tenemos varios enfoques para hacernos una idea de si el contenido de una web es bueno. El más sencillo es la tasa que hay entre el texto y el código HTML, CSS y Javascript de nuestra web. Realmente, es la tasa entre el texto y el HTML, CSS y Javascript, aunque muchos se olvidan de que no sólo hay HTML.. Y muchas veces este CSS y Javascript puede ser tanto que la tasa de texto resultante baje demasiado. Todo esto se reduce en la tasa llamada Text to HTML ratio.

php7-logo

PrEDA: distribuir cosas con volumen en el mínimo de paquetes disponibles

Hoy traigo de nuevo otro code-cata, para resolver el clásico problema de llenar paquetes con cosas de volumen variable, usando el mínimo de paquetes posible. Este problema de igual modo que los anteriores, se podría resolver de varias formas. Pero la forma más eficiente es usar el algoritmo de ramificación y poda. El algoritmo de ramificación y poda, mediante este refinamiento, es una variante del de vuelta atrás. Como es habitual comenzamos generando todas las posibles soluciones como si lo resolviéramos por fuerza bruta. Generando un árbol de soluciones, haciendo la misma vuelta atrás para las soluciones no posibles. Es decir, haremos vuelta atrás si ya no caben más cosas en el paquete que estemos llenando; ramificando llenando la siguiente cosa en el siguiente paquete. También haremos vuelta atrás si hemos hecho un llenado completo con todas las cosas, para continuar estudiando la siguiente ramificación posible.

php7-logo

PrEDA: distribuir cosas no fraccionables en dos conjuntos equitativamente

Imaginemos que tenemos cosas de varios valores, y tenemos que dividir todo en dos partes. De forma que a cada parte le toca un conjunto de cosas de igual valor que a la otra parte. Esto se da en casos como en la separación de bienes entre dos cónyuges, o cuando se liquida una sociedad entre dos socios, o en el reparto de un botín entre dos piratas o corsarios 😀 Con un poco más de desarrollo se puede generalizar para la división en N conjuntos. Para atacar este problema la mejor estrategia de programación es la vuelta atrás. No es eficiente usar la fuerza bruta, tampoco podemos encontrar una forma de decidir la mejor partición para cada nuevo elemento para usar la estrategia voraz. Tampoco podemos usar el divide y vencerás. Y por último tenemos que encontrar no sólo una solución, sino todas las soluciones posibles. Así que no nos queda otra que recorrer creando un árbol de combinaciones. Pero sin entrar a comprobar todas las posibilidades ya que crearíamos un algoritmo de fuerza bruta. Sino que iremos sólo explorando el árbol de posibilidades que quizá nos sirven como solución. En cada ramificación pondremos cada nuevo objeto en un […]

php7-logo

PrEDA: formando palabras con dados de letras

Hoy traigo otro script de estudio a modo de code-kata. Se trata de una variante de juego de mesa en el que hay que formar palabras con dados de letras. Es decir, tenemos unos dados que toman letras aleatoriamente. Teniendo entonces N dados de 6 letras cada uno. A su vez, se forman palabras aleatoriamente del mismo tamaño que la cantidad de dados que tenemos. Comienza el juego; tenemos que encontrar si combinando dichos dados podemos formar la palabra. Para dar la respuesta hay que decir en qué posición ponemos cada dado y en qué cara.

php7-logo

PrEDA: generador de palabras con restricciones

Aquí dejo un pequeño code-kata sobre cómo generar todas las palabras posibles con ciertas condiciones hecho en PHP. Se aplica el algoritmo de vuelta atrás, ramificando y podando el árbol de soluciones. Se usa este algoritmo porque tenemos que encontrar todas las posibles soluciones al problema. Pero debemos de cortar cada posible ramificación lo antes posible, haciendo una vuelta atrás, para continuar explorando por la siguiente rama de posibles soluciones. De nuevo, también podemos generar las palabras a lo bruto para después ir comprobando si cumplen las restricciones. Pero será más eficiente tanto en tiempo como en espacio con esta estrategia de programación. Será mejor ir generarando las palabras e ir comprobando mientras que se van construyendo. La estrategia consiste en ir añadiendo letra a letra e ir comprobando si la nueva letra añadida puede ser una solución.

php7-logo

PrEDA: cálculo del elemento mayoritario de un vector

Hoy vengo a compartir un algoritmo de programación para resolver el problema de calcular el elemento mayoritario de un vector. Podemos hacerlo a lo bruto, directamente calculando cuántas veces se repite cada elemento. Pero aquí la historia está en aplicar la estrategia de programación divide y vencerás. Si un elemento es mayoritario en un vector de n elementos, entonces se repite por lo menos n/2+1 veces. La estrategia consiste en que si un elemento es mayoritario en una mitad del vector, entonces es candidato para ser mayoritario. El problema inicial se subdivide en subproblemas hacia abajo más sencillos de resolver, para luego combinar las soluciones hacia arriba hasta llegar a la solución. Nice coding!

YoRobot3 - El Time To First Byte

Yo, robot III – White/Gray/Black Hat SEO – El Time To First Byte

Hoy vengo a compartir otro pequeño script para testear el tiempo de respuesta de un servidor. Este es el llamado TTFB, Time To First Byte en inglés. Simplemente es el tiempo que pasa entre que tu navegador pide una web hasta que empieza el servidor a enviar los bytes de respuesta. Esta prueba nos da una buena visión de si el servidor y la web se pueden optimizar. Un TTFB bajo es buena señal, indica que tanto el servidor (a nivel hardware y software) como la aplicación web esta todo bien optimizado. Sino, ya tenemos algo en lo que enfocarnos.

YoRobot2

Yo, robot II – White/Gray/Black Hat SEO – Navegando por toda una web..

Hoy traigo otro pequeño HOWTO para recorrer una web mediante dos scripts de PHP de unas 30 líneas de código. Sí, 30 líneas, no hace falta mucho para empezar a crawlear. Hay herramientas para hacer esto, incluso algunas libres, aunque limitadas en funcionalidades. De todas formas es muy divertido hacer a modo de code-kata un robot que crawlee una web. Luego lo puedes reutilizar para un sinfin de cosas: si necesitas hacer auditorías, recopilar información, generar resultados, o re-generar más información con los contenidos crawleados.. probablemente con un simple desarrollo lo puedes resolver en poco tiempo. Quizá estás pensando en automatizar todo esto.. O quizá simplemente quieres forzar que tu web se cachee y así vaya más rápido.. Es la única forma de no estar limitado a lo que la herramienta de turno puede hacer. Si se puede pensar, se puede hacer.. pero ¡ojo! que no todo está permitido en este mundillo. Un poco de teoría Crawlear: es el hecho de recorrer una web obteniendo información sobre esta. Puede interesarte simplemente su estructura, si el HTML está bien formado, si tiene encabezados, utiliza secciones, etc.. Scrapear: es el hecho de guardarse la información contenida en las webs. Si luego reutilizas […]