Sumar 18: un problema fácil y otro que lo es menos

En una página que no mencionaré (solo porque creo que en los comentarios hay soluciones) se propuso el siguiente problema: combinar los números 2, 3, 4 y 5 con las operaciones aritméticas (+, -, *, /) para obtener 18 como resultado.

Tal es el problema fácil.

El menos fácil: encontrar todas (¡ya sabemos que la suma conmuta!) las soluciones.

5 comentarios sobre “Sumar 18: un problema fácil y otro que lo es menos

  1. Daniel 21 mayo, 2015 11:57

    Una solución en Lisp:

    Resultado:

    ((2 + 4 = 6) (6 * 3 = 18))
    ((2 + 4 = 6) (3 * 6 = 18))
    ((2 * 5 = 10) (10 – 4 = 6) (6 * 3 = 18))
    ((2 * 5 = 10) (10 – 4 = 6) (3 * 6 = 18))
    ((4 + 2 = 6) (6 * 3 = 18))
    ((4 + 2 = 6) (3 * 6 = 18))
    ((4 + 5 = 9) (9 * 2 = 18))
    ((4 + 5 = 9) (2 * 9 = 18))
    ((4 * 5 = 20) (20 – 2 = 18))
    ((5 * 2 = 10) (10 – 4 = 6) (6 * 3 = 18))
    ((5 * 2 = 10) (10 – 4 = 6) (3 * 6 = 18))
    ((5 + 4 = 9) (9 * 2 = 18))

    ————————————————–
    código:

    (defun opera(l op x y)
    (when (and (zerop y) (eq op #’/))
    (return-from opera (values nil 0)))
    (let ((z (funcall op x y)))
    (values (cons z (loop for k in l when (and (/= k x) (/= k y)) collect k))
    z)))

    (defun calcula(l target mem)
    (loop with ops = (list #’+ #’- #’* #’/)
    for i below (length l) for x in l
    do (loop for j below (length l) for y in l when (/= i j)
    do (loop for op in ops for opn = (nth-value 2 (function-lambda-expression op))
    do (multiple-value-bind (l1 z) (opera l op x y)
    (if (= z target)
    (print (reverse (cons (list x opn y ‘= z) mem)))

    llamada:

    (calcula (list 2 3 4 5) 18 nil)

  2. Carlos J. Gil Bellosta 21 mayo, 2015 15:13

    Muy bien. Aunque creo que el enunciado original llevaba implícito usar los cuatro números; en tal caso, la solución es prácticamente única.

  3. Daniel 21 mayo, 2015 15:58

    Una sencilla modificación para obtener solución que usa todos los números de la lista inicial, suponiendo que sean distintos.
    ——————————————————-
    LLamada:
    CL-USER> (calcula (list 2 3 4 5) 18)

    ((2 * 5 = 10) (10 – 4 = 6) (6 * 3 = 18))
    ((2 * 5 = 10) (10 – 4 = 6) (3 * 6 = 18))
    ((5 * 2 = 10) (10 – 4 = 6) (6 * 3 = 18))
    ((5 * 2 = 10) (10 – 4 = 6) (3 * 6 = 18))
    ———————————————-
    Código:

    (defun opera(l op x y)
    (when (and (zerop y) (eq op #’/))
    (return-from opera (values nil 0)))
    (let ((z (funcall op x y)))
    (values (cons z (set-difference l (list x y))) z)))

    (defun calcula0(l l0 target mem)
    (loop with ops = (list #’+ #’- #’* #’/)
    for i below (length l) for x in l
    do (loop for j below (length l) for y in l when (/= i j)
    do (loop for op in ops for opn = (nth-value 2 (function-lambda-expression op))
    do (multiple-value-bind (l1 z) (opera l op x y)
    (if (and (= z target) (endp (intersection l1 l0)))
    (print (reverse (cons (list x opn y ‘= z) mem)))
    (when (>= (length l1) 2)
    (calcula0 l1 l0 target (cons (list x opn y ‘= z) mem)))))))))

    (defun calcula(l target)
    (calcula0 l l target nil))

    Posiblemente alguna versión con python usando la librería para permutaciones saldría más corto. Un saludo.

  4. daniel 21 mayo, 2015 16:03

    Modificado para que use todos los números de la lista, se supone que la lista inicial no tiene números repetidos.

    CL-USER> (calcula (list 2 3 4 5) 18)

    ((2 * 5 = 10) (10 – 4 = 6) (6 * 3 = 18))
    ((2 * 5 = 10) (10 – 4 = 6) (3 * 6 = 18))
    ((5 * 2 = 10) (10 – 4 = 6) (6 * 3 = 18))
    ((5 * 2 = 10) (10 – 4 = 6) (3 * 6 = 18))

    ——————-
    Código:

    (defun opera(l op x y)
    (when (and (zerop y) (eq op #’/))
    (return-from opera (values nil 0)))
    (let ((z (funcall op x y)))
    (values (cons z (set-difference l (list x y))) z)))

    (defun calcula0(l l0 target mem)
    (loop with ops = (list #’+ #’- #’* #’/)
    for i below (length l) for x in l
    do (loop for j below (length l) for y in l when (/= i j)
    do (loop for op in ops for opn = (nth-value 2 (function-lambda-expression op))
    do (multiple-value-bind (l1 z) (opera l op x y)
    (if (and (= z target) (endp (intersection l1 l0)))
    (print (reverse (cons (list x opn y ‘= z) mem)))
    (when (>= (length l1) 2)
    (calcula0 l1 l0 target (cons (list x opn y ‘= z) mem)))))))))

    (defun calcula(l target)
    (calcula0 l l target nil))

  5. Daniel 22 mayo, 2015 1:03

    Para ver qué números se pueden formar con las operaciones +,-,*,/ usando sólo números enteros positivos en cada paso.

    Ejemplo, usando la lista del 2 al 5 obtenemos:
    *Main> h3 [2..5]
    [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,33,34,36,37,38,39,40,42,43,44,45,46,48,50,52,54,55,58,62,64,66,68,70,84,90,100,120]
    ——————–
    Código en Haskell, solo 5 líneas:

    import Data.List
    ops = [(+),(-),(*),div]
    h1 l = [ ((f x y) : (l \\ [x,y])) | f <- ops, x <- l, y y ]
    h2 l = nub $ sort $ l >>= h1
    h3 l = map head $ (iterate h2 (h1 l)) !! (length l – 2)
    ———————–

    Imagino que en R también se puede hacer fácilmente.

Los comentarios están desabilitados.