Un pequeño reto de programación

Acabo de pasar un rato resolviendo un reto de programación. Los premios no son gran cosa. Aunque si viven en Nueva York podrían ganar el poder trabajar un mes en las oficinas de Hyperpublic (y podrían ser contratados).

Para quien se considere un buen programador, publico aquí uno de los dos problemas ya que me pareció muy interesante: La descripción del problema es muy sencilla, es necesario muy poco código para resolverlo (mi solución es de 35 lineas en java) y la primera solución que se le ocurre a uno no funciona. En otras palabras, es interesante porque tienes que pensar.

Considera la siguiente suma de productos:

x1*98 + x2*42 + x3*23 + x4*17 + x5*3 + x6*2

Crea un programa que encuentre los xi (números naturales, incluyendo el 0) para lograr los resultados 2349, 2102, 2001 y 1747 pero que cumplan que el resultado de la suma yi = x1+x2+x3+x4+x5+x6 sea el menor posible.

Dos tips:

  • No intenten la fuerza bruta. Si lo hacen su programa requeriría  aprox. 23^6 loops por cada resultado. Mi programa (en java) obtiene todos los resultados en menos de un segundo.
  • Cuando terminen multipliquen y1*y2*y3*y4. Si el resultado es 450225 (o mas), cayeron en la trampa.

Si lo resuelven hagan el reto completo ya que el otro problema es más sencillo, y mándenme su solución para conocer a los hackers que visitan este blog. En unos días publico mi solución por si alguien lo intentó.

Por cierto, si su solución es correcta habrán usado, tal vez sin saberlo, programación dinámica.

Actualización: olvidé mencionar que los coeficientes deben ser números naturales incluyendo el 0.

13 comentarios en “Un pequeño reto de programación

    • No es un sistema de ecuaciones. Tu función se llama una vez por cada uno de los 4 resultados de manera independiente. La única condición es que el resultado de la suma de los coeficientes que obtengas, sea el menor posible en cada caso.

      Me gusta

    • Pues el reto formalmente es únicamente encontrar los coeficientes cuya suma sea lo menor posible. Pero si tu programa tardó varias horas en encontrar el resultado, tal vez te intrigue saber que puedes hacerlo de tal forma que tome menos de un segundo. Por otro lado, es muy fácil equivocarse. Para verificar tu solución puedes poner aqui tu resultado de y1*y2*y3*y4, así como lo hizo Ramon, y si es correcto, lo edito antes de que se muestre públicamente.

      Me gusta

      • en la versión de código veloz me da exactamente lo mismo que a ti, en la versión de menor coeficiente me da mucho menos que a ti, aunque es mas lenta. claro que no estamos hablando de horas sino de apenas un poco mas.

        Me gusta

  1. Este es como el problema de dar un cambio con el menor número de billetes posibles, sólo que los billetes que tienes son de valor 98, 42, 23, 17, 3 y 2. Como curiosidad, decir que que el algoritmo rápido con “trampa” en el que se suele caer, es perfectamente válido para las monedas que normalmente usamos, porque los valores de nuestros billetes y monedas hacen que la solución rápida siempre sea también con la que devuelves el menor número.

    Para quien le gusten este tipo de problemas de programación: http://acm.uva.es/problemset/

    Me gusta

  2. Bueno la versión pensada para mínimos coeficientes va en 354.200 creo que ese sera mi límite. Tiempo de ejecución 1 segundo o menos.

    En el trascurso de estos días publicare mi solución y debo admitir que es bastante más compleja de lo que es la primera versión de la que hable acá.

    saludos.

    Me gusta

  3. Para dejar trace de lo que dije en Twitter:
    bueno, lo que hice es trabajar en tres grupos
    1# el numero mas grandes
    2# los 3 números intermedios
    3# los 2 de valor mas bajo

    No soy malo en mates pero tampoco soy muy bueno, asi q estoy seguro q mi codigo esta + complejo de la cuenta,aunque es muy rápido.

    Me gusta

  4. Hola, no se si mi solucione s correcta pero me voy a arriesgar: lo que hice (para simplificar el asunto) es asignar a x2, x3, x4, x5, x6 cero. con eso solo debiria despejar x1

    el resultado esperado (2349, 2102, 2001 y 1747) lo dividí por 98 para cada caso x1 resultaria en los siguientes valores:

    X1 = 23,969387755102040816326530612 X2 = 0 X3 = 0 X4 = 0 X5 = 0 X6
    X1 = 21,44897959183673469387755102 X2 = 0 X3 = 0 X4 = 0 X5 = 0 X6
    X1 = 20,418367346938775510204081633 X2 = 0 X3 = 0 X4 = 0 X5 = 0 X6
    X1 = 17,826530612244897959183673469 X2 = 0 X3 = 0 X4 = 0 X5 = 0 X6

    como cada Y es igual a la suma de todos los x entonces podemos decir que

    y1 = 23,969387755102040816326530612
    y2 = 21,44897959183673469387755102
    y3 = 20,418367346938775510204081633
    y4 = 17,826530612244897959183673469

    Si hacemos la comprobacion de la “trampa” entonces tenemos que:
    y1 * y2 * y3 * y4 = 187133,4478382903

    mi programa tambien se ejecuta en menos de un segundo. Ahora como mensione antes no se si lo que hice es politicamente correcto… pero desde mi punto de vista me parece que funciona.

    Me gusta

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