Contenedores en el puerto
¡Hola!
Al parecer, uno de los problemas que ha causado el incremento en el coste en el Canal de Panamá no se debe a dificultades en la construcción, sino a dificultades logísticas. Junto al canal se debe construir un gran puerto marítimo de carga, al que llegan por un lado los camiones con los contenedores que deben ser embarcados, y por otro los barcos donde éstos deben ser estibados. Por mucho que lo han pensado, los constructores no son capaces de ponerse de acuerdo en la mejor forma de organizar esta tarea.
Usando unas gigantescas grúas, los contenedores se van depositando por orden de llegada unos encima de otros en pilas de altura arbitraria. Una vez que todos los contenedores del día han sido apilados en el puerto, la grúa comienza a cargar los buques. Cada contenedor debe ser estibado en un barco concreto, conocido de antemano. Además, los barcos son cargados en un orden específico, y no se puede comenzar a cargar uno hasta que todos los anteriores han salido rumbo a su destino.
Como los contenedores se van apilando en el puerto según llegan en los camiones, es importante la forma en la que se organizan para que luego se puedan ir retirando de las pilas según se cargan los barcos sin tener que quitar de encima los contenedores que estorban. Por ejemplo, supongamos que tenemos tres barcos, A, B y C, que deben ser cargados en ese orden. Por la mañana, nos van llegando camiones con contenedores; supongamos que los tres primeros camiones traen cada uno un contenedor para el barco C, luego llegan tres con contenedores para el barco B y finalmente nos llegan tres contenedores para el barco A. Esto lo representaremos como CCCBBBAAA. Con esta configuración, podemos ir colocando todos los contenedores según nos van llegando uno encima de otro, y luego irlos cogiendo también por orden para cargar los barcos. Como en la parte superior de la pila de contenedores están los últimos contenedores que se pusieron, sacaremos primero los contenedores para el barco A, luego los del barco B y finalmente los del C. Por tanto, únicamente necesitaremos una pila de contenedores para cargar los barcos sin problema.
Sin embargo, si los contenedores nos llegaran en el orden CBACBACBA no podríamos usar una única pila de contenedores, porque para conseguir los tres contenedores destinados al primer barco (el A) tendríamos que retirar de la pila los contenedores C y B que nos estorban. Necesitaríamos 3 pilas diferentes, por ejemplo una para los contenedores A, otra para los B y una última para los C.
¿Cuál es el mínimo número de pilas de contenedores que necesitamos organizar en el puerto para que la carga de los barcos sea rápida si los contenedores que nos llegan son CBACBA? Si ampliamos el número de barcos a todas las letras del abecedario, y consideramos que debemos cargar los barcos en orden alfabético, ¿cuál es el número de pilas mínimo en el puerto para la llegada de los contenedores ACERTIJO o PROGRAMAME? Y ya que estamos… ¿y MUCHOPORPROGRAMAR? 🙂
Como siempre si das con la solución y sabes programar, puedes probar tu implementación aquí. Si consigues que te funcione ¡cuéntanoslo!
¡Hasta el domingo!
Mucho por Programar 
Buenos y programables días,
Aquí os traigo una posible solución:
CBACBA -> 2 pilas
ACERTIJO -> 6 pilas
PROGRAMAME -> 2 pilas
MUCHOPORPROGRAMAR -> 5 pilas
Dejo mi algoritmo: http://www.codeskulptor.org/#user28_jinUUM6FMXmtF5E.py
no voy a publicar mi respuesta por que es la misma que la que a dado david y no hace falta repetir las cosas XD.
Hoola
Yo también coincido con David. Por poner algo nuevo 🙂 La palabra «SUPERCALIFRAGILISTICOESPIALIDOSO» me sale que necesita 8 pilas.
Por cierto, como solo hay que dar el número de pilas, no hace falta guardar el estado completo (como hacía David), sino que basta quedarse con lo que hay en la cima.
En mi solución para evitar el bucle (lineal) de David, mantengo el vector (de cimas) ordenado para usar búsqueda binaria 🙂
Un vector de cimas es un HEAP? Mi array está siempre ordenado también.. No entiendo muy bien a que te refieres. Puedes ponerme el algoritmo o algo.
Salu2 =)
Hola,
No me expliqué bien 🙂 Si entendí bien tu solución, tu guardas un array de arrays (un array de pilas). Pero luego en cada vuelta (para cada container), únicamente miras la última posición de cada array (es decir, la cima de cada pila). Dado que de cada pila sólo te interesa la cima, puedes «tirar» el resto. Así, solo necesitas un array de caracteres. Cada entrada del array representa una pila y se guarda únicamente el contenedor superior.
Por otro lado, lo que tú haces es, para un contenedor dado, mirar en qué pila se puede poner, comparando la letra con la letra de la cima de cada pila hasta encontrar uno que valga.
Esa búsqueda es lineal, es decir, en el peor de los casos tienes que comprobar recorrer el array completo.
La solución para evitar ese bucle lineal es hacer que ese vector en el que se guardan las cimas de todas las pilas utilizadas se mantenga ordenado alfabéticamente. De esa forma, utilizando búsqueda binaria es rápido encontrar, dado un nuevo contenedor, en qué pila se podría añadir.
El código lo tengo en C++. Si cuando publiquen la solución no ponen uno los autores del blog, pongo el mío en los comentarios. Aunque como usa la librería de C++, es bastante críptico, la verdad.