Skip to content
Tags

,

Solución: salvemos al lince ibérico

by en 08/06/2014

Hola!

Vamos, un domingo más, con la respuesta del acertijo de la semana. En él, os hablábamos de una carretera que cruza el territorio del lince ibérico, en peligro de extinción. Para evitar atropellos, se pusieron vallas en varios tramos. Sin embargo, los linces seguían cruzando la carretera por los tramos no vallados de modo que se ha decidido hacer pequeños túneles o “pasos de fauna”. Se sabe que uno de estos túneles cubre tres tramos, es decir se estima que un lince no cruzará una carretera por la superficie si hay un paso subterráneo en el tramo en el que está o en alguno de los tramos adyacentes. Las preguntas que os hacíamos era cuál es el mínimo número de túneles que hay que hacer para evitar atropellos en diferentes configuraciones de carretera.

Este acertijo surge de uno de los problemas que se pusieron en los regionales de Madrid y Reus de ProgramaMe, y está publicado en ¡Acepta el reto!. Aunque nadie ha puesto su solución en los comentarios, ha habido varias personas que han resuelto el problema en la última semana, de modo que ¡enhorabuena a todos ellos! La próxima vez no seáis tan tímidos, y contarnos vuestra solución aquí 🙂

Vamos con la nuestra. La primera pregunta que os hacíamos era relativa a una carretera con la configuración .... que significa que tiene cuatro tramos, y ninguna valla. Dado que cada túnel cubre tres tramos, es imprescindible hacer dos túneles. Hay varias posiciones válidas para ellos (por ejemplo, si los marcamos con una t podríamos hacerlo t..t, t.t., .tt. o .t.t), pero es imposible evitar el cruce en todos los tramos con un único túnel.

La siguiente pregunta era ..X...X, donde una X representa una valla. En este caso necesitamos un túnel para el primer bloque sin vallas, y un segundo túnel para el segundo. Una configuración podría ser t.X.t.X. Observa que todos los tramos tienen o bien un túnel o valla, o un túnel adyacente.

La última pregunta era un poco más larga, X.XXX....X.X.X. Para cubrir el primer tramo sin valla necesitamos un túnel. La parte más interesante de esta pregunta es darse cuenta de que podemos poner túnel debajo de vallas lo que en este caso nos ahorrará túneles. En concreto, basta con 4 túneles; aunque hay varias formas de conseguirlo, una sería XtXXX.t..T.XtX donde T representa un tramo con túnel y valla.

Todas estas respuestas se pueden deducir con relativa facilidad gracias al sentido común, el problema es cómo programarlo 🙂 Para eso, basta con ir colocando túneles al ir recorriendo los tramos de carretera. En concreto, cuando nos planteamos qué hacer al llegar al tramo i asumiremos que todos los tramos anteriores están ya resueltos (y los linces no cruzarán la carretera por ellos). Si el tramo i tiene valla, entonces no hay nada de lo que preocuparse y pasamos al siguiente. Si no la tiene, entonces colocaremos un túnel en el tramo siguiente (es decir en i+1). Ese túnel cubrirá al tramo actual y a los dos siguientes, a si es que, independientemente de si esos dos tienen valla o no, nos los saltamos sin preocuparnos de ellos, y seguimos buscando. Fíjate que colocar el túnel en el tramo siguiente hace que se aproveche lo más posible. Si lo colocáramos en la posición i (la actual), el túnel estaría cubriendo también el tramo anterior, i-1, que, hemos dicho, estamos suponiendo que ya no será cruzado por ningún lince por nuestros túneles anteriores. Por tanto desaprovecharíamos un poco nuestro túnel recién puesto y la solución podría no ser la óptima.

Surge la pregunta de qué pasa al final de la carretera. Si tenemos una carretera XXX. en nuestra simulación colocaríamos un túnel más allá del final. En realidad la posición exacta de los túneles no nos la preguntan, sólo el número. Lo importante es que aquí necesitamos un único túnel, y eso es justo lo que nuestro algoritmo contestaría 🙂

Esta solución pertenece a la familia de los algoritmos voraces, que ya son viejos conocidos nuestros (sin ir más lejos, usamos uno en el acertijo anterior). En ellos, tomamos una decisión “local” (colocar o no un túnel) sin preocuparnos del problema completo, sólo de una pequeña parte (el tramo actual, no la configuración de toda la carretera). Además, tampoco nos replanteamos en ningún momento las decisiones tomadas por si resultaron no ser una buena idea. Aunque no siempre dan la solución óptima, en el caso del acertijo que nos ocupa sí lo hace, y de una manera muy sencilla de programar por lo que ¡nos lo quedamos!

Como siempre, si quieres programar tu solución y probarla, puedes hacerlo aquí.

¡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: