Faster solver for (1,3,4,6) Puzzle in k

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

Advertisements
Posted in k&q. Tags: . Leave a Comment »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: