Solver for (1, 3, 4, 6) Puzzle in k

The puzzle is this: given the numbers (1,3,4, 6) and the binary operators (+, -, *, /) form the integer 24 using all the numbers (once each) and some of the operators (may be repeated). Parenthesis are allowed, of course. E.g. the expression 3*(1+4*6) is a valid attempt but clearly the wrong solution.

I’ve previously solved this in Python: 1346.py. The basic idea is to exhaustively construct Reverse Polish Notation (RPN) expressions using all the numbers and 3 operators (chosen with replacement). It is much shorter when implemented in k:

c:{x@y(,/{_[*y,0;!x],\:y}[#x]')/,()}
p:{?x(#x)(,/{y,/:&~x in y}[!#x]')/,()}
e:{$[0>@f:*x;x;f[*g;*h],1_h:e 1_g:e 1_x]}
t:{1e-8>abs x-y}
s:{a@&t[z;*:'b]&1=#:'b:e'a:,/p'y,/:c[x;-1+#y]}

The Python version actually ran faster in this case because the algorithm to generate all RPNs is more optimized in the Python version.

Explanation:

• The function c() returns all possible y-tuples combinations of items in x, with replacement allowed. It is used to generate all possible 3-tuples of the 4 binary operators.
• The function p() returns all distinct permutations of the items in x. Since x may have repeated items, we apply ? to make the result distinct.
• The function e() is a recursive RPN evaluator which stores the result of its computation in the first element of the list returned. If the the entire expression is a valid RPN, the returned list will be a singleton.
• The function t() takes care of floating point trickiness (24 is not exactly the same as 24f sometimes).
• The function s() is the main solver. It starts by creating all ((#y)-1)-tuples combinations of the operators (x) and appending them to the numbers (y). The result is permuted to get a list of expressions and all permutations are then evaluated by e(). If the expression is a valid RPN (i.e. result is a singleton) and its evaluated value is the target (z), it would be selected.

The result for 24, 29 and -18 are as follows:

solution for 24
"(6%(1-(3%4)))"

solution for 29
"((3*(4+6))-1)"
"((3*(6+4))-1)"
"(((4+6)*3)-1)"
"(((6+4)*3)-1)"

solution for -18
"(6%(1-(4%3)))"

The code is here: 1346_k