## Notes on k

### `wc` in k

Crowd-sourced, ngn-refined:

``wc:+/'(1=;<':4=;#:)@\:" \n\t\r"?``

On big.txt:

`````` ."\\wc big.txt"
," 128457 1095695 6488666 big.txt"
wc@1:`big.txt
128457 1095695 6488666

/ total ms on k 2019-09-20
\t:100 wc@1:`big.txt
2767
\perf stat -r 100 -B wc big.txt
/ 0.28s/run (10x time in my vm)``````

Will future k close on SIMD C (Reddit, Lobsters): 0.3sec for 100 runs?

And if we're golfing and order doesn't matter...

``+/+1,(1=;<':4=)@\:" \n\t\r"?``

### Sudoku

``````p:(&|/p=)'+p,:,3/:3/p:!9 9
f:,/{@[x;y;]'10^x p y}'
s:{f/[,x;&~x]}
input:,/("200370009";"009200007"
"001004002";"050000800"
"008000900";"006000040"
"900100500";"800007600"
"400089001")-"0"
``````

kparc.com's solver, expressed in Shakti k and split over more than 2 lines.

I did not invent this solver, but I wanted to understand how it works.

The short answer is: pick an unknown slot; for each number left after excluding the known numbers in the same row/column/box, create a candidate solution; repeat for each candidate solution until all slots are filled. You now have a list of solutions.

Unknown cells are `0`s in the input. It's expressed as a string subtraction because it's shorter than writing the equivalent integer list literal.

`p` is a list of, for each cell in the Sudoku grid, the indices of all cells that directly restrict what its value can be (ie share a row, column and/or box). It is the same regardless of the input.

• It generates a list of box-row-col ID lists using floored int division (`3/`) and conversion from base 3 digits (`3/:`).
• Then, for each ID list, it finds the indices of all cells that share with it a row, col or box (`(&|/p=)'`).

`s` returns a list of valid answers. `s` has shape `f/[x;y]` ie `x f/y`: it iterates left-to-right over the indices of the unknown cells (`&~x`), with an explicit starting state (`,x`). Each iteration fills one slot and returns an updated list of candidate solutions; that list, and the next unknown cell index, are inputs to the next iteration.

`f` does the real work in each iteration of `s`. It takes a list of candidate solutions and the index of an unknown cell, and returns the next set of WIP candidate solutions.

• The first iteration starts with the input puzzle (`,x`), enlisted because the iterator expects a list of candidate solutions.
• `p` is used to get the known values of cells that contend with the unknown cell examined in that iteration (`x p y`), to determine which possible values remain (`10^`). A lot of the time, the contending cells will cover all legal values, being 0–9 (ie it's a dead end), so `10^` will return an empty list.
• `@[x;y;]'` just says "for each legal value this cell could take, generate a candidate solution for consideration in the next iteration that has the unknown cell filled with that value".

When reading kparc's code, I couldn't understand how illegal solutions were weeded out. The answer is: if a candidate solution has no legal values for the unknown cell, then `10^` (and therefore `@[x;y;]'`) will return an empty list, so that solution won't spawn any children for inclusion in the candidate list used in the next iteration!

We can see the candidate count (`#:`) change each iteration by switching from over (`/`) to scan (`\`):

`````` / Candidate counts
l: #:'{f\[,x;&~x]} input

/ 5-at-a-time for display
` 1:,/"\n"/:,/'-5\$\$Ø 5#l
3    5   13   12   10
20   34   64  100   87
46   81   71  142  112
64   64  116  348 1010
2670 3373 2706  664  455
769 1857 3728 4480 3779
1020  184  184  294  210
120  100   49   98  196
182   66   12   12   24
38   14    1    1    1
1    1    1    1    1``````

Unfortunately 'hard' puzzles require a different approach, such as the one mentioned in Peter Norvig's article about his own solver. Try:

``````input:,/("400000805";"030000000"
"000700000";"020000060"
"000080400";"000010000"
"000603070";"500200000"
"104000000")-"0"``````

But hey, come on: it's a Sudoku solver in two lines of code.

See also John Scholes' APL walk-through video + Roger Hui's solver in J.

### Rule 30

Wikipedia
```                #
###
##  #
## ####
##  #   #
## #### ###
##  #    #  #
## ####  ######
##  #   ###     #
## #### ##  #   ###
##  #    # #### ##  #
## ####  ## #    # ####
##  #   ###  ##  ## #   #
## #### ##  ### ###  ## ###
##  #    # ###   #  ###  #  #
## ####  ## #  # #####  #######
##  #   ###  #### #    ###      #
```
``````/ setup
(r;c):16 60
start:(2/c)=!c

/ next: left XOR (mid OR right)
/ n1 by me. n2, n3 by k expert.
n1:{{~x=y|z} .' 3':0,x,0}
n2:{{~x=y|z} . +3':0,x,0}
n3:{~=[0,-1_x; x|1_x,0]}

` 0: " #" r n1\ start;   / show

/ check getting same results
~[r n1\ start; r n2\ start]
~[r n2\ start; r n3\ start]

/ speed (ms; lower=better)
\t:1000 r n1\ start      / 1445
\t:1000 r n2\ start      / 550
\t:1000 r n3\ start      / 36``````

Stellar address: `GDU2THPYFWOY7Z5TDV4LAZOVBKACGPLFM5TQ3O2K22ACXCJXWGJOKY7M`