PHP

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.

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 conjunto o en otro. Así que ramificaremos de dos en dos ya que vamos a divir en dos conjuntos. Viendo la salida por pantalla se verá claro..

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.

De nuevo tenemos varias formas de resolverlo. Podríamos combinar a lo bruto los dados, cara a cara, comprobando si la solución es posible. La forma mas rápida y eficiente es usando el algoritmo de vuelta atrás. Tenemos que explorar todas las posibles soluciones, recorriendo el árbol completo de posibles soluciones. La lógica para resolverlo es ir poniendo dado a dado, haciendo llamadas recursivas para construir el árbol.

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.

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!