TripleByte Long Test Question

tb_test.js

'use strict';

var listOfNumbers = "32435406576";
var targetNumber  = 1047;

console.log(getValidExpressions(listOfNumbers, targetNumber));

function getValidExpressions(listOfNumbers, targetNumber) {
    if (!listOfNumbers || (!targetNumber && targetNumber !== 0)) {
        return [];
    }

    if (typeof listOfNumbers === 'int') {
        listOfNumbers = listOfNumbers.toString();
    }

    if (typeof listOfNumbers !== 'string') {
        return [];
    }

    // Initiate algorithm
    return generate(listOfNumbers, targetNumber)
        // Compact list of valid results to one dimension.
        .reduce(function(carry, part) {
            return carry.concat(part);
        }, []);
}

// Generates a list of valid expressions resulting from
// the passed list of numbers, and a target number.
function generate(numbers, target) {
    // Split number string into a list.
    var numberParts = numbers.split('');
    // Generate a calculate function for our target number.
    var calculate = calculator(target);

    // Create an outer loop over all the numbers in our numberlist.
    return numberParts.map(function(outerNumber, outerIndex) {
        // Create an inner loop over all the numbers in our numberlist
        return numberParts.reduce(function(sequence, innerNumber, innerIndex) {
            // Add the list of valid expressions from the current
            // permutation to the list of all valid expressions.
            return sequence.concat(
                // Pass the current permutation to calculate()
                // and get a list of all valid combinations of
                // operators that result in an expression producing
                // our target.
                calculate(
                    // Generate the next permutation from the numbers in
                    // our list.
                    permutate(outerIndex, innerIndex, numberParts)
                )
            );
        }, []);
    });
}

// Generates a single permutation from a list of numbers based
// on current inner/outer index positions, e.g.
//
//  permutate(o = 2, i = 4, [1, 2, 3, 4, 5, 6]);
//  |
//  |        o
//  | [1, 2, 3, 4, 5, 6]
//  |              i
//  |
//  => [1,2,345,6]
//
function permutate(outerIndex, innerIndex, numberParts) {
    // If both the indices are zero, we return the base
    // case (no joined numbers).
    if (!outerIndex && !innerIndex) {
        return numberParts;
    }

    // If the inner index has not yet reached the outer index,
    // or if they're equal but non-zero, we'd just be
    // generating invalid permutations or duplicates
    // of the base case (no joined numbers).
    if (outerIndex >= innerIndex) {
        return [];
    }

    return [].concat(
        // Numbers in the sequence before the number being concatenated.
        // From the start of the sequence to the number before the outer index.
        numberParts.slice(0, outerIndex),
        // Number being concatenated.
        // From the outer index to the inner index.
        numberParts.slice(outerIndex, innerIndex+1).join(''),
        // Numbers in the sequence after the number being concatenated.
        // From the number after the inner index to the end of the sequence.
        numberParts.slice(innerIndex+1, numberParts.length)
    );
}

// Returns a function that evaluates an array of numbers
// and returns a list of expressions that result in the
// target.
function calculator(target) {
    // Setup signs of op functions,
    // to make it easier to generate
    // the expression string in the
    // calculate function.
    add.sign = '+';
    multiply.sign = '*';
    divide.sign = '/';
    subtract.sign = '-';

    function add(a,b) {
        return a + b;
    }

    function multiply(a,b) {
        return a * b;
    }

    function divide(a,b) {
        return a/b;
    }

    function subtract(a,b) {
        return a-b;
    }

    function calculate(sequence, expression, sum, op, valid) {
        var current = parseFloat(sequence[0], 10);
        var rest    = sequence.slice(1);

        // Initial case,
        // Calculate was called externally.
        if (arguments.length === 1) {
            expression = current;
            sum = current;
            valid = [];
        }

        if (op) {
            // handle special case of division by zero by
            // exiting from this branch.
            if (op === divide && current === 0) {
                return valid;
            }
            sum = op(sum, current);
            expression = expression + ' ' + op.sign + ' ' + current;
        }

        // Keep recursing
        if (rest.length) {
            calculate(rest, expression, sum, add, valid);
            calculate(rest, expression, sum, subtract, valid);
            calculate(rest, expression, sum, divide, valid);
            calculate(rest, expression, sum, multiply, valid);
        } else {
        // ... or check if the sum matches our target (terminal case).
            if (sum === target) {
                valid.push(expression + ' = ' + sum);
            }
        }

        return valid;
    }


    return function(sequence) {
        // Wrap in another closure to only
        // check validity of sequence once ...
        if (!sequence.length) {
            return [];
        }
        // ... and shield recursion arguments from
        // being passed in from the outside.
        return calculate(sequence);
    }
}