Game of Life in (one line of) k

In my previous post I mentioned several q implementation of Conway’s Game of Life. There are also some k implementations at nsl.com (see this page). The shortest one I know of comes from Arthur Whitney:

life:{3=a-x*4=a:2{+(0+':x)+1_x,0}/x}

The key insight here is that for each cell in the grid we can compute the number of occupied cells in its neighbourhood by (i.) summing its column-wise neighbours; and then (ii.) summing the row-wise neighbours of the first sum. To visualize the components of the sum in ASCII art:

  +---+---+---+---+       +---+---+---+---+       +---+---+---+---+
  |   |   |   |   |       |   |   |   |   |       |   |   |   |   |
  | 0 | 1 | 2 | 3 |       | 0 | 1 | 2 | 3 |       | 01|012|123|23 |
  |   |   |   |   |       | 4 | 5 | 6 | 7 |       | 45|456|567|67 |
  +---+---+---+---+       +---+---+---+---+       +---+---+---+---+
  |   |   |   |   |  col  | 0 | 1 | 2 | 3 |  row  | 01|012|123|23 |
  | 4 | 5 | 6 | 7 |  sum  | 4 | 5 | 6 | 7 |  sum  | 45|456|567|67 |
  |   |   |   |   | ----> | 8 | 9 | A | B | ----> | 89|89A|9AB|AB |
  +---+---+---+---+       +---+---+---+---+       +---+---+---+---+
  |   |   |   |   |       | 4 | 5 | 6 | 7 |       | 45|456|567|67 |
  | 8 | 9 | A | B |       | 8 | 9 | A | B |       | 89|89A|9AB|AB |
  |   |   |   |   |       |   |   |   |   |       |   |   |   |   |
  +---+---+---+---+       +---+---+---+---+       +---+---+---+---+

The code {+(0+’:x)+1_x,0} simply arranges the rows and computes the column-wise sums.

      x                (0+':x)            1_x,0
  +-------+       +---------------+     +-------+
  | 01234 |       | 01234         |     | 56789 |
  | 56789 | ----> | 56789 + 01234 |  +  | ABCDE |
  | ABCDE |       | ABCDE + 56789 |     | FGHIJ |
  | FGHIJ |       | FGHIJ + ABCDE |     |       |
  +-------+       +---------------+     +-------+

The flip (+) operation changes columns to rows so that the same {+(0+’:x)+1_x,0} code can be used to compute the row-wise sums. The 2nd flip restores the orientation of the grid.

The above Game of Life is not exactly the same as what I posted earlier since the boundary cells do not wrap around. To get a wrap-around version, we can use this one-liner:

life:{3=a-x*4=a:2{+x-2{|1_0+':x,1#x}/x}/x}

I will leave it to the reader to figure out how this works. :-)

Advertisements

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

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 »