NYCJUG/2012-09-11

From J Wiki
Jump to navigation Jump to search

Sudoku, statistics, distributions, effect of noise on short-term memory, data chunking, mathematical brain area


Location:: ThomasNet

Meeting Agenda for NYCJUG 20120911

1. Beginner's regatta: generating complete Sudokus - how many are there?  See
"CodeGolf-SudokuGenerator.pdf" and "SolvedSudokuPuzzleGeneration.pdf".


2. Show-and-tell: Building families of statistical distributions - Poisson and
Beta - see "Beta distribution - selections.pdf".


3. Advanced topics: an example of high-dimensional data presentation - see
"Interactive High-Dimensional data presentation - GGobi.pdf" and
"interface-classification-boundariesInHighDimensions.pdf".


4. Learning, teaching and promoting J, et al.: data on how we think and what
makes us more or less effective as thinkers: see "Noisy surroundings take toll
on short.pdf", "Inattention blindness due to brain load.pdf", "Applying New
Rules Costly.pdf", "Motor Chunking - how our brains parse and concatenate
learned actions.pdf", "General Information about Chunking.pdf",
"Using Motor-Chunking in Education.pdf", and " Mathematics or Memory - collision
course in brain.pdf"

An example of a fun introduction to a language: see "Land of Lisp.pdf".

See "Pretty Pictures in J.pdf" and "Less Than Brute Force.pdf".

Proceedings

...

Beginner's Regatta

The following is from [From: http://codegolf.stackexchange.com/questions/5693/minimal-sudoku-generator this CodeGolf page.]

Minimal Sudoku Generator

Ask questions if you need to, I'll elaborate on anything that needs clarified. My challenge is to unsolve a sudoku to a minimal state. Basically take a supplied, solved, sudoku board and unsolve it as far as possible while keeping the solution unique. I'll leave input up to you, I don't like forcing anything which would make some solutions longer. Output can be anything reasonable, as long as it spans the nine lines it'll take to display the sudoku board, for example: 

{[0,0,0], [0,0,0], [0,1,0]} ┐
{[4,0,0], [0,1,0], [0,0,0]} ├ Easily understood to me
{[1,2,0], [0,0,0], [0,0,0]} ┘

000000010 ┐
400010000 ├ A-OKAY
120000000 ┘

000, 000, 010 ┐
400, 010, 000 ├ Perfectly fine
120, 000, 000 ┘

000000010400010000120000000 <-- Not okay!
Example

input: 

693 784 512
487 512 936
125 963 874

932 651 487
568 247 391
741 398 625

319 475 268
856 129 743
274 836 159

output: 

000 000 010
400 000 000
020 000 000

000 050 407
008 000 300
001 090 000

300 400 200
050 100 000
000 806 000

Most minimal answer in shortest time is the winner.

Solved Sudoku Puzzles: How Many?

A “solved Sudoku puzzle” is a 3x3 arrangement of 3x3 tables where each table contains the digits one through nine, as does each line of digits across the rows and down the columns throughout the arrangement of tables. The number of possible arrangements of nine tables without paying attention to what makes an arrangement a valid sudoku, is 

      9^~!9
1.09111e50

This large number is simple enough to calculate but does not address the more difficult question of how many valid sudoku arrangements there are. How might we figure out this number? To start with, let's consider only the top leftmost square in isolation. Obviously, there are !9 ways to permute these nine values, or 362,880. Since any permutation will do, let's start with the simplest one for the square in the position (0,0): 

   ]I9=: >:i.9            NB. The digits we care about
1 2 3 4 5 6 7 8 9
   ]sq00=. 3 3 $ 0 A. I9  NB. Their 0th “anagram”
1 2 3
4 5 6
7 8 9

An Interesting Wrong Turn

Now consider the next table, the one to left of this first one. The first row of this first table over can contain any of our nine digits except those in the first row of sq00, or 

(0{sq00) -. I9

Similarly, the second row of this next table over can have any digits except those in the second row of sq00, or 

(1{sq00) -. I9

The same logic applies to the third row. Combining these ideas, the possibilities for each row of the next table over is 

   (<I9)-.&.> <"1 sq00
+-----------+-----------+-----------+
|4 5 6 7 8 9|1 2 3 7 8 9|1 2 3 4 5 6|
+-----------+-----------+-----------+

Taking all combinations of these possibilities 

   $ { (<I9)-.&.> <"1 sq00
6 6 6
   $, { (<I9)-.&.> <"1 sq00
216
   5{., { (<I9)-.&.> <"1 sq00
+-----+-----+-----+-----+-----+
|4 1 1|4 1 2|4 1 3|4 1 4|4 1 5|
+-----+-----+-----+-----+-----+

Looking at these first few, we see an obvious problem but, since there are so few possibilities, it's simple enough to weed out the obviously wrong ones. 

   3!6
20
   $ixs3of6=. ~./:~"1 ] 3{."1 (i.!6) A. i.6
20 3
   /:~ ~. ,ixs3of6
0 1 2 3 4 5
   20^3
8000
   ${ (<ixs3of6) {&.> (<I9)-.&.> <"1 sq00
20 3 20 3 20 3
   $0 2 4 1 3 5|:{ (<ixs3of6) {&.> (<I9)-.&.> <"1 sq00
20 20 20 3 3 3
   $~.>,<"2]0 2 4 1 3 5|:{ (<ixs3of6) {&.> (<I9)-.&.> <"1 sq00
2400 3 3
   
   $ { (<I9)-.&.> <"1 sq00
6 6 6
   $ >{ (<I9)-.&.> <"1 sq00
6 6 6 3

   allPossRows=. { (<I9)-.&.> <"1 sq00
   +/,3=#&>~.&.> allPossRows
162
   162^3
4.25153e6
   rp=. (<I9)-.&.> <"1 sq00
   apr=. (,allPossRows)#~,3=#&>~.&.> allPossRows
   $apr e.&.>/ rp
162 3
   3{.apr e.&.>/ rp
+-----+-----+-----+
|1 0 0|0 1 1|1 1 1|
+-----+-----+-----+
|1 0 0|0 1 1|1 1 1|
+-----+-----+-----+
|1 0 1|0 1 0|1 1 1|
+-----+-----+-----+
   $3=&>|:+/&.>apr e.&.>/ rp
3 162
   'r0 r1 r2'=. 3=&>|:+/&.>apr e.&.>/ rp
   +/&>r0;r1;r2
36 36 36
   */+/&>r0;r1;r2
46656
   216^2
46656
   $>(r0#apr),&.>/(r1#apr),:&.>/r2#apr
36 36 36 3 3
   $(r0#apr),&.>/(r1#apr),:&.>/r2#apr
36 36 36
   $,(r0#apr),&.>/(r1#apr),:&.>/r2#apr
46656
   1 10 100 1000{,(r0#apr),&.>/(r1#apr),:&.>/r2#apr
+-----+-----+-----+-----+
|4 7 5|4 7 5|4 7 5|4 7 5|
|7 1 2|7 1 2|7 2 1|9 2 3|
|4 1 3|4 3 5|6 2 1|6 2 1|
+-----+-----+-----+-----+
   apr=. ,(r0#apr),&.>/(r1#apr),:&.>/r2#apr
   $apr#~9=([: # [: ~. ,)&>apr
432
   $apr=. apr#~9=([: # [: ~. ,)&>apr
432
   1 10 100{apr
+-----+-----+-----+
|4 7 5|4 7 5|5 8 4|
|8 9 1|9 8 3|7 9 3|
|6 3 2|6 1 2|6 1 2|
+-----+-----+-----+
   432^2
186624

Now find the tables below: 

   allPoss=. { cp=. (<I9)-.&.> <"1 |:sq00
   apc=. (,allPoss)#~,3=#&>~.&.> allPoss
   'c0 c1 c2'=. 3=&>|:+/&.>apc e.&.>/ cp
   apc=. ,(c0#apc),&.>/(c1#apc),:&.>/c2#apc
   $apc=. |:&.>apc#~9=([: # [: ~. ,)&>apc
432
   3{.apc
+-----+-----+-----+
|2 6 8|2 6 8|2 6 8|
|3 9 4|3 9 7|3 9 1|
|5 1 7|5 1 4|5 4 7|
+-----+-----+-----+
   isValidDO
4 : 0
   rawPoss=. (<I9)-.&.>(<"1 x),&.>/<"1|:y
   -.0 e. ,#&>(,&.>/~i.3) possibleIntersection &.> <rawPoss
NB.EG valmat=. down isValidDO&>/ over
)

   6!:2 'valcombs=. (([:$])#:[:I.[:,]) apc isValidDO &>/ apr'
58.7522
   $valcombs
26880 2

   possibleIntersection
4 : '(,{(0{x){y)([#~[ e. ]) ,{(1{x){"1 y'
    
   2 2$4{.sq00;(0{apr),_1{apc
+-----+-----+
|1 2 3|4 7 5|
|4 5 6|8 9 1|
|7 8 9|6 2 3|
+-----+-----+
|9 3 5|     |
|6 7 1|     |
|8 4 2|     |
+-----+-----+


Better than Brute Force Solution?

The empty square shown above will be a recurring theme as we fill in successive squares of this puzzle. Currently, I have a “brute force” solution to generate all possible values for the blank square based on the restrictions introduced by the square above and to the left of it. 

   above;left
+-----+-----+
|4 7 5|9 3 5|
|8 9 1|6 7 1|
|6 2 3|8 4 2|
+-----+-----+

   (<"1 left) ,&.>/ <"1 |:above
+-----------+-----------+-----------+
|9 3 5 4 8 6|9 3 5 7 9 2|9 3 5 5 1 3|
+-----------+-----------+-----------+
|6 7 1 4 8 6|6 7 1 7 9 2|6 7 1 5 1 3|
+-----------+-----------+-----------+
|8 4 2 4 8 6|8 4 2 7 9 2|8 4 2 5 1 3|
+-----------+-----------+-----------+

   ]poss=. (<I9)-.&.>(<"1 left) ,&.>/ <"1 |:above
+---------+-------+---------+
|1 2 7    |1 4 6 8|2 4 6 7 8|
+---------+-------+---------+
|2 3 5 9  |3 4 5 8|2 4 8 9  |
+---------+-------+---------+
|1 3 5 7 9|1 3 5 6|6 7 9    |
+---------+-------+---------+

The problem I have not solved is how to quickly generate all possible solutions given the restrictions embodied in poss.

Show-and-Tell

The following [From http://en.wikipedia.org/wiki/Beta_distribution is from Wikipedia.]

Beta Distribution

Not to confused with Beta function.

In probability theory and statistics, the beta distribution is a family of continuous probability distributions defined on the interval (0, 1) parameterized by two positive shape parameters, typically denoted by α and β. The beta distribution can be suited to the statistical modelling of proportions in applications where values of proportions equal to 0 or 1 do not occur. One theoretical case where the beta distribution arises is as the distribution of the ratio formed by one random variable having a Gamma distribution divided by the sum of it and another independent random variable also having a Gamma distribution with the same scale parameter (but possibly different shape parameter). 639px-Beta distribution pdf.svg.png
The usual formulation of the beta distribution is also known as the beta distribution of the first kind, whereas beta distribution of the second kind is an alternative name for the beta prime distribution. 640px-Beta distribution cdf.svg.png 
=== Characterization ===

Probability density function

The probability density function of the beta distribution is:

Advanced Topics

...

Learning, teaching and promoting J

...

Attachments

Retrieved from "https://code.jsoftware.com/mediawiki/index.php?title=NYCJUG/2012-09-11&oldid=41273"