Here are 13 K problems ranging from medium to difficult. As we all know, the first solution is rarely the best one. It sometimes takes days or even weeks before a good solution pops into your head as an "aha!" moment. Each of the following problems can be solved without explicit looping or recursion. Finding the "array solution" is not always easy. In some cases it might make sense to solve the problem iteratively, by looping or through recursion, and then use the iterative algorithm to search for a more K-ish non-iterative solution. 0. Combinations Write a function 'cross' which takes a list a of lists (0 1 2;3 4;5 6 7 8) and returns a matrix of all combinations of elements from each list in a: cross(0 1 2;3 4;5 6 7 8) (0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 4 4 4 4 3 3 3 3 4 4 4 4 3 3 3 3 4 4 4 4 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8) 1. Fibonacci A recursive function which generates the first n+2 fibonacci numbers is easy to write in K (or most other languages): fib:{:[y;_f[x,+/-2#x]y-1;x]} fib[1 1;5] 1 1 2 3 5 8 13 Write an expression which does not contain a lambda which generates the first n+2 fibonacci numbers. 2. Dictionary to list. Write a function 'undict' which takes a nested dictionary and replaces each dictionary with a pair of lists: (symbols;values): d:.+(`a`b;(.+(`c`d`e;10 20 30);.+(`f`g;(40;.+(`h`i`j;50 60 70))))) undict d (`a `b ((`c `d `e 10 20 30) (`f `g (40 (`h `i `j 50 60 70))))) 3. Word wrap. Write a function 'wrap' which takes a width w and a string of words s and returns a list of strings which represent the word-wrap of s in w. For example, wrap[20;"Write a function 'wrap' which takes a width w and a string of words s and returns a list of strings which represent the word-wrap of s in w"] ("Write a function " "'wrap' which takes " "a width w and a " "string of words s " "and returns a list " "of strings which " "represent the " "word-wrap of s in " "w ") 4. Infinite loop. Write an infinite loop. Now find an expression which does not terminate and which does not use an explicit loop. 5. "Depends on me." Suppose we have the following calculation a:10 b:a+1 c:a+2 d:c+20 e:b+d f:e+4 g:f+5 In this example, if a is assigned a new value, then b, c, e, f and g need to be recalculated. In general, if any variable x is reassigned, then all the variables which depend on x need to be recalculated. Represent the dependency structure of the calculation above as a dictionary: s:.+(`a`b`c`d`e`f;(0#`;,`a;,`a;,`c;`b`d;,`e,`f)) Write a function 'dependson' which takes s and a single symbol v and returns a list of ALL the variables which depend on v: dependson[s]`a `a`b`c`e`f`g dependson[s]`d `e`f`g 6. "Who moved?" You're given a vector of unique elements: v:10 20 30 40 50 60 70 Some operation has moved a single one of the elements into a new position: w:10 20 70 30 40 50 60 / 70 inserted between 10 and 20 There is a function which returns the index of the repositioned element: moved[v;w] 2 moved[10 20 30;20 30 10] 2 moved[10 20;20 10] 0 More examples: a:10 20 30 40 50 b:10 40 20 30 50 c:10 30 40 20 50 d:10 20 40 30 50 e:50 10 20 30 40 moved:{d?|/d:_abs(x?/:y)-!#x} a moved/:(b;c;d;e) 1 3 2 0 Write 'moved'. 7. Order expressions. Given a list of expressions d:c+b c:-b e:d*a b:10 a:20 We want to reorder them so that each variable is computed before it is used: b:10 c:-b a:20 d:c+b e:d*a Represent the expression list as a dictionary s: s:.+(`d`c`e`b`a;(`c`b;`b;`d`a;0#`;0#`)) There is a function which computes the reordering, e.g.: reorder s `b`c`d`a`e Write 'reorder'. 8. Trees. How would you represent the following tree in K? 0 1 2 3 4 5 6 7 8 Suppose the leaves have values attached to them: 0 1 2 : 20 3 : 30 4 5 6 : 60 7 : 70 8 : 80 Write a function to sum those values at the nodes: 0 : 260 = 50+210 1 : 50 = 20+30 2 : 20 3 : 30 4 : 210 = 210 5 : 210 = 60+70+80 6 : 60 7 : 70 8 : 80 9. Graphs Suppose we represent a graph using a dictionary to represent the edges: g:.+(`a`b`c`d`e`f`g`h`i`j;(),/:(`b`e`h;`c`f;0#`;0#`;`d`g;`e`j;`f;`i;`h;`j)) Write a function which detects the existence of cycles (loops) in a graph like the one above. hasloops g 1 Write a function which returns just the looping subgraphs: loopsof g .((`e `d `g ) (`f `e `j ) (`g ,`f ) (`h ,`i ) (`i ,`h ) (`j ,`j )) because e -> g -> f -> e and h -> i -> h and j->j. 10. Transitive Closure Write a function 'trans' which computes the transitive closure of a boolean matrix: m:(1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1) trans m (1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1) 11. Count Subsequences You're given two sequences a and b: a:`x`y`a`b`z`x`b`c`a`y`w`a`b`c`u`v`a`b`c`x b:`a`b`c Write a function 'seq' which returns the starting-indices of each occurrence of the b-sequence in the a-list: seq[a]b 11 16 seq[`x`y`b`c`a`u`v] !0 12. Converging Selection Write a k function 'select' which does converging selection on a table: t:.+(`f`g`h;(10 _draw 10;10 _draw 100;`foo`bar`baz 10 _draw 3)) / select from t where h=`foo,g<50 13. Squarification Write a function squarify which given an n x m integer matrix returns a k x k matrix, where k = n | m, the additional rows or columns padded out with 0. a:3 5#!15 a (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14) squarify a (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0 0 0 0 0 0 0 0 0) 14. Outline Sort Write a function u which given a list of o outline headings and subheadings, returns an index vector i such that the result of o u o is the sorted outline. o:("1.0";"1.0.1";"1.1.1";"1.2";"1.10";"1.11";"1.20";"1.20.1";"1.30";"1.9") u o 0 1 2 3 9 4 5 6 7 8 o u o ("1.0" "1.0.1" "1.1.1" "1.2" "1.9" "1.10" "1.11" "1.20" "1.20.1" "1.30") 15. Anesthesia (difficult) Write a query to determine for each anest the maximum number s of intersecting ids over periods of intersection. procs.id:10*1+!8 procs.anest:`baker`baker,6#`dow procs.start:0800 0900 0900 0800 1000 1230 1330 1800 procs.end:1100 1300 1530 1330 1130 1330 1430 1900 Here is the answer: id anest start end s --------------------- 10 baker 0800 1100 2 20 baker 0900 1300 2 30 dow 0900 1530 3 40 dow 0800 1330 3 50 dow 1000 1130 3 60 dow 1230 1330 3 70 dow 1330 1430 2 80 dow 1800 1900 1