Archivos diarios: 23/08/2017

2 entradas

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.