Skip to content

Solución: Astérix y el escudo arverno

by en 15/12/2013

¡Bienvenidos otra vez!

Tras una semana de exámenes, y oliendo ya la Navidad, ha llegado la hora de desvelar la solución al acertijo que os propusimos el lunes.

Esta vez nos desplazamos, de la mano de Astérix,  a Gergovia, un antiguo pueblo de la Galia. Allí, os contábamos, tienen una larga calle de comercios dedicados al vino, que todas las mañanas deciden cuánto vino quieren vender (o comprar) a otros comercios de su misma calle. Como todos venden el mismo tipo de vino, se quiere minimizar el trabajo dedicado a transportarlo de unos comercios a otros, y os preguntábamos cuál era el mínimo número de litros de vino que había que transportar sabiendo que el transporte de cada litro de vino se contaba de manera reiterada en cada desplazamiento desde un comercio al siguiente.

En esta ocasión la respuesta tardó en llegar, y lo hizo de nuestro fiel lector David que, no sólo se atrevió a dar su solución, sino que nos envió el código en Python con el que lo resolvió. Como es habitual en él ¡acertó! De manera que nuestras sinceras felicitaciones para él 🙂 Esta semana el acertijo era, quizá, un poquito más difícil que otras veces. Sin embargo nos gusta mucho porque la programación es bastante sencilla, a la vez que bastante críptica si no se entiende la lógica que hay detrás. Para todos aquellos que no habéis dado con la solución, o que habéis mirado el código de David y no habéis entendido la lógica que tiene detrás, vamos con la explicación.

Os contábamos que, para simplificar la escritura de cada punto de partida, pondríamos una serie de números indicando la cantidad de litros que cada comerciante desea comprar (con un número positivo) o vender (un número negativo). El ejemplo que os pusimos era la secuencia:

5 -4 1 -3 1

En el acertijo, la suma siempre será cero, coincidiendo así la oferta y la demanda. En este caso el primer comerciante (el de la izquierda) desea comprar 5 litros. Para ahorrar transporte, es mejor comprárselos a la persona que tenga más cerca, de manera que le compra los 4 litros que tiene a la venta el segundo. El litro que le falta debe comprárselo, irremediablemente, al cuarto comerciante (el que vende 3). Por tanto, la compra del vino del primer comerciante supone desplazar 4 + 3 × 1 litros, es decir 7 (hay un litro que pasa por tres comerciantes, por eso cuenta por tres). Los comerciantes tercero y quinto compran el litro que quieren al cuarto, que es el que tienen cerca, por lo que se suman dos desplazamientos más. El número total de desplazamientos es, por tanto, de 9 libros.

Fijaos que el tercer comerciante podría haber comprado su litro de vino al segundo (el que vende 4), pero en ese caso, el primero habría tenido que comprarle un litro más al cuarto, lo que sería a todas luces más ineficiente, por lo que no es la solución óptima.

En la explicación anterior hemos planteado dos formas de realizar las compra-venta de vino, y luego nos hemos quedado con la más óptima en número de litros transportados. Pero tener que buscar todas las posibilidades (de hecho en el ejemplo hay más que ni siquiera hemos considerado) para luego quedarnos con la menos costosa es muy laborioso, horriblemente lento cuando hay un número de comerciantes mínimamente alto, y muy propenso a errores. Además es difícil de programar y, sobre todo, muy aburrido para hacerlo a mano y, como sabéis, tratamos de poner acertijos que, aunque se puedan programar, también se puedan resolver sin la ayuda de un ordenador. Por tanto tenemos que destilar de nuestro ejemplo anterior una manera sistemática y sencilla de resolverlo que resulte fácil de realizar a mano.

Para explicarla, vamos con la primera pregunta que os hacíamos, que tiene más comerciantes que la de ejemplo. Para que sea luego más fácil referirnos a ellos, vamos a numerarlos:

1 2 3 4 5 6 7 8 9 10
-100 -200 -300 -400 -500 500 400 300 200 100

En este caso vemos que el primer comerciante desea vender 100 litros (el valor es negativo). Al estar en el lateral izquierdo, no tiene otra opción que vender sus 100 litros a alguien que esté a su derecha. Por tanto sus 100 litros, irremediablemente, tendrán que desplazarse al comerciante número 2, aunque no los quiera comprar. Podemos verlo como si el segundo comerciante comprara todos los litros al primero, y asumiera la responsabilidad de venderlos él mismo a alguien de su derecha. El resultado es que los 100 litros de excedente que tenía el comerciante número 1 se han desplazado, por lo que tenemos 100 litros movidos. La nueva situación es esta:

1 2 3 4 5 6 7 8 9 10 Despl.
-100 -200 -300 -400 -500 500 400 300 200 100
-300 -300 -400 -500 500 400 300 200 100 100

En la tabla, hemos puesto la situación inicial, antes de empezar a mover litros de vino, y la final después de que el comerciante número uno vendiera sus 100 litros. Ahora es el segundo comerciante el que se encuentra con 300 litros de vino por vender, y la única opción es que los venda hacia la derecha, porque su vecino de la izquierda ha completado el trabajo por hoy. Por tanto, “vende” todo su excedente al tercer comerciante, que se encuentra con un montón de vino, y, de manera global, hay 300 litros más que hemos desplazado:

1 2 3 4 5 6 7 8 9 10 Despl.
-100 -200 -300 -400 -500 500 400 300 200 100
-300 -300 -400 -500 500 400 300 200 100 100
-600 -400 -500 500 400 300 200 100 400

El tercer y cuarto comerciantes hacen lo mismo, asumir las ventas de sus vecinos de la izquierda y quedarse con sus litros de vino, acumulando el desplazamiento total:

1 2 3 4 5 6 7 8 9 10 Despl.
-100 -200 -300 -400 -500 500 400 300 200 100
-300 -300 -400 -500 500 400 300 200 100 100
-600 -400 -500 500 400 300 200 100 400
-1000 -500 500 400 300 200 100 1000
-1500 500 400 300 200 100 2000

Llegados a este punto se produce un cambio, pues el sexto comerciante quiere comprar vino, no venderlo. El quinto comerciante no tiene otra opción que venderle sus 1500 litros de vino, que, obviamente, se sumarán al desplazamiento total. Pero en esta ocasión, el comerciante número 6 se quedará con 500 de esos litros, por lo que únicamente deberá vender 1000 a sus vecinos de la derecha:

1 2 3 4 5 6 7 8 9 10 Despl.
-100 -200 -300 -400 -500 500 400 300 200 100
-300 -300 -400 -500 500 400 300 200 100 100
-600 -400 -500 500 400 300 200 100 400
-1000 -500 500 400 300 200 100 1000
-1500 500 400 300 200 100 2000
-1000 400 300 200 100 3500

Con el resto de comerciantes ocurre lo mismo; cogen todo el vino sobrante de su vecino de la izquierda (que suma al desplazamiento total), pero se quedan con una parte, por lo que cada vez tienen que vender menos hacia la derecha y el número de litros de vino que siguen su camino desciende. Fijaos que, curiosamente, con este procedimiento da igual de dónde venga el vino que se queda cada comprador.

Si completamos el proceso, la tabla queda:

1 2 3 4 5 6 7 8 9 10 Despl.
-100 -200 -300 -400 -500 500 400 300 200 100
-300 -300 -400 -500 500 400 300 200 100 100
-600 -400 -500 500 400 300 200 100 400
-1000 -500 500 400 300 200 100 1000
-1500 500 400 300 200 100 2000
-1000 400 300 200 100 3500
-600 300 200 100 4500
-300 200 100 5100
-100 100 5400
0 5500

Vemos que el número final de litros transportados es de 5.500, tal y como nos dijo David.

Vamos con la segunda pregunta, que tiene una pequeña vuelta de tuerca:

1 2 3 4 5 6 7 8 9 10
100 200 300 400 500 -100 -200 -300 -400 -500

En este caso el primer comerciante quiere comprar vino, no venderlo. Por tanto no podemos decir que haya vino que se traslade de la izquierda hacia la derecha (del primero al segundo) como cómodamente decíamos en el primer ejemplo. En este caso la única opción es que el segundo comerciante venda vino al primero. Pero el segundo comerciante no puede venderle nada, dado que él mismo quiere comprar… ¿cómo resolvemos esto?

Lo que tenemos que hacer es “pensar hacia delante”. Es verdad que el segundo comerciante no puede venderle vino… ahora mismo. Pero para que el primer comerciante vea cubierta su necesidad de compra, irremediablemente tendremos que transportar vino desde el segundo comerciante hacia el primero, vino que tendrá que haber llegado de la derecha. Lo que hacemos es “simular” que el segundo comerciante asume las compras del primero y, cuando las tenga, le dará su vino, incrementando el desplazamiento total. Es decir, para que el primer comerciante tenga sus 100 litros de vino, tendremos que haberlo transportado irremediablemente desde el segundo comerciante hacia el primero, y el segundo comerciante tendrá que haber comprado no sus 200 litros, sino 300:

1 2 3 4 5 6 7 8 9 10 Despl
100 200 300 400 500 -100 -200 -300 -400 -500
300 300 400 500 -100 -200 -300 -400 -500 100

Con los siguientes comerciantes ocurre lo mismo: asumen la responsabilidad de las compras de sus vecinos de la izquierda, igual que en la primera pregunta que os hacíamos asumían la de las ventas. El resultado es:

1 2 3 4 5 6 7 8 9 10 Despl
100 200 300 400 500 -100 -200 -300 -400 -500
300 300 400 500 -100 -200 -300 -400 -500 100
600 400 500 -100 -200 -300 -400 -500 400
1000 500 -100 -200 -300 -400 -500 1000
1500 -100 -200 -300 -400 -500 2000

Llegados a este punto, el quinto comerciante se ve en la necesidad de adquirir 1500 litros de vino. De esos 1500, 100 serán cubiertos por el sexto, pero éste debe asumir la responsabilidad de conseguir los 1400 restantes. Por tanto, el proceso continúa siendo el mismo:

1 2 3 4 5 6 7 8 9 10 Despl
100 200 300 400 500 -100 -200 -300 -400 -500
300 300 400 500 -100 -200 -300 -400 -500 100
600 400 500 -100 -200 -300 -400 -500 400
1000 500 -100 -200 -300 -400 -500 1000
1500 -100 -200 -300 -400 -500 2000
1400 -200 -300 -400 -500 3500
1200 -300 -400 -500 4900
900 -400 -500 6100
-500 -500 7000
0 7500

Y llegamos a los 7500 litros desplazados, tal y como también nos adelantó David.

Si recapitulamos, el proceso que seguimos es sencillo. Siempre llevamos la cuenta de los litros de vino que acumula el “comerciante actual”, ya sea para vender o para comprar gracias al signo. Todo ese vino, en valor absoluto, debe ser trasladado hacia la derecha, por lo que se suma al desplazamiento acumulado que será nuestro resultado. Además, el siguiente comerciante asume la responsabilidad de tratar con el vino del de su izquierda, por lo que la siguiente cantidad de vino a procesar será la suma de lo acumulado hasta ahora, más el del nuevo comerciante. El uso del signo hace que entren en juego las compras y las ventas, y el valor absoluto a la hora de sumar los desplazamientos totales hace que ignoremos si el vino se desplaza realmente del comerciante actual hacia el de la derecha, o del comerciante de la derecha hacia el actual. Lo importante es que se desplaza 🙂

La última pregunta era un poco más larga, al tener 15 comerciantes (-1 -2 -3 -4 5 -6 7 -8 9 -10 11 -12 13 -14 15) pero el proceso para resolverlo es exactamente el mismo. Si hacéis la tabla, llegaréis al resultado correcto, 100 litros desplazados.

Si os gusta programar, podéis, como siempre, probar vuestra solución aquí. El juez on-line no soporta Python, por lo que tendréis que programarlo en Pascal, C, C++ o Java. Pero con la explicación y con la ayuda del código de David, ¡lo tenéis chupado! 🙂

¡Hasta el próximo!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: