Solución Desafío 40+6: La gota de aceite


Escribe Divagante:

Bueno. Otro desafio terminado. Ha habido 13 respuestas, todas ellas acertadas. 3353 caminos. Como habeis visto todos, el mejor camino ha sido  el manual, como dice superpanzeta “La manera más simple de contar los caminos distintos que llegan a un vértice de una cuadrícula, es empezar contando los caminos que llegan a otros vértices más sencillos, es decir, los más próximos al inicio, e ir anotando la cantidad de caminos que llegan a ellos.”
 Os adjunto su solución por que se parece mucho a la que habia preparado yo pero en fino y ademas fue la primera que recibí.
El resto han sido básicamente variaciones de lo mismo, de arriba a abajo o de abajo a arriba. casi todos altamente elaborados y trabajados.
Como dice pardillano, es una función exponencial con un término general que se aproxima a D(N) = 0,47168579 * 4,39025688 ^ N para N igual al número de filas de la rejilla.
A continuación incluyo las soluciones que habéis aportado en fichero adjunto.
Gracias a todos y a por el próximo.
SOLUCIONES:
Esta semana me ha sido imposible conectarme. El jueves Jabon ataca de nuevo.

15 comentarios

Archivado bajo OTROS

15 Respuestas a “Solución Desafío 40+6: La gota de aceite

  1. jabon

    Muy bien Divagante.
    De paso animaros a que presentéis desafíos, veo que hay poca reserva porque el siguiente lo envié hace poco.
    Se trata de un desafío fácil. Lo de original es prácticamente imposible, está basado en uno que conocí hace unos 30 años.
    Y estoy trabajando en uno que tengo casi ultimado, que me ha llevado bastante tiempo. Es de los que pueden entretener un ratito. Ese será para otra semana, pero me gustaría que alguien más se sume a esta iniciativa.

  2. Muy cierto jabon, el tuyo es, de momento, el último. Yo tengo la intención de presentar alguno, pero mi situación familiar últimamente no me permite un respiro… todo se andará.

    • Superpanzeta

      Bueno, ya que nos quedamos sin munición, voy a mandar un desafío original mío, que muy probablemente va a ser:
      1-Fácil en parte, aunque espero que no todo el mundo acierte.
      2-Feo, o por lo menos extraño.
      3-Malo en definitiva.
      No me termina de convencer, pero oye, es para pasar el rato y pensar un poco en cosas diferentes a las habituales.

      • Superpanzeta

        Hecho.
        Acabo de enviarlo y ya me estoy arrepintiendo. Qué vergüenza…
        Espero que no me odiéis por esto.

        Santi, ánimo con la vida real. Y no tengas prisa. Así no tendrás que sufrir mi desafío.

  3. Maito

    Volviendo al aceite, en la versión sin diagonales llegamos al triángulo de Tartaglia (o Pascal), que es analizado de forma amena en el libro “El diablo de los números”, aunque el estudio del Triángulo de Divagante creo que es digno de la Medalla Fields.
    Me pongo como loco a busvcar un desafío, esto no puede parar.

    • Superpanzeta

      Sí, lo del triángulo es sorprendente. Yo ya conocía la forma de sumar los caminos en la versión clásica (que después de todo es la misma forma que en este desafío), pero no que en ella salieran los coeficientes binomiales, y por tanto que se pudieran calcular sin sumar los anteriores.
      Si las rejillas sin diagonales que había visto hubieran sido suficientemente grandes (y cuadradas) me habría saltado a la vista, pero siempre había visto retículas pequeñas y estrechas, y los coeficientes me pasaron desapercibidos.

  4. Superpanzeta

    Rogelio, ¿cómo es que no has respondido al desafío?

    Bueno, te prometí que te enseñaría mi programa para sumar los caminos. Te pongo dos versiones ligeramente distintas (que he comentado un poco). Espero que el WordPress no descoloque el código.

    Esta primera versión mantiene toda la rejilla en memoria, y por lo tanto tiene un límite de almacenamiento que depende de la RAM disponible.
    Aún así, con 4Gb de RAM permite llegar sin problemas a rejillas como la de 2012*2014. Las rejillas mayores, como 3000*3000 no caben.

    def suma_rejilla1(columnas,filas):
    rejilla=[]#Simularemos la rejilla con una lista de listas
    for f in xrange(filas+1):#Hay una fila más que cuadrados tiene la rejilla
    fila = []
    for c in xrange(columnas+3):#Hay una columna más que cuadrados tiene la rejilla, y además hacemos la rejilla más ancha de la cuenta, con una columna de 0 extra a la izquierda y otra a la derecha
    fila.append(0)#Se inicializa todo a 0
    rejilla.append(fila)
    for c in xrange(1,columnas+2):
    rejilla[0][c]=1#Ponemos a 1 la fila de arriba para empezar
    for f in xrange(1,filas+1):#Nos saltamos la fila de “1” de arriba y vamos de arriba a abajo…
    for c in xrange(columnas+1,0,-1):#… y de derecha a izquierda, ya que el aceite viene desde arriba a a derecha.
    rejilla[f][c]=rejilla[f][c+1]+rejilla[f-1][c]+rejilla[f-1][c-1]#Vamos sumando las tres casillas que hay “encima”
    return rejilla[filas][1]#El resultado final es la casilla de abajo a la izquierda, sin contar la columna extra

    Y esta es mi versión “mejorada” que sólo mantiene en memoria 2 filas de la rejilla, así que la única limitación es la RAM necesaria para almacenar los dígitos que se producen.
    Es algo más lenta porque tiene que mover la fila sumada cada vez. Eso sí, el límite es mucho mayor al anterior, si tienes la paciencia para esperar el resultado.

    def suma_rejilla2(columnas,filas):
    rejilla=[]#Simularemos la rejilla con una lista de 2 listas
    for f in xrange(2):
    fila = []
    for c in xrange(columnas+3):#Hay una columna más que cuadrados tiene la rejilla, y además hacemos la rejilla más ancha de la cuenta, con una columna de 0 extra a la izquierda y otra a la derecha
    fila.append(0)#Se inicializa todo a 0
    rejilla.append(fila)
    for c in xrange(1,columnas+2):
    rejilla[0][c]=1#Ponemos a 1 la fila de arriba para empezar
    for f in xrange(filas):
    for c in xrange(columnas+1,0,-1):#vamos de derecha a izquierda, ya que el aceite viene desde la derecha.
    rejilla[1][c]=rejilla[1][c+1]+rejilla[0][c]+rejilla[0][c-1]#Vamos sumando las tres casillas que hay “encima”
    rejilla[0]=rejilla[1]#subimos la fila de abajo a la posición de arriba
    return rejilla[1][1]#El resultado final es la casilla de abajo a la izquierda, sin contar la columna extra

    Como verás, nada especial. Hace lo mismo que hago yo a mano.
    Agrando la rejilla con dos columnas de 0 para poder usar siempre la misma suma de tres casillas.

    Con la última versión he probado por ejemplo 7*100000 (muchas sumas y un resultado “astronómico” de 72796 dígitos), que acaba en 9 (impar) porque 100000= (11111*(7+2))+1

    También he probado 10000*10000 (un número “astronómico” de sumas, y un resultado grande): 10447 dígitos y acaba en 4.

    • Superpanzeta

      Me lo imaginaba, el Worpress se ha merendado las indentaciones.
      Bueno, si sigues interesado, dame un e-mail y te lo mando.
      O se lo mando a Santi para que lo cuelgue ahí arriba junto a mi respuesta.

    • Rogelio

      Muchisimas gracias SuperpanZ!!!
      si que respondi pero con un laconico:

      1 2 6 22 89 377
      1 4 16 67 288 1253
      1 6 29 132 588 2597
      1 7 36 168 756 3353
      (que ya es suficiente para deducir cuando n*m tendra par o impar numero de caminos, si nos fijamos en la “diagonal” de impares 7-29-67-89 y vuelta a columna de impares como la inicial de 1s).

      El codigo se entiende perfectamente, muchas gracias. Lo que no entiendo es porque a mi me peta… sera mi RAM? o sera porque defini los enteros como long(), no veo que tu lo hagas. Bueno probare un poco mas. Seguramente es la RAM porque almacenaba toda la rejilla.
      Asi que enhorabuena por la optimizacion que haces, muy acertada!
      Gracias tambien por los comentarios y el 7*100000 !! Caramba!!

      Hasta el proximo!
      ooops! hay crisis de desafios! a ver que se puede hacer…

      • Superpanzeta

        De nada, hombre.

        Pues no, nunca hasta ahora he definido los long y me ha ido bien, pero yo uso la versión 2.7 o la 3.
        Si por “petar” entiendes que los enteros se pasen de vueltas y se conviertan en negativos, no, eso no debería suceder en ningún caso, ni siquiera con versiones anteriores a la 2.4 (ya que especificas los long).
        Si no hay suficiente RAM, se produce un error en tiempo de ejecución y santas pascuas. Lo de los negativos NO PUEDE SER.
        A no ser que…
        Hmmm. ¿No estarás importando por casualidad los long de la librería ctypes?
        Porque esos long sí que pueden padecer overflow.
        ¿Mis funciones a pelo (sin ningún import) también te petan?
        A ver si tienes algún módulo de RAM en mal estado…

        La optimización es una pijada. Es lo que haría alguien con lápiz y papel para continuar una rejilla inacabada en otro papel. Como el cambio es mínimo, me pareció que merecía la pena.

        En cuanto a los impares, genial observación.

        Ánimo, presenta algo tú también. A ver si mantenemos el tinglado.
        Total, peor que el mío no va a haber ninguno…

  5. Rogelio

    Por cierto, Divagante, tu problema deberia pasar a la historia. Y lo digo porque el de Delannoy lo ha hecho:
    http://mathworld.wolfram.com/DelannoyNumber.html
    Y no es mas que el tuyo pero con las diagonales opuestas!!!!
    Eso si, Delannoy se lo curro y obtuvo el termino general, pero tambien el suyo es mucho mas facil, mucho mas simetrico y todos los numeros de Delannoy son impares !!!!

    Jabon, decias que el termino general de Schroder te ayudaria, pues aqui esta:
    http://mathworld.wolfram.com/SchroederNumber.html
    Suerte!!! A por la medalla!!!!

    Este problema se merece su rincon en la historia, me extranya que no lo hayan machacado ya.

  6. jabon

    Muy bien Superpan, seguro que tu desafío será muy interesante.
    El de mañana es fácil (no digo extremadamente fácil esta vez), y seguro que alguien habrá visto algo similar.
    A mí me gusta (de los que habéis visto míos, el que más), pero eso no quiere decir que sea del agrado vuestro.
    Tengo ya prácticamente ultimado otro que a más de uno le entretendrá un ratito. Sólo el planteamiento y análisis me ha llevado mucho tiempo. Hasta puede que tenga algún error en la respuesta, pero no me importa, así también aprendo y participo yo.
    Bueno, para ir calentando, el de mañana se basa en un conocido juego.

    • Superpanzeta

      Lo único interesante en mi desafío va a ser la cara de tonto que se me va a quedar.
      Menos mal que aquí todo el mundo es muy amable.

      Gracias, Jabón. Me encanta que sigas al ataque.
      A ver si se anima más gente.

  7. rogelio

    Por cierto, Divagante, tu problema deberia pasar a la historia. Y lo digo porque el de Delannoy lo ha hecho:
    http://mathworld.wolfram.com/DelannoyNumber.html
    Y no es mas que el tuyo pero con las diagonales opuestas!!!!
    Eso si, Delannoy se lo curro y obtuvo el termino general, pero tambien el suyo es mucho mas facil, mucho mas simetrico y todos los numeros de Delannoy son impares !!!!

    Jabon, decias que el termino general de Schroder te ayudaria, pues aqui esta:
    http://mathworld.wolfram.com/SchroederNumber.html
    Suerte!!! A por la medalla!!!!

    Este problema se merece su rincon en la historia, me extranya que no lo hayan machacado ya.

  8. Bilbomath

    Yo tengo alguno por ahí, a ver si en semanas posteriores lo mando porque estos días estoy bastante liado y ni siquiera me he puesto con el último desafío.

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