StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This was a fun question. Here's my full solution:</p> <pre><code>ExprEval[nums_, ops_] := Fold[ #2[[1]][#1, #2[[2]]] &, First@nums, Transpose[{ops, Rest@nums}]] SymbolicEval[nums_, ops_] := ExprEval[nums, ToString /@ ops] GetExpression[nums_, ops_, target_] := Select[ Tuples[ops, Length@nums - 1], (target == ExprEval[nums, #]) &] </code></pre> <p>Usage example:</p> <pre><code>nums = {-1, 1, 2, 3}; ops = {Plus, Subtract, Times, Divide}; solutions = GetExpression[nums, ops, 3] ExprEval[nums, #] & /@ solutions SymbolicEval[nums, #] & /@ solutions </code></pre> <p>Outputs:</p> <pre><code>{{Plus, Times, Plus}, {Plus, Divide, Plus}, {Subtract, Plus, Plus}, {Times, Plus, Times}, {Divide, Plus, Times}} {3, 3, 3, 3, 3} {"Plus"["Times"["Plus"[-1, 1], 2], 3], "Plus"["Divide"["Plus"[-1, 1], 2], 3], "Plus"["Plus"["Subtract"[-1, 1], 2], 3], "Times"["Plus"["Times"[-1, 1], 2], 3], "Times"["Plus"["Divide"[-1, 1], 2], 3]} </code></pre> <hr> <p><strong>How it works</strong></p> <p>The <code>ExprEval</code> function takes in the numbers and operations, and applies them using (I think) RPN:</p> <pre><code>ExprEval[{1, 2, 3}, {Plus, Times}] == (1 + 2) * 3 </code></pre> <p>It does this by continually folding pairs of numbers using the appropriate operation.</p> <p>Now that I have a way to evaluate an expression tree, I just needed to generate them. Using <code>Tuples</code>, I'm able to generate all the different operators that I would intersperse between the numbers.</p> <p>Once you get all possible operations, I used <code>Select</code> to pick out the the ones that evaluate to the target number.</p> <hr> <p><strong>Drawbacks</strong></p> <p>The solution above is <em>really</em> slow. Generating all the possible tuples is exponential in time. If there are k operations and n numbers, it's on the order of O(k^n).</p> <p>For <code>n = 10</code>, it took 6 seconds to complete on Win 7 x64, Core i7 860, 12 GB RAM. The timings of the runs match the theoretical time complexity almost exactly:</p> <p><img src="https://i.stack.imgur.com/pyIdS.png" alt="Timings"></p> <p>Red line is the theoretical, blue is experimental. The x-axis is size of the nums input and the y-axis is the time in seconds to enumerate all solutions.</p> <p>The above solution also solves the problem using a functional programming style. It looks pretty, but the thing also sucks up a butt ton of memory since it's storing the full results at nearly every step.</p> <p>It doesn't even make use of parallelization, and I'm not entirely certain how you would even parallelize the solution I produced.</p> <hr> <p><strong>Some limitations</strong></p> <p>Mr. Wizard brought to my attention that this code only solves for only particular set of solutions. Given some input such as <code>{a, b, c, d, e, ... }</code> it only permutes the operators in between the numbers. It doesn't permute the ordering of the numbers. If it were to permute the numbers as well, the time complexity would rise up to <code>O(k^n * n!)</code> where <code>k</code> is the number of operators and <code>n</code> is the length of the input number array.</p> <p>The following will produce the set of solutions for any permutation of the input numbers and operators:</p> <pre><code>(* generates a lists of the form { {number permutation, {{op order 1}, {op order 2}, ... } }, ... }*) GetAllExpressions[nums_, ops_, target_] := ParallelMap[{#, GetExpression[#, ops, target]} &, Tuples[nums, Length@nums]] </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload