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"?

See also 'Beating C with...':

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"
answer:s input

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 0s 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.

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.

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.


To learn more about Shakti k, see this unofficial tutorial and reference.

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

About Solarpunk Systems

Inspiration...

Automated discovery:

Stellar address: GDU2THPYFWOY7Z5TDV4LAZOVBKACGPLFM5TQ3O2K22ACXCJXWGJOKY7M