Descomposición
Seguí leyendo
Enterate del próximo post
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Organizar una mudanza es, en apariencia, una sola tarea. En la práctica nadie la encara así: se separa en embalar la cocina, embalar el placard, desarmar los muebles grandes y contratar el flete. Cada una de esas tareas se resuelve por separado -embalar la cocina no depende de cómo se resuelva el flete- y ninguna, por sí sola, es tan grande como la mudanza completa. Eso es descomposición, aplicada sin necesidad de nombrarla.
El post anterior mostró cómo separar, dentro de un enunciado, los datos de entrada, el dato de salida y las restricciones. Ese análisis funciona bien mientras el problema entero cabe en una sola lectura. Cuando no cabe -cuando tiene varias partes que conviene resolver por separado- hace falta un paso más: decidir en qué partes se corta, y cómo se combinan sus resultados.
Descomponer un problema es partirlo en problemas más chicos, cada uno con su propia entrada y su propia salida, que se puedan resolver por separado y combinar después en una solución del problema original.
La razón para hacerlo es práctica: un problema grande es difícil de sostener completo en la cabeza a la vez -cuántos datos entran, qué pasa con cada uno, en qué orden-, mientras que un problema chico, con una entrada y una salida bien definidas, se resuelve, se revisa y se corrige sin tener que pensar en el resto.
No cualquier corte sirve. Una buena descomposición cumple tres cosas:
Cuando una de las partes sigue siendo demasiado grande para resolverla de un tirón, se aplica la misma idea otra vez, sobre esa parte. Descomponer no es una operación que se hace una sola vez: se repite hasta que cada pieza es chica.
El siguiente problema tiene tres costos que sumar, cada uno calculado con datos distintos: el costo de organizar un cumpleaños simple, a partir de la cantidad de invitados, el gasto de comida por persona, el precio de la torta y la cantidad y el precio de los globos.
Antes de escribir un único algoritmo largo, conviene separar el problema en sus partes: el costo de la comida depende solo de los invitados y el gasto por persona; el costo de los globos depende solo de la cantidad y el precio unitario; la torta es un valor fijo que no necesita ningún cálculo propio. Cada una de esas partes se escribe como su propio algoritmo, con su propia entrada y su propia salida.
algoritmo costo_comida(personas, costo_por_persona):
multiplicar personas por costo_por_persona
devolver el resultadoalgoritmo costo_globos(cantidad_globos, precio_unidad):
multiplicar cantidad_globos por precio_unidad
devolver el resultadoCon las dos partes resueltas, el algoritmo principal no vuelve a calcular nada: se limita a pedirles el resultado a los dos algoritmos anteriores y a sumarlos junto con el costo de la torta.
algoritmo costo_cumpleanos(personas, costo_por_persona, costo_torta, cantidad_globos, precio_unidad):
llamar a costo_comida con personas y costo_por_persona para obtener la comida
llamar a costo_globos con cantidad_globos y precio_unidad para obtener los globos
sumar la comida, costo_torta y los globos
devolver el resultadoCon 12 invitados, un gasto de comida de $1500 por persona, una torta de $8000 y 30 globos a $100 cada uno: la comida cuesta $18000, los globos $3000, y el total es $29000.
Ninguna de las tres partes necesitó saber nada de las otras dos. costo_comida no sabe que existen los globos, y costo_globos no sabe que existe la comida; el único lugar donde las tres piezas se juntan es costo_cumpleanos, y ahí el trabajo es apenas sumar. Si más adelante cambia cómo se calcula el costo de los globos -por ejemplo, un descuento a partir de cierta cantidad- alcanza con modificar costo_globos, sin tocar ni costo_comida ni el algoritmo principal.
Calcular el costo de pintar una habitación, a partir de cuántos litros de pintura hacen falta, el precio del litro, cuántas horas estima llevar el trabajo y el precio de la hora de mano de obra.
Pista: son dos costos que no dependen uno del otro -el de la pintura y el de la mano de obra-, así que conviene resolverlos como dos algoritmos separados antes de escribir el que los combina. Preguntarse, para cada uno: ¿qué datos necesita, y qué necesita devolver, sin que le importe cómo se resuelve el otro?
algoritmo costo_pintura(litros, precio_litro):
multiplicar litros por precio_litro
devolver el resultadoalgoritmo costo_mano_obra(horas, precio_hora):
multiplicar horas por precio_hora
devolver el resultadoalgoritmo costo_pintar_habitacion(litros, precio_litro, horas, precio_hora):
llamar a costo_pintura con litros y precio_litro para obtener la pintura
llamar a costo_mano_obra con horas y precio_hora para obtener la mano de obra
sumar la pintura y la mano de obra
devolver el resultadoCon 3 litros a $2500 cada uno y 4 horas a $3000 cada una: la pintura cuesta $7500, la mano de obra $12000, y el total es $19500. La misma estructura de tres algoritmos del ejemplo anterior -dos partes independientes y uno que las combina- funciona igual acá, aunque el problema sea distinto.
Una excursión de un día para un grupo de personas se organiza en un colectivo con capacidad limitada, con entrada paga al lugar que se visita y un almuerzo incluido por persona. Calcular el costo total de la excursión.
Pista: hay tres costos que sumar, y uno de ellos -el transporte- no depende directamente de la cantidad de personas sino de cuántos colectivos hacen falta para llevarlas a todas. Ese cálculo ya apareció en el post anterior con otro propósito: dividir y redondear hacia arriba, porque un colectivo incompleto sigue siendo un colectivo entero.
algoritmo costo_transporte(personas, capacidad_colectivo, precio_colectivo):
dividir personas por capacidad_colectivo
redondear ese resultado hacia arriba para obtener la cantidad de colectivos
multiplicar la cantidad de colectivos por precio_colectivo
devolver el resultadoalgoritmo costo_entradas(personas, precio_entrada):
multiplicar personas por precio_entrada
devolver el resultadoalgoritmo costo_almuerzo(personas, precio_almuerzo):
multiplicar personas por precio_almuerzo
devolver el resultadoalgoritmo costo_excursion(personas, capacidad_colectivo, precio_colectivo, precio_entrada, precio_almuerzo):
llamar a costo_transporte con personas, capacidad_colectivo y precio_colectivo para obtener el transporte
llamar a costo_entradas con personas y precio_entrada para obtener las entradas
llamar a costo_almuerzo con personas y precio_almuerzo para obtener el almuerzo
sumar el transporte, las entradas y el almuerzo
devolver el resultadoCon 47 personas, colectivos con capacidad para 45, a $90000 cada uno, entradas a $1200 y almuerzo a $2500 por persona: hacen falta 2 colectivos (47 dividido 45 redondeado hacia arriba), el transporte cuesta $180000, las entradas $56400, el almuerzo $117500, y el total es $353900. Cuatro algoritmos chicos, ninguno más complicado que una multiplicación o una división, resuelven un problema que, escrito de un tirón, mezclaría cinco datos de entrada distintos en una sola cuenta larga.
Descomponer un problema es partirlo en partes que tengan su propia entrada y su propia salida, se puedan resolver sin mirar las demás, y se combinen con un paso simple. No es una técnica reservada para problemas complicados: es la forma de que un problema grande deje de sentirse grande, aunque nada de su dificultad real haya desaparecido.
Las partes de este post -comida y globos, pintura y mano de obra, transporte, entradas y almuerzo- se ejecutaban siempre en el mismo orden y ninguna dependía del resultado de otra antes de empezar. Eso no es casualidad: es una simplificación para presentar la idea con claridad. El próximo paso de la serie trata qué pasa cuando el orden en el que se ejecutan los pasos sí importa, incluso dentro de partes ya bien separadas.