Tuercas y Tornillos
Descripción
En la fábrica de Construcciones Castor, Benito trabaja en la línea de ensamblaje de tuercas y tornillos.
Benito se coloca al final de una banda que transporta una líena de tornillos y tuercas, y toma cada elemento en orden de izquierda a derecha. Si toma una tuerca, la coloca en la cubeta a su lado. Si toma un tornillo, toma una tuerca de la cubeta, la coloca en el tornillo y pone la pieza ensamblada en la caja.
Hay dos casos en que Benito está en problemas: si toma un tornillo y no hay una tuerca en la cubeta par aensamblaro; o si termina la banda y todavía quedan tuercas en la cubeta.
Pregunta
¿En cuál de estos casos TODO sale bien?
Ver soluciónOcultar solución
Solución
La respuesta correcta es C. Se puede comprobar recorriendo cada secuencia de izquierda a derecha y llevando la cuenta de las tuercas que hay en la cubeta. Cada tuerca agrega una a la cubeta y cada tornillo necesita retirar una. La cantidad nunca puede bajar de cero y al final debe quedar exactamente en cero. En A aparece un tornillo cuando ya no hay tuercas disponibles; en B ocurre lo mismo más adelante; y en D sobran dos tuercas al terminar. Sólo C cumple las dos condiciones.
La informática detrás del desafío
La cubeta se comporta como una memoria donde se guardan elementos mientras se procesa una secuencia. La fuente original relaciona la tarea con los autómatas de pila (push-down automata): modelos que toman decisiones según el símbolo actual y una memoria organizada como pila. También compara tuercas y tornillos con paréntesis balanceados: una tuerca puede verse como un paréntesis que abre y un tornillo como uno que cierra. Comprobar que una secuencia de paréntesis está bien formada es importante al analizar lenguajes y programas.
Para el aula
Prepara tarjetas con N para tuerca y T para tornillo y usa un vaso como cubeta. Construye distintas secuencias y procésalas de izquierda a derecha: N agrega una ficha al vaso y T debe retirar una. Decide cuáles secuencias son válidas. Después inventa una secuencia que falle a la mitad y otra que termine con fichas sobrantes.
Recursos del desafío
