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 »

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

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

Randomized N Queens in k

In an earlier post, I described an N Queens solver that returned all solutions for a given board size N. However that approach is too slow for large N due to the enormous search space. For large N, it seemed more appropriate to construct one solution at a time. The following is k code does that:

row:{&~(!y)in,/x+|-1 0 1*/:1+!#x}
rnd:{(-#x)?x}
rqn:{$[y=#x;x;do[#a:rnd row[x]y;$[y>#b:.z.s[x,*a]y;a_:0;:b]]]}()

Explanation:

  • The row() function returns the available positions in the next row.
  • The rnd() returns a random permutation of its input.
  • The rqn() function solves the problem by recursively iterating over all available positions in the next row. It returns only when a solution is found (y=#x).

The updated code is here: qns2_k.

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

Finding words in k

Facebook has a game called Word Challenge (on Yahoo it is known as Text Twist). The idea of the game is to form as many words as possible (of minimum length 3) given a set of 6 characters. It is the type of problem that can be easily solved with k or q.

My first attempt is basically brute-force:

w:w@=#:'w:?_0:`$words                         / read words & group by length
p:{[n;r]r(,/{y,/:&~x in y}[!n]')/,()}         / nPr; permute r items from !n
f:{[r;s],/a@'(a:w r)(&:in)'s@p[#s]'r}         / find words; r:lengths s:chars

The first line reads in a list of possible English words from a file and groups them by length. The second line is used to create the permutation (nPr) indices. The last line checks whether the words in the file appear in the list of permutations of the given characters.

While it works well for 6 or less characters, the performance is poor for longer strings since nPr is huge for large n and r. My second solution is better:

v:v@={x@<x}'v:?_0:`$words                     / read words, sort & group
c:{[n;r]r(,/{_[y-1+#z;!*z,x],\:z}[n;r]')/,()} / nCr; choose r items from !n
g:{[r;s]a@&0<#:'a:,/v@?,/(s@<s)@c[#s]'r}      / find words;

The first line reads in the words, sorts each word lexicographically (think of it as reducing each word to a canonical form) and groups them according to that canonical form. The second line creates the combination (nCr) indices. The last line takes the characters, creates a list of all canonical forms obtainable from combinations of the characters and retrieves all the words associated with each canonical form. The performance is much faster because nCr is smaller and the pre-processing of v helps a lot.

Here’s a sample output for the characters “qwertyzxcvbi” and a list of 98,569 English words (/etc/dictionaries-common/words in Ubuntu). It took only 49 ms to compute.

brevity cervix verity zyrtec bizet brice
bryce   civet  evict  ritzy  rivet tiber
tribe   trice  twice  write  bert  bevy
bier    bite   bret   brew   brie  brit
byte    cite   city   crew   crib  eric
exit    ibex   rice   rite   ritz  rive
teri    tier   tire   trey   tyre  verb
very    vibe   vice   view   weir  wire
wiry    wite   wive   writ   yeti  bet
bic     bit    bye    cry    ice   icy
ire     ivy    rev    rex    rib   rte
rye     tex    tic    tie    try   vet
vex     vic    vie    web    wei   wet
wit     wry    yet    yew    zit

The code is here: fbwc.k.

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

N Queens in k

I read the Eight Queens article on nsl.com. It describes a nice algorithm to solve the problem. The given code however does not work in the current q/k4 interpreter. (The dvl function is not implemented.)

So I wrote my own:

q7:{[n]n(,/{y,/:&~x in,/y+|-1 0 1*/:1+!#y}[!n]')/,()}

It returns all solutions for a board of size n x n. For n larger than 8, it could probably be made more efficient by doing some pre-computation. The code (including several other versions) is here: qns_k.

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

More Sudoku solvers in k and q

I was informed by Attila that the Sudoku solver I mentioned in my previous post wasn’t the only version developed by Arthur. There’s a shorter one here: http://nsl.com/k/sudoku/aw3.k. In fact, in the same directory there are several other solvers by Arthur, Attila and Roger Hui.

So here is all 72-bytes (including the 2 trailing \n) of the shortest Sudoku solver I’ve seen to date:

p,:3/:_(p:9\:!81)%3
s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x}

and its translation to q:

P,:3 sv floor(P:9 vs til 81)%3
S:{first(enlist x)(raze@{@[x;y;:;]each where 21=x[where(or)over P[;y]=P]?til 10}')/where not x}

How does it work? Unlike the previous solver, there is considerable simplification.

  1. The P array now comprises of 3 lists: the row, column and sub-square. So P[;i] returns a 3 element vector containing the row, column and sub-square of position i.
  2. The S function is no longer recursive. Instead it iterates over the unfilled positions of the board (/where not x). At each iteration, “where(or)over P[;y]=P is used to identify those positions that lies on the same row, column and sub-square. The “?til 10” returns a list of those positions where the numbers 0 to 9 first appeared. As there are 21 positions, a value of 21 indicates that the corresponding number is missing. So “where 21=” identifies those missing numbers which are then exhaustively substituted using @[x;y;:;]. The “raze” is required to flatten the resulting nested list.

Here is the downloadable code: sudoku2_q.

Posted in k&q. Tags: , . 3 Comments »

Sudoku solver translated from k to q

Many months ago I came across a Sudoku solver written in k by Arthur Whitney:

p:+{(=x)x}'p,,3/:_(p:,/'+:\9#'!9)%3
f:{$[&/x;,x;,/f'@[x;i;:;]'&27=x[,/p i:x?0]?!10]}

Amazingly it is only 2 lines of code. I decided to see if I can translate it into q. The translation was relatively painless as the two languages are so similar. Here it is in q:

P:flip{(group x)x}each P,enlist 3 sv floor(P:raze each flip scan 9#'til 9)%3
F:{$[min x;enlist x;raze F each@[x;i;:;]each where 27=x[raze P i:x?0]?til 10]}

Still 2 lines of code. But the real question is: how does it work? There was no explanation where I found the k code and so I have to go through it line by line (literally speaking).

Here’s a quick summary of how it works:

  1. Treat the 9 x 9 Sudoku board as an array of 81 squares indexed from 0 to 80. So every position on the board corresponds to a number between 0 and 80 inclusive.
  2. Each position has a row , column and sub-square number (0 to 8 inclusive). These are computed inside the expression for P as intermediate values. They are then reorganized such that positions from the same row, column and sub-square are grouped together. The end-effect is that for any position i on the board, P[i] returns a list comprising
    • a list of positions on the same row as i,
    • a list of positions on the same column as i, and
    • a list of positions on the same sub-square as i.
  3. The second line of code is a recursive function F. If the input Sudoku board does not have an empty position (indicated by 0), F returns the board as it is already solved. If there is an empty position at i, F uses P to identify all positions sharing the same row, column and sub-square as i. The numbers from 1 to 9 which did not appear in these positions are exhaustively substituted into position i and the function F is invoked on the newly-updated board.

A clearer and more illustrative explanation of the algorithms is available in this code: sudoku_q. (It is tedious to write q on WordPress. So I’ve moved the explanation into the code instead.)

Update: I’ve written an article on an even shorter implementation here.

Posted in k&q. Tags: , . 2 Comments »