//Given a list of numbers and a target solution, determine the series of operations that join the list to produce the target solution

//valid operations are addition, subtraction, multiplication, and division

//IMPORTANT - the order of the numbers can change

var test1 = solve([25, 100, 9, 7, 3, 7], 881);

var solutions1 = ["3*7+100*7+9+25", "3*7+100*7+25+9", "7*3+100*7+9+25",  "7*3+100*7+25+9", "7/7+100*9-3-25", "7/7+100*9-25-3", "9-3/7+25+100*7", "9-3/7+100+25*7", "9/7+25+100*7-3", "9/7+100+25*7-3", "25-9*7*7-3+100", "25-9*7*7+100-3"]

checkSolutions(test1, solutions1);

​

var test2 = solve([6, 75, 3, 25, 50, 100], 952);

var solutions2 = ["3+100*6/50*75+25", "3+100*6*75/50+25", "3+100/50*6*75+25", "3+100/50*75*6+25", "3+100*75*6/50+25", "3+100*75/50*6+25", "6+100*3*75-50/25", "6+100*75*3-50/25", "100+3*6/50*75+25", "100+3*6*75/50+25", "100+3/50*6*75+25", "100+3/50*75*6+25", "100+3*75*6/50+25", "100+3*75/50*6+25", "100+6*3*75-50/25", "100+6*75*3-50/25"];

checkSolutions(test2, solutions2);

​

​

var test3 = solve([1,3,7,6,8,3], 250)

var solutions3 = ["3+3*7+1*6-8", "3+8*7+6*3+1", "7/3+3*8-1*6", "8+3*7+6*3+1"];

checkSolutions(test3, solutions3);

​

​

function solve(numberList, targetSolution) {

    var operations = ["+", "-", "*", "/"]

    var solutions = [];

    var allPermsOfList = permute(numberList);

    allPermsOfList = removeDuplicates(allPermsOfList);

    allPermsOfList.forEach(function(list) {

        solveRecursive(list, list[0].toString())

    });  

    return solutions;

​

    function solveRecursive(numberList, testExpression) {

        if (numberList.length == 1) {

            if (approximatelyEqual(numberList[0], targetSolution)) {

                solutions.push(testExpression);

            }     

        } else {

            for(var operatorNum = 0; operatorNum < operations.length; operatorNum ++) {

                var newExpression = testExpression + operations[operatorNum] + numberList[1].toString();

                var collapsedList = collapseE1E2(numberList, operations[operatorNum]);

                solveRecursive(collapsedList, newExpression);

            }

        }

​

    }

​

    function collapseE1E2(numberList, operation) {

        var copyArray = numberList.slice();

        var combined = copyArray[0];

        switch(operation) {

            case "+":

                combined += copyArray[1];

                break;

            case "-":

                combined -= copyArray[1];

                break;

            case "*":

                combined *= copyArray[1];

                break;

            case "/":

                combined /= copyArray[1];

                break;

            default:

                throw("Unknown operation encountered during combination attempt!");

        }

        copyArray.splice(0, 2, combined);

        return copyArray;

    }

​

    function approximatelyEqual(n1, n2) {

        if(Math.abs(n1 - n2 ) < 0.00001) { //ish? sure.

            return true;

        }

    }

}

​

//Heap's Algorithm for Generating Permutations https://en.wikipedia.org/wiki/Heap%27s_algorithm

function permute(array) {

​

    var permutations = [];

    generate(array);

    return permutations;

​

    function generate (array, n) {

        n = n || array.length;

        if (n == 1) {

            permutations.push(array.slice());

        } else {

            for (var i = 0; i < n - 1; i ++) {

                generate(array, n - 1);

                if (n % 2 === 0) {

                    swap(array, i, n-1);

                } else {

                    swap(array, 0, n-1)

                }

            }

             generate(array, n-1);

        }

    } 

​

    function swap (array, a, b) {

        var temp = array[a];

        array[a] = array[b];

        array[b] = temp;

    }   

}

​

function removeDuplicates(array) {

    var seen = {};

    return array.filter(function(item) {

        return seen.hasOwnProperty(item) ? false : (seen[item] = true);

    })

}

​

function checkSolutions(answers, solutions) {

    console.log("Answers found: " + answers.length)

    console.log("Solutions: " + solutions.length);

    for(var i = 0; i < solutions.length; i++) {

        var unmatched = true;

        for(var j = 0; j < answers.length; j++) {

            if (solutions[i] == answers[j]) {

                unmatched = false;

            }

        }

        if (unmatched) {

            console.log("Unaccounted Solution: "+ solutions[i]);

        }

    }

    for(var i = 0; i < answers.length; i++) {

        var unmatched = true;

        for(var j = 0; j < solutions.length; j++) {

            if (answers[i] == solutions[j]) {

                unmatched = false;

            }

        }

        if (unmatched) {

            console.log("Unaccounted Answers: "+ answers[i]);

        }

    }

​

    console.log("Answers: " + answers.join(", "));

}