Ir al contenido principal

Ralsina.Me — El sitio web de Roberto Alsina

Brute Force Works

Last ni­gh­t, Juan­jo Conti twee­ted this:

Or, in en­glis­h: "U­sing exac­tly on­ce the di­gi­ts 1,3,4 and 6, and any of the four ba­sic ope­ra­tion­s, ob­tain 24."

I first spent a cou­ple of mi­nu­tes thi­nking about it and then it hit me: the­re is no point in thi­nking this sort of pro­ble­m, be­cau­se:

  1. Bru­­te fo­r­­cing it wi­­ll take le­ss ti­­me

  2. What you do whi­­le "thi­nki­n­­g" it is sort of la­­me, is­n't it?

So, he­re is a mo­re-o­r-­le­ss ge­ne­ral so­lu­tion for any of the­se pro­ble­ms.

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) == -tar­get where you just need to add a unary - to the expression, but who cares.

Did I miss so­me­thin­g? Is this rea­lly a ge­ne­ral so­lu­tio­n?

jjconti / 2015-10-28 15:46:

Great!

Output:

((14)-6)*3

6/(1-(3/4))

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:

"the­re is no po­int in thi­nking this sort of pro­ble­m"

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!


Contents © 2000-2024 Roberto Alsina