java - tiempo - timbiriche juego estrategia

Cómo diseñar un algoritmo para calcular la cuenta regresiva estilo matemático número rompecabezas

Question

Siempre quise hacer esto, pero cada vez que empiezo a pensar en el problema me sorprende por su naturaleza exponencial.

El solucionador de problemas que quiero entender y codificar es para el problema matemático de la cuenta regresiva:

Dado el conjunto de números X1 a X5, calcule cómo se pueden combinar utilizando operaciones matemáticas para hacer Y. Puede aplicar la multiplicación, la división, la suma y la resta.

Entonces, ¿cómo hace 1,3,7,6,8,3 hace 348 ?

Respuesta: (((8 * 7) + 3) -1) *6 = 348 .

¿Cómo escribir un algoritmo que pueda resolver este problema? ¿Dónde empiezas cuando intentas resolver un problema como este? ¿Qué consideraciones importantes debe tener en cuenta al diseñar un algoritmo de este tipo?

Answer 1

Claro que es exponencial, pero es pequeño, por lo que una buena implementación (ingenua) sería un buen comienzo. Le sugiero que elimine la notación de infijo habitual con el horquillado, y use postfix, es más fácil de programar. Siempre puedes pretender las salidas como una etapa separada.

Comience enumerando y evaluando todas las secuencias (válidas) de números y operadores. Por ejemplo (en postfix):

1 3 7 6 8 3 + + + + + -> 28
1 3 7 6 8 3 + + + + - -> 26

Mi Java es risible, no vengo aquí para que me rían, así que dejaré la codificación para usted.

Para todas las personas inteligentes que leen esto: sí, sé que incluso para un problema pequeño como este existen enfoques más inteligentes que probablemente sean más rápidos, solo estoy apuntando a OP hacia una solución de trabajo inicial. Alguien más puede escribir la respuesta con las soluciones más inteligentes.

Por lo tanto, para responder a sus preguntas:

• Comienzo con un algoritmo que creo que me llevará rápidamente a una solución de trabajo. En este caso, la elección obvia (para mí) es la enumeración exhaustiva y la prueba de todos los cálculos posibles.
• Si el algoritmo obvio no parece atractivo por razones de rendimiento, comenzaré a pensar más profundamente en él, recordando otros algoritmos que conozco que probablemente ofrezcan un mejor rendimiento. Puedo comenzar a codificar uno de esos primero.
• Si me quedo con el algoritmo exhaustivo y encuentro que el tiempo de ejecución es, en la práctica, demasiado largo, entonces podría volver al paso anterior y codificar nuevamente. Pero tiene que valer la pena, hay que hacer una evaluación de costo / beneficio, siempre que mi código pueda superar a Rachel Riley, estaría satisfecho.
• Las consideraciones importantes incluyen mi tiempo frente a la computadora, la mía cuesta muchísimo más.

Answer 2

Creo que primero debes definir estrictamente el problema. Lo que se te permite hacer y lo que no eres. Puedes comenzar haciéndolo simple y solo permitiendo la multiplicación, división, resta y suma.

Ahora ya conoce el espacio de su problema: conjunto de entradas, conjunto de operaciones disponibles y entrada deseada. Si solo tiene 4 operaciones y x entradas, el número de combinaciones es menor que:

El número de orden en el que puede realizar operaciones (¡x!) Multiplicado por las posibles opciones de operaciones en cada paso: 4 ^ x. Como se puede ver en 6 números, ofrece 2949120 operaciones razonables. Esto significa que este puede ser su límite para el algoritmo de fuerza bruta.

Una vez que tenga la fuerza bruta y sepa que funciona, puede comenzar a mejorar su algoritmo con algún tipo de algoritmo A * que requiera que defina funciones heurísticas.

En mi opinión, la mejor manera de pensarlo es como el problema de búsqueda. La principal dificultad será encontrar buenas heurísticas o formas de reducir el espacio de su problema (si tiene números que no suman la respuesta, necesitará al menos una multiplicación, etc.). Comience poco a poco, aproveche eso y haga preguntas de seguimiento una vez que tenga algo de código.

Answer 3

Encontré un gran algoritmo de los documentos de ciencias de la computación de Oxford (con código fuente de Java) hace mucho tiempo. Y lo admiro cada vez que leo esta solución. Creo que será útil.

Answer 4

Este problema exacto se trata en el capítulo 9 de "Programación en Haskell" por Graham Hutton. Uno puede mirar allí si está interesado en un enfoque de lenguaje funcional para el problema.

Answer 5

La entrada es obviamente un conjunto de dígitos y operadores: D = {1,3,3,6,7,8,3} y Op = {+, -, *, /}. El algoritmo más directo sería un solucionador de fuerza bruta , que enumerates todas las combinaciones posibles de estos conjuntos. Donde los elementos del conjunto Op pueden usarse tan a menudo como se desee, pero los elementos del conjunto D se usan exactamente una vez. Pseudo código:

D={1,3,3,6,7,8,3}
Op={+,-,*,/}
Solution=348
for each permutation D_ of D:
   for each binary tree T with D_ as its leafs:
       for each sequence of operators Op_ from Op with length |D_|-1:
           label each inner tree node with operators from Op_
           result = compute T using infix traversal
           if result==Solution
              return T
return nil

Aparte de eso: lee las respuestas de jedrus07 y HPM.

Answer 6

Solución muy rápida y sucia en Java:

public class JavaApplication1
{

    public static void main(String[] args)
    {
        List<Integer> list = Arrays.asList(1, 3, 7, 6, 8, 3);
        for (Integer integer : list) {
            List<Integer> runList = new ArrayList<>(list);
            runList.remove(integer);
            Result result = getOperations(runList, integer, 348);
            if (result.success) {
                System.out.println(integer + result.output);
                return;
            }
        }
    }

    public static class Result
    {

        public String output;
        public boolean success;
    }

    public static Result getOperations(List<Integer> numbers, int midNumber, int target)
    {
        Result midResult = new Result();
        if (midNumber == target) {
            midResult.success = true;
            midResult.output = "";
            return midResult;
        }
        for (Integer number : numbers) {
            List<Integer> newList = new ArrayList<Integer>(numbers);
            newList.remove(number);
            if (newList.isEmpty()) {
                if (midNumber - number == target) {
                    midResult.success = true;
                    midResult.output = "-" + number;
                    return midResult;
                }
                if (midNumber + number == target) {
                    midResult.success = true;
                    midResult.output = "+" + number;
                    return midResult;
                }
                if (midNumber * number == target) {
                    midResult.success = true;
                    midResult.output = "*" + number;
                    return midResult;
                }
                if (midNumber / number == target) {
                    midResult.success = true;
                    midResult.output = "/" + number;
                    return midResult;
                }
                midResult.success = false;
                midResult.output = "f" + number;
                return midResult;
            } else {
                midResult = getOperations(newList, midNumber - number, target);
                if (midResult.success) {
                    midResult.output = "-" + number + midResult.output;
                    return midResult;
                }
                midResult = getOperations(newList, midNumber + number, target);
                if (midResult.success) {
                    midResult.output = "+" + number + midResult.output;
                    return midResult;
                }
                midResult = getOperations(newList, midNumber * number, target);
                if (midResult.success) {
                    midResult.output = "*" + number + midResult.output;
                    return midResult;
                }
                midResult = getOperations(newList, midNumber / number, target);
                if (midResult.success) {
                    midResult.output = "/" + number + midResult.output;
                    return midResult
                }
            }

        }
        return midResult;
    }
}

ACTUALIZAR

Es básicamente un algoritmo de fuerza bruta simple con complejidad exponencial. Sin embargo, puede obtener algunas mejoras al aprovechar alguna función heurística que le ayudará a ordenar la secuencia de números o (y) las operaciones que procesará en cada nivel de recursión de la función getOperatiosn() .

Un ejemplo de dicha función heurística es, por ejemplo, la diferencia entre el resultado medio y el resultado objetivo total.

De esta manera, sin embargo, solo se mejoran las complejidades de caso óptimo y caso medio. La peor complejidad del caso permanece intacta.

La complejidad del peor de los casos se puede mejorar mediante algún tipo de corte de rama. No estoy seguro si es posible en este caso.

Answer 7

Una solución de trabajo en c ++ 11 a continuación.

La idea básica es utilizar una evaluación basada en pila (ver RPN ) y convertir las soluciones viables a notación de infijo solo para fines de visualización.

Si tenemos N dígitos de entrada, usaremos operadores (N-1) , ya que cada operador es binario.

Primero creamos permutaciones válidas de operandos y operadores (el selector_ array). Una permutación válida es una que puede evaluarse sin desbordamiento de pila y que termina con exactamente un valor (el resultado) en la pila. Así, 1 1 + es válido, pero 1 + 1 no lo es.

Probamos cada permutación de operador-operando con cada permutación de operandos (la matriz de los values_ ) y cada combinación de operadores (la matriz ops_ ). Los resultados coincidentes están bastante impresos.

Los argumentos se toman de la línea de comando como [-s] <target> <digit>[ <digit>...] . El interruptor -s evita la búsqueda exhaustiva, solo se imprime el primer resultado coincidente.

(use ./mathpuzzle 348 1 3 7 6 8 3 para obtener la respuesta a la pregunta original)

Esta solución no permite concatenar los dígitos de entrada para formar números. Eso podría agregarse como un bucle externo adicional.

El código de trabajo se puede descargar desde here . (Nota: actualicé ese código con soporte para concatenar dígitos de entrada para formar una solución)

Vea los comentarios en el código para una explicación adicional.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iterator>
#include <string>

namespace {

enum class Op {
    Add,
    Sub,
    Mul,
    Div,
};

const std::size_t NumOps = static_cast<std::size_t>(Op::Div) + 1;
const Op FirstOp = Op::Add;

using Number = int;

class Evaluator {
    std::vector<Number> values_; // stores our digits/number we can use
    std::vector<Op> ops_; // stores the operators
    std::vector<char> selector_; // used to select digit (0) or operator (1) when evaluating. should be std::vector<bool>, but that''s broken

    template <typename T>
    using Stack = std::stack<T, std::vector<T>>;

    // checks if a given number/operator order can be evaluated or not
    bool isSelectorValid() const {
        int numValues = 0;
        for (auto s : selector_) {
            if (s) {
                if (--numValues <= 0) {
                    return false;
                }
            }
            else {
                ++numValues;
            }
        }
        return (numValues == 1);
    }

    // evaluates the current values_ and ops_ based on selector_
    Number eval(Stack<Number> &stack) const {
        auto vi = values_.cbegin();
        auto oi = ops_.cbegin();
        for (auto s : selector_) {
            if (!s) {
                stack.push(*(vi++));
                continue;
            }
            Number top = stack.top();
            stack.pop();
            switch (*(oi++)) {
                case Op::Add:
                    stack.top() += top;
                    break;
                case Op::Sub:
                    stack.top() -= top;
                    break;
                case Op::Mul:
                    stack.top() *= top;
                    break;
                case Op::Div:
                    if (top == 0) {
                        return std::numeric_limits<Number>::max();
                    }
                    Number res = stack.top() / top;
                    if (res * top != stack.top()) {
                        return std::numeric_limits<Number>::max();
                    }
                    stack.top() = res;
                    break;
            }
        }
        Number res = stack.top();
        stack.pop();
        return res;
    }

    bool nextValuesPermutation() {
        return std::next_permutation(values_.begin(), values_.end());
    }

    bool nextOps() {
        for (auto i = ops_.rbegin(), end = ops_.rend(); i != end; ++i) {
            std::size_t next = static_cast<std::size_t>(*i) + 1;
            if (next < NumOps) {
                *i = static_cast<Op>(next);
                return true;
            }
            *i = FirstOp;
        }
        return false;
    }

    bool nextSelectorPermutation() {
        // the start permutation is always valid
        do {
            if (!std::next_permutation(selector_.begin(), selector_.end())) {
                return false;
            }
        } while (!isSelectorValid());
        return true;
    }

    static std::string buildExpr(const std::string& left, char op, const std::string &right) {
        return std::string("(") + left + '' '' + op + '' '' + right + '')'';
    }

    std::string toString() const {
        Stack<std::string> stack;
        auto vi = values_.cbegin();
        auto oi = ops_.cbegin();
        for (auto s : selector_) {
            if (!s) {
                stack.push(std::to_string(*(vi++)));
                continue;
            }
            std::string top = stack.top();
            stack.pop();
            switch (*(oi++)) {
                case Op::Add:
                    stack.top() = buildExpr(stack.top(), ''+'', top);
                    break;
                case Op::Sub:
                    stack.top() = buildExpr(stack.top(), ''-'', top);
                    break;
                case Op::Mul:
                    stack.top() = buildExpr(stack.top(), ''*'', top);
                    break;
                case Op::Div:
                    stack.top() = buildExpr(stack.top(), ''/'', top);
                    break;
            }
        }
        return stack.top();
    }

public:
    Evaluator(const std::vector<Number>& values) :
            values_(values),
            ops_(values.size() - 1, FirstOp),
            selector_(2 * values.size() - 1, 0) {
        std::fill(selector_.begin() + values_.size(), selector_.end(), 1);
        std::sort(values_.begin(), values_.end());
    }

    // check for solutions
    // 1) we create valid permutations of our selector_ array (eg: "1 1 + 1 +",
    //    "1 1 1 + +", but skip "1 + 1 1 +" as that cannot be evaluated
    // 2) for each evaluation order, we permutate our values
    // 3) for each value permutation we check with each combination of
    //    operators
    // 
    // In the first version I used a local stack in eval() (see toString()) but
    // it turned out to be a performance bottleneck, so now I use a cached
    // stack. Reusing the stack gives an order of magnitude speed-up (from
    // 4.3sec to 0.7sec) due to avoiding repeated allocations.  Using
    // std::vector as a backing store also gives a slight performance boost
    // over the default std::deque.
    std::size_t check(Number target, bool singleResult = false) {
        Stack<Number> stack;

        std::size_t res = 0;
        do {
            do {
                do {
                    Number value = eval(stack);
                    if (value == target) {
                        ++res;
                        std::cout << target << " = " << toString() << "/n";
                        if (singleResult) {
                            return res;
                        }
                    }
                } while (nextOps());
            } while (nextValuesPermutation());
        } while (nextSelectorPermutation());
        return res;
    }
};

} // namespace

int main(int argc, const char **argv) {
    int i = 1;
    bool singleResult = false;
    if (argc > 1 && std::string("-s") == argv[1]) {
        singleResult = true;
        ++i;
    }
    if (argc < i + 2) {
        std::cerr << argv[0] << " [-s] <target> <digit>[ <digit>].../n";
        std::exit(1);
    }
    Number target = std::stoi(argv[i]);
    std::vector<Number> values;
    while (++i <  argc) {
        values.push_back(std::stoi(argv[i]));
    }
    Evaluator evaluator{values};
    std::size_t res = evaluator.check(target, singleResult);
    if (!singleResult) {
        std::cout << "Number of solutions: " << res << "/n";
    }
    return 0;
}