Escribiendo una versión en C++ del juego de álgebra 24

Question

Estoy tratando de escribir un programa en C++ que funcione como el juego 24. Para aquellos que no saben cómo se juega, básicamente tratas de encontrar cualquier forma en que 4 números puedan total 24 a través de los cuatro operadores algebraicos de +, -, /, * y paréntesis.

Como un ejemplo, que un usuario introduce 2,3,1,5 ((2 + 3) * 5) - 1 = 24

era relativamente sencillo para codificar la función para determinar si tres números pueden make 24 debido a la cantidad limitada de posiciones para paréntesis, pero no entiendo cómo se codifica de manera eficiente cuando se ingresan cuatro variables.

---

Tengo algunas permutaciones de trabajo ahora, pero todavía no se pueden enumerar todos los casos, porque no sé cómo el código para los casos en que las operaciones son las mismas.

Además, ¿cuál es la forma más fácil de calcular el RPN? Encontré muchas páginas como esta: http://www.dreamincode.net/forums/index.php?showtopic=15406 pero como principiante, no estoy seguro de cómo implementarlo.

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 





bool MakeSum(int num1, int num2, int num3, int num4) 
{ 

    vector<int> vi; 
    vi.push_back(num1); 
    vi.push_back(num2); 
    vi.push_back(num3); 
    vi.push_back(num4); 

    sort(vi.begin(),vi.end()); 


    char a1 = '+'; 
    char a2 = '-'; 
    char a3 = '*'; 
    char a4 = '/'; 
    vector<char> va; 
    va.push_back(a1); 
    va.push_back(a2); 
    va.push_back(a3); 
    va.push_back(a4); 

    sort(va.begin(),va.end()); 
    while(next_permutation(vi.begin(),vi.end())) 
    { 

     while(next_permutation(va.begin(),va.end())) 
    { 

     cout<<vi[0]<<vi[1]<<vi[2]<<vi[3]<< va[0]<<va[1]<<va[2]<<endl; 

     cout<<vi[0]<<vi[1]<<vi[2]<<va[0]<< vi[3]<<va[1]<<va[2]<<endl; 

     cout<<vi[0]<<vi[1]<<vi[2]<<va[0]<< va[1]<<vi[3]<<va[2]<<endl; 

     cout<<vi[0]<<vi[1]<<va[0]<<vi[2]<< vi[3]<<va[1]<<va[2]<<endl; 

     cout<<vi[0]<<vi[1]<<va[0]<<vi[2]<< va[1]<<vi[3]<<va[2]<<endl; 


    } 

    } 

    return 0; 

} 

int main() 
{ 

    MakeSum(5,7,2,1); 
    return 0; 
} 

Answer 1

Por lo tanto, la forma más sencilla es a través de permutar todas las combinaciones posibles. Esto es un poco complicado, el orden de los números puede ser importante, y ciertamente el orden de las operaciones es.

Una observación es que está intentando generar todos los árboles de expresión posibles con ciertas propiedades. Una propiedad es que el árbol siempre tendrá exactamente 4 hojas. Esto significa que el árbol también tendrá siempre exactamente 3 nodos internos. Solo hay 3 formas posibles para dicho árbol:

A 
/\ 
N A 
/\  (and the mirror image) 
    N A 
    /\ 
    N N 

    A 
/\ 
N A 
/\ 
    A N (and the mirror image) 
/\ 
N N 

    A 
    /` `\ 
    A  A 
/\ /\ 
N N N N 

En cada lugar para A puede tener una de las 4 operaciones. En cada lugar para N puedes tener cualquiera de los números. Pero cada número solo puede aparecer para una N. N.

Codificar esto como una búsqueda de fuerza bruta no debería ser demasiado difícil, y creo que una vez que haya hecho las cosas de esta manera será más fácil pensar en las optimizaciones. Por ejemplo, + y * son conmutativos. Esto significa que los espejos que activan los hijos izquierdo y derecho de esas operaciones no tendrán ningún efecto. Podría ser posible reducir la búsqueda a través de tales volteos.

Alguien más ha mencionado la notación RPN. Los árboles se asignan directamente a esto. Aquí está una lista de todos los árboles posibles en RPN:

N N N N A A A 
N N N A N A A 
N N N A A N A 
N N A N N A A 
N N A N A N A 

Eso es 4 * 3 * 2 = 24 posibilidades de números, 4 * 4 * 4 = 64 posibilidades para las operaciones, 24 * 64 * 5 = 7680 posibilidades totales para un conjunto dado de 4 números. Fácil de contar y se puede evaluar en una pequeña fracción de segundo en un sistema moderno. Diablos, incluso en básico en mi viejo Atari 8 bit, apuesto a que este problema solo tomaría minutos para un grupo dado de 4 números.

Answer 2

escribí algo como esto antes. Necesitas un evaluador recursivo. Llamada evaluar, cuando presionas "(" evaluar de la llamada nuevamente, de lo contrario, ejecutar junto con dígitos y operadores hasta que toques ")", ahora devuelve el resultado de - + */operaciones la instancia de evaluación anterior

Answer 3

Consulta la Problema de mochila (aquí hay un enlace para que comiences: http://en.wikipedia.org/wiki/Knapsack_problem), este problema es bastante parecido a eso, solo un poco más difícil (y el problema de mochila es NP-completo!)

Answer 4

Una cosa que podría hacer esto más rápido de lo normal es paralelismo Consulte OpenMP. Al usar esto, se realiza más de una comprobación a la vez (su función "alg"), por lo tanto, si tiene una CPU de núcleo doble/cuádruple, su programa debería ser más rápido.

Dicho esto, si como se sugirió anteriormente el problema es NP-completo, será más rápido, no necesariamente rápido.

Answer 5

Puede simplemente usar Reverse Polish Notation para generar las expresiones posibles, lo que debería eliminar la necesidad de parantheses.

Una forma absolutamente ingenua de hacer esto sería generar todas las cadenas posibles de 4 dígitos y 3 operadores (sin prestar atención a la validez como RPN), asumir que está en RPN e intentar evaluarlo. Tocará algunos casos de error (como en cadenas RPN no válidas). El número total de posibilidades (si calculé correctamente) es ~ 50,000.

Una manera más inteligente debería bajarlo a ~ 7500 Creo (64 * 24 * 5 para ser exactos): Generar una permutación de los dígitos (24 formas), generar un triplete de 3 operadores (4^3 = 64 formas) y ahora coloca los operadores entre los dígitos para que sea válido RPN (hay 5 formas, ver la respuesta Omnifarious).

Debe encontrar fácilmente los generadores de permutación y las calculadoras RPN en la web.

Espero que ayude!

PD: Solo FYI: RPN no es más que el recorrido del árbol de expresiones correspondiente al postorder, y para d dígitos, el número es d! * 4^(d-1) * Elija (2 (d-1), (d-1))/d. (El último término es un número catalán).

Answer 6

Editado: La solución a continuación es mal. También debemos considerar los números que se pueden hacer con solo x_2 y x_4, y con solo x_1 y x_4. Este enfoque todavía puede funcionar, pero va a ser bastante más complejo (e incluso menos eficiente). Lo sentimos ...

---

Supongamos que tenemos cuatro números x_1, x_2, x_3, x_4. Escribir

S = { all numbers we can make just using x_3, x_4 }, 

Entonces podemos reescribir el conjunto que nos interesa, que llamaré a

T = { all numbers we can make using x_1, x_2, x_3, x_4 } 

como

T = { all numbers we can make using x_1, x_2 and some s from S }. 

Así que es un algoritmo para generar todos los números posibles de S, luego use cada número s en S a su vez para generar parte de T. (Esto se generalizará bastante fácilmente a n números en lugar de solo 4).

Aquí está un áspero, ejemplo de código no probado:

#include <set> // we can use std::set to store integers without duplication 
#include <vector> // we might want duplication in the inputs 

// the 2-number special case 
std::set<int> all_combinations_from_pair(int a, int b) 
{ 
    std::set results; 

    // here we just use brute force 
    results.insert(a+b); // = b+a 
    results.insert(a-b); 
    results.insert(b-a); 
    results.insert(a*b); // = b*a 
    // need to make sure it divides exactly 
    if (a%b==0) results.insert(a/b); 
    if (b%a==0) results.insert(b/a); 

    return results; 
} 

// the general case 
std::set<int> all_combinations_from(std::vector<int> inputs) 
{ 
    if (inputs.size() == 2) 
    { 
    return all_combinations_from_pair(inputs[0], inputs[1]); 
    } 
    else 
    { 
    std::set<int> S = all_combinations_from_pair(inputs[0], inputs[1]); 
    std::set<int> T; 
    std::set<int> rest = S; 
    rest.remove(rest.begin()); 
    rest.remove(rest.begin()); // gets rid of first two 

    for (std::set<int>.iterator i = S.begin(); i < S.end(); i++) 
    { 
     std::set<int> new_inputs = S; 
     new_inputs.insert(*i); 
     std::set<int> new_outputs = all_combinations_from(new_inputs); 

     for (std::set<int>.iterator j = new_outputs.begin(); j < new_outputs.end(); j++) 
     T.insert(*j); // I'm sure you can do this with set_union() 
    } 

    return T; 
    } 
} 

Answer 7

Si puede utilizar el mismo operador dos veces, probablemente no desee mezclar los operadores en los números. En su lugar, quizás use tres 0 como marcador de posición para donde ocurrirán las operaciones (ninguno de los 4 números es 0, ¿verdad?) Y use otra estructura para determinar qué operaciones se usarán.

La segunda estructura podría ser vector<int> inicializada con tres 1 seguidos de tres 0. Los 0 corresponden a los 0 en el número vector. Si un 0 está precedido por cero 1 de, la operación correspondiente es +, si es precedido por uno 1, es -, etc. Por ejemplo:

6807900 <= equation of form (6 @ 8) @ (7 @ 9) 
100110 <= replace @'s with (-,-,/) 
possibility is (6-8)-(7/9) 

avanzar por las posibilidades de operación utilizando next_permutation en un bucle interno.

Por cierto, también puede volver temprano si la permutación de número es una expresión de postfijo no válida. Todas las permutaciones del ejemplo anterior menos de 6708090 no son válidas, y todas las mayores son válidas, por lo que puede comenzar con 9876000 y trabajar con prev_permutation.