In the previous post, an exhaustive evaluation of RPN expressions was used to solve the (1,3,4,6)-Puzzle. It wasn’t a good solution as the generation of those expressions was inefficient.

A better method might be to construct binary trees with the numbers as leaves and operators as roots of subtrees. Here is one such solution in k:

p:{y(,/{y,/:&~x in y}[!x]')/,()} / permutation of y items out of !x
u:{{(,y),&~x in y}[!x]'p[x]y} / append unselected items of p[x]y
r:{,/.[a;(!#a:y@u[#y]2;0);{y,x};]'x} / add operators(x) to all head items
t:{,/(-1+#y)(,/r[x]')/,y} / all binary trees (with repetition)
e:{$[0>@x;x;(*x). e'1_x]} / evaluate each binary tree recursively
s:{?a@&z=e'a:t[x]y} / x:operators y:numbers z:target

Explanation:

- p() generates permutations of y indices taken from !x.
- u() appends the unused indices to each permutation generated by p().
- r() is slightly harder to explain. Effectively it takes 2 elements from a list, combines them with an operator and puts the result back to the head of the list.
- t() uses r() to iteratively build up binary trees. Note that some trees are repeated.
- e() is a recursive evaluator of each tree.
- s() is the solver. Due to the repeated binary trees, it is necessary to call distinct (?) before returning the results.

This is much faster than the previous solution. But there probably is a more efficient method. Another post for another day. :-)

The code is here: 1346b_k

### Like this:

Like Loading...

*Related*

## Leave a Reply