Brute Force Works

2015-10-28 15:24 | También disponible en: English

Last night, Juanjo Conti tweeted this:

Usando exactamente una vez los dígitos 1, 3, 4 y 6 y cualquiera de las cuatro operaciones básicas, obtener 24.
— Juanjo Conti (@jjconti) octubre 27, 2015

Or, in english: "Using exactly once the digits 1,3,4 and 6, and any of the four basic operations, obtain 24."

I first spent a couple of minutes thinking about it and then it hit me: there is no point in thinking this sort of problem, because:

Brute forcing it will take less time
What you do while "thinking" it is sort of lame, isn't it?

So, here is a more-or-less general solution for any of these problems.

from __future__ import print_function, division
import itertools

numbers = ['1','3','4','6']
target = 24

# Having '' as an operation allows for solution (14-6)*3, which
# may or may not be valid depending on rule interpretation.
operations =  ['*','/','+','-','']

t1='(({0}{4}{1}){5}{2}){6}{3}'
t2='{0}{4}({1}{5}({2}{6}{3}))'

for nums in itertools.permutations(numbers):
    for ops1 in itertools.combinations_with_replacement(operations, 3):
        for ops2 in itertools.permutations(ops1):
            for t in (t1, t2):
                s = t.format(*(nums+ops2))
                #print(repr(s))
                try:
                    if eval(s) == target:
                        print(s)
                except (ZeroDivisionError, SyntaxError, TypeError):
                    continue

Of course you can make it solve any problem of this class by adjusting numbers and target. There is also a possible extra solution if eval(s) == -target where you just need to add a unary - to the expression, but who cares.

Did I miss something? Is this really a general solution?

jjconti / 2015-10-28 15:46:

Great!

Output:

((14)-6)*3

6/(1-(3/4))

jjconti / 2015-10-28 15:48:

With -target:

3*(6-(14))

Roberto Alsina / 2015-10-28 15:56:

claro, porque -(3*(6-14)) tambien es una solucion para 24 :-)

Juanlu001 / 2015-10-29 08:30:

"there is no point in thinking this sort of problem"

The point of this sort of problem is actually thinking about it, not finding a solution. As you proved, any computer can find a solution :)

zetam / 2015-11-28 21:09:

(1+2+3)*4

Ariel Juan Rodriguez / 2016-09-25 21:28:

Hola Roberto, tengo una duda. ¿Por qué solo tuviste en cuenta estos dos órdenes?
t1='(({0}{4}{1}){5}{2}){6}{3}'
t2='{0}{4}({1}{5}({2}{6}{3}))'

Por ejemplo, para esta combinación, tu script da dos posibilidades:
((6*1)4)+3
6*(1(4+3))

Se me ocurren otras alternativas:
(6*1)(4+3)
6*((1)4)+3

Un saludo.

Roberto Alsina / 2016-09-25 23:08:

El problema de permitir '' como operador es que produce combinaciones que no funcionan porque no son expresiones válidas, como esas.

Si ponemos el operador habitual entre un número y un paréntesis (multiplicacion) tus alternativas no funcionan:

(6*1)*(4+3) da 42, no 24

6*((1)*4)+3 da 27, no 24

Y de hecho lo que dices que da mi script tampoco:

((6*1)*4)+3 -> 27
6*(1*(4+3)) -> 42

O me estoy perdiendo algo? Porque mi script no imprime eso, imprime lo que dice Juanjo en un comentario anterior.

Ok, hablando por twitter creo que entendi la pregunta. Sería algo como "por que solo t1 y t2, acaso no hay algun otro orden posible para combinar numeros y operaciones?"

Veamos! Es combinar 4 numeros. Para dos numeros es trivial:

N1 op1 N2

Para 3 numeros:

N1 op1 N2 op2 N3

Pero como podemos poner parentesis, podemos cambiar el orden de precedencia:

(N1 op1 N2) op2 N3

no es lo mismo que

N1 op1 (N2 op2 N3)

Para 4 numeros, es mas complicado. Estos son los dos ordenes que yo usé en el script:

N1 op1 (N2 op2 (N3 op3 N4))

((N1 op1 N2) op2 N3) op3 N4

Tambien se podría hacer esto:

N1 op1 (N2 op2 N3) op3 N4

o esto:

(N1 op1 N2) op3 (N3 op4 N4)

Que sí, falta. (antes decía que era equivalente a t1 y t2, pero no lo es)

Ariel Juan Rodriguez / 2016-09-25 23:37:

Mi duda es cómo elegiste inicialmente los dos órdenes.
Los que te pasé eran ejemplos de tus dos órdenes y otros dos que yo creé con los mismos 7 elementos en el mismo orden (cambiando los paréntesis).
Porque vi tu script y no pude sacarme la duda acerca de cómo, en un principio, escogiste solo esos dos órdenes cuando se me ocurren otros.

Roberto Alsina / 2016-09-26 14:35:

No puede ser. Mi script no produciría jamás "((6*1)4)+3" porque no es válido (daría SyntaxError al tratar de evaluarlo)

Ariel Juan Rodriguez / 2016-09-25 23:43:

Veo que editaste el comentario, ahora sí nos hemos entendido. Buscaba entender cómo razonaste la solución al programarla, porque es correcta pero me quedaba a mitad de camino al intentar enteder esos dos órdenes.
Gracias!

Ralsina.Me — El sitio web de Roberto Alsina