[Jprogramming] May knight's challenge
Linda Alvord
lindaalvord at verizon.net
Wed May 2 14:01:03 HKT 2012
I basically got as far in you version as I did in Raul's.
I got a "simple version" from p to q but I couldn't understand what happens
when you the apply #~ to get to the next step.
This challenge was too challenging for me, but fun! I'm resting a little
with the next one and you'll probably find it too easy.
Thanks for all your help and I'm sure your careful presentation will be
thought provoking for some, like Raul, who really read J so fluently. I
think I'm at about the third grade reading level trying to read some of the
weighty classics.
Cheers. Linda
-----Original Message-----
From: programming-bounces at jsoftware.com
[mailto:programming-bounces at jsoftware.com] On Behalf Of David Ward Lambert
Sent: Tuesday, May 01, 2012 10:38 PM
To: programming
Subject: [Jprogramming] May knight's challenge
NB. The latter portion of this code demonstrates NB. various Markov chain
computations.
Note 'code notes'
Use Raul Miller's easy, useful
NOUN Adverb Conjunction verb
name convention.
Data structure:
o Board is a vector tallying *:N. Apparently, I
have virtualized BOARD. It exists in thought
only.
o The state is vector of 2 boxed knight paths
with next to move at head.
program should work for N in [3,9]
The upper limit stems from the chess
algebraic display algorithm.
1 piece moves each ply
)
N=: 8
NB. convert array coordinates to vector index
index=: N&#.
GRID=: 2 ({@:# <@:i.) N
CELLS=: ,/@:> GRID
JUMPS=: (, |."1) 1 2 *"1 (1 1,_1 1,_1 _1,:1 _1)
LC=: 26 }. Alpha_j_ NB. lowercase
CD=: }. Num_j_ NB. counting digits
NAMES=: ((LC {~ {.) , (CD {~ {:))"1 CELLS
NB. T are the circle of moves from each square
T=: <"2 CELLS+"1/JUMPS
NB. VerifyRange Interval is (]
NB. 0 means in range, 1 for outside
VerifyRange=: &(1 ~: I.)
assert 1 1 0 0 0 0 1 1 1 1 -: 1 5 VerifyRange i.10 Note 'why adverb?'
I like adverbs. When I write in other languages I hard-code constants,
then I have to rewrite, extracting and naming constants to generalize
my code. Adverbs will help me overcome this.
)
assert 0 -: 2 9 VerifyRange N NB. process check
none=: +:/ NB. works for a pair of numbers
MOVES2D=: (#~ none"1@:((_1+0,N)VerifyRange))&.> T
MOVES=: index&.> MOVES2D
NB. sorry, I like commuted hook
'WN BN'=: 2 ((A.~ ?)~ index) 1 1 ,: N - 2 2
choose=: {~ ?@:#
move=: choose@:>@:({&MOVES)
While=: conjunction def 'u^:v^:_'
position=: {:@:>
continue=: ~:&position/
assert 1 -: continue 2 3;4
assert 0 -: continue 2 3;4 2 3
ply=: {: , (, move@:position)&.>@:{.
NB. run the simulation
PATHS=: WN ply While continue@:;&, BN
NB. report
WN 4 : 0 PATHS
NB. algebraic notation for the moves
AN=. (('N' , [ , ' N' , ])/"2) NAMES {~ ,.&>/ y
NB. display the numbered moves
smoutput 'Move 0 shows setup.'
smoutput 'White plays first. Black wins.'
smoutput (,.~ '. ' ,"1~ ":@:,.@:i.@:#) AN
)
Note 'Markov chain'
Consider an (*:N) by (*:N) transition matrix.
Each row represents a square on the chess board,
so does each column. The row is the starting
square, the column is the index of end square.
The value at each row column cell is the
probability to move to the cell of the column starting from the cell
of the row. For example, the first row represents the corner cell a1.
From
a1 there are two legal moves, with equal
probability. Those two columns in top row will
have probability 1r2.
The probability that a knight is located at a square is the matrix
product of the current location vector by the transition probability
matrix. Repeat the matrix multiplication for each hop. Begin!
)
NB. transition probability matrix
NB. sorry, I like commuted hook
P=: ((%@:x:@:#@:[`[`]}~ >)~"0 1 (0 $~ ,~@:#)) MOVES
Note 'transition probability matrix'
4x4 symmetric corner of 8x8 chess board.
The display is chopped at right hand side for email.
Perhaps difficult to understand.
a1 a2 a3 a4..b1 b2 b3 b4..c1 c2 c3 c4..d
+--------------------------------------------------
a1| 0 0 0 0 0 0 1r2 0 0 1r2 0 0
a2| 0 0 0 0 0 0 0 1r3 1r3 0 1r3 0
a3| 0 0 0 0 1r4 0 0 0 0 1r4 0 1r4
a4| 0 0 0 0 0 1r4 0 0 0 0 1r4 0
.
b1| 0 0 1r3 0 0 0 0 0 0 0 1r3 0
b2| 0 0 0 1r4 0 0 0 0 0 0 0 1r4 1r
b3|1r6 0 0 0 0 0 0 0 1r6 0 0 0
b4| 0 1r6 0 0 0 0 0 0 0 1r6 0 0
.
c1| 0 1r4 0 0 0 0 1r4 0 0 0 0 0
c2|1r6 0 1r6 0 0 0 0 1r6 0 0 0 0
c3| 0 1r8 0 1r8 1r8 0 0 0 0 0 0 0 1r
c4| 0 0 1r8 0 0 1r8 0 0 0 0 0 0
.
d1| 0 0 0 0 0 1r4 0 0 0 0 1r4 0
d2| 0 0 0 0 1r6 0 1r6 0 0 0 0 1r6
d3| 0 0 0 0 0 1r8 0 1r8 1r8 0 0 0
d4| 0 0 0 0 0 0 1r8 0 0 1r8 0 0
)
start=: (i.@:# P)&=
mp=: +/ .*
Note 'various probabilities'
NB. percent probability to land on a square
NB. after 80 and 81 jumps.
NB. Observe the white-black alternation.
<.0.5+100*(_1 x: P)mp~^:80 81(start@:index 1 1)
1 0 2 0 2 0 2 0 0 2 0 4 0 4 0 2 2 0 5 0 5 0 4 0...
0 2 0 2 0 2 0 1 2 0 4 0 4 0 2 0 0 4 0 5 0 5 0 2...
NB. probability sum 1, knight still on board.
+/"1 (_1 x: P) mp~^:80 81 (start@:index 1 1)
1 1
NB. compute probability to be on same square
NB. after 6 hops. Different question from
NB. "The first time they meet is at move 6."
NB. locations after 6 hops
HOPS=: 6
P_CELL=: WN mp&(_1 x: P)^:HOPS@:,:&start BN
NB. show the probabilities (clipped at 50 colum
_ 50 {. 6j3 ": P_CELL
0.013 0.000 0.030 0.000 0.026 0.000 0.016 0.000 0
0.007 0.000 0.016 0.000 0.018 0.000 0.016 0.000 0
NB. Probability to share square at move 6
mp/ P_CELL
0.0349013
NB. Probability to share after
NB. 0, 2, ... , 22 plies.
NB. (display clipped!)
mp/"2 WN mp&(_1 x: P)^:(<12)@:,:&start BN
0 0 0.0117188 0.0226508 0.0313695 0.0322698 0.0349
NB. First capture can occur at move 2.
)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
More information about the Programming
mailing list