Écrire une version C++ du jeu d'algèbre 24

Question

J'essaie d'écrire un programme C++ qui fonctionne comme le jeu 24. Pour ceux qui ne connaissent pas ce jeu, il s'agit de trouver comment 4 nombres peuvent totaliser 24 grâce aux quatre opérateurs algébriques +, -, /, * et les parenthèses.

A titre d'exemple, disons que quelqu'un entre 2,3,1,5 ((2+3)*5) - 1 = 24

Il était relativement simple de coder la fonction permettant de déterminer si trois nombres peuvent faire 24 en raison du nombre limité de positions pour les parenthèses, mais je ne parviens pas à la coder efficacement lorsque quatre variables sont entrées.

---

J'ai quelques permutations qui fonctionnent maintenant mais je ne peux toujours pas énumérer tous les cas car je ne sais pas comment coder pour les cas où les opérations sont les mêmes.

Par ailleurs, quelle est la méthode la plus simple pour calculer l'IPR ? Je suis tombé sur de nombreuses pages telles que celle-ci : http://www.dreamincode.net/forums/index.php?showtopic=15406 mais en tant que débutant, je ne sais pas comment le mettre en œuvre.

#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

Le moyen le plus simple est donc de permuter toutes les combinaisons possibles. C'est un peu délicat, l'ordre des nombres peut être important, et certainement l'ordre des opérations.

Une observation est que vous essayez de générer tous les arbres d'expression possibles avec certaines propriétés. L'une de ces propriétés est que l'arbre aura toujours exactement 4 feuilles. Cela signifie que l'arbre aura également toujours exactement 3 nœuds internes. Il n'y a que trois formes possibles pour un tel arbre :

  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

Dans chaque emplacement de A, vous pouvez avoir n'importe laquelle des 4 opérations. Dans chaque case de N, on peut avoir n'importe lequel des chiffres. Mais chaque nombre ne peut apparaître que pour un seul N.

Coder cela comme une recherche par force brute ne devrait pas être trop difficile, et je pense qu'une fois que vous aurez fait les choses de cette manière, il sera plus facile de penser aux optimisations.

Par exemple, + y * sont commutatives. Cela signifie que les miroirs qui inversent les enfants de gauche et de droite de ces opérations n'auront aucun effet. Il pourrait être possible de réduire la recherche à travers tous ces retournements.

Quelqu'un d'autre a mentionné la notation RPN. Les arbres correspondent directement à cette notation. Voici une liste de tous les arbres possibles 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

Cela fait 4*3*2 = 24 possibilités pour les nombres, 4*4*4 = 64 possibilités pour les opérations, 24 * 64 * 5 = 7680 possibilités totales pour un ensemble donné de 4 nombres. Facilement dénombrable et pouvant être évalué en une minuscule fraction de seconde sur un système moderne. Heck, même en basic sur mon vieil Atari 8 bit, je parie que ce problème ne prendrait que quelques minutes pour un groupe donné de 4 nombres.

Answer 2

Vous pouvez simplement utiliser Notation polonaise inversée pour générer les expressions possibles, ce qui devrait supprimer la nécessité des paranthèses.

Une façon absolument naïve de le faire serait de générer toutes les chaînes possibles de 4 chiffres et 3 opérateurs (sans tenir compte de la validité en tant que RPN), de supposer que c'est en RPN et d'essayer de l'évaluer. Vous rencontrerez quelques cas d'erreur (comme pour les chaînes RPN invalides). Le nombre total de possibilités (si j'ai bien calculé) est de ~50 000.

Une méthode plus astucieuse devrait permettre de descendre à ~7500 je crois (64*24*5 pour être exact) : Générer une permutation des chiffres (24 façons), générer un triplet de 3 opérateurs (4^3 = 64 façons) et maintenant placer les opérateurs parmi les chiffres pour en faire un RPN valide (il y a 5 façons, voir la réponse d'Omnifarious).

Vous devriez pouvoir trouver facilement des générateurs de permutations et des calculateurs RPN sur le web.

J'espère que cela vous aidera !

PS : Juste pour info : RPN n'est rien d'autre que la traversée post-ordre de l'arbre d'expression correspondant, et pour d chiffres, le nombre est d ! * 4^(d-1) * Choose(2(d-1), (d-1))/d. (Le dernier terme est un nombre catalan).

Answer 3

Modifié : La solution ci-dessous est mauvais . Nous devons également considérer les nombres réalisables avec seulement x_2 et x_4, et avec seulement x_1 et x_4. Cette approche peut toujours fonctionner, mais elle sera plus complexe (et encore moins efficace). Désolé...

---

Supposons que nous ayons quatre nombres x_1, x_2, x_3, x_4. Ecrivez

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

On peut alors réécrire l'ensemble qui nous intéresse, que j'appellerai

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

comme

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

Un algorithme consiste donc à générer tous les nombres possibles dans S, puis à utiliser chaque nombre s dans S à tour de rôle pour générer une partie de T. (Cela se généralise assez facilement à n nombres au lieu de 4 seulement).

Voici un exemple de code brut, non testé :

#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 4

Si vous êtes autorisé à utiliser le même opérateur deux fois, vous ne voulez probablement pas mélanger les opérateurs dans les chiffres. Au lieu de cela, vous pouvez utiliser trois 0 pour indiquer où les opérations auront lieu (aucun des 4 nombres n'est égal à 0, n'est-ce pas ?) et utiliser une autre structure pour déterminer quelles opérations seront utilisées.

La deuxième structure pourrait être un vector<int> initialisé avec trois 1 suivis de trois 0. Les 0 correspondent aux 0 du nombre vector . Si un 0 est précédé de zéro 1, l'opération correspondante est + si elle est précédée d'un 1, elle est - etc. Par exemple :

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

Avancez dans les possibilités d'opération en utilisant next_permutation dans une boucle interne.

Au fait, vous pouvez également retourner prématurément si la permutation du nombre est une expression postfixe invalide. Toutes les permutations de l'exemple ci-dessus inférieures à 6708090 ne sont pas valides, et toutes les permutations supérieures sont valides, donc vous pouvez commencer par 9876000 et descendre avec prev_permutation .

Answer 5

Recherchez le problème du sac à dos (voici un lien pour vous aider à démarrer) : http://en.wikipedia.org/wiki/Knapsack_problem ), ce problème en est assez proche, juste un peu plus difficile (et le problème du Knapsack est NP-complet !).